Multi-robot coordination and task allocation

Many field missions are too large, too urgent or too risky for one robot. A fleet of weeding robots covers a farm in the spraying window; several AUVs map a seabed faster; a team of ground robots and drones explores a mine after an accident. Multiple robots can work in parallel, specialize, and back each other up, but they must decide who does what, avoid getting in each other's way and share what they learn. This lesson covers the structure of multi-robot task allocation problems, optimal assignment with the Hungarian algorithm, market-based and auction methods, routing several robots through many tasks, coordinating paths and sharing maps. Lesson 10 turns to swarms, where coordination emerges from simple local rules rather than explicit allocation.

Why teams, and what makes them hard

Teams offer speed through parallelism, robustness through redundancy (lesson 1's k-out-of-n reasoning), and capability through heterogeneity, for example a drone that scouts and a ground robot that carries a heavy sensor. They also introduce new problems. Allocation decides which robot performs which task and in what order. Coordination prevents conflicts, such as two robots trying to use the same narrow passage or charging station. Communication is limited in range, bandwidth and reliability, so robots may have different and outdated information. Scalability matters because methods that work for three robots may be impractical for fifty. Finally, the team's objective must be chosen carefully: minimizing the total distance traveled by all robots and minimizing the time until the last task is done (the makespan) can lead to very different plans.

Gerkey and Matarić proposed a widely used taxonomy of multi-robot task allocation (MRTA) along three axes. Single-task robots (ST) can do one task at a time, while multi-task robots (MT) can do several at once. Single-robot tasks (SR) need one robot, while multi-robot tasks (MR) need several working together, such as carrying a large object. Instantaneous assignment (IA) allocates tasks using only current information, while time-extended assignment (TA) plans a schedule of future tasks for each robot. The simplest class, ST-SR-IA, is the classical assignment problem and can be solved optimally in polynomial time; most other classes are NP-hard and need heuristics.

Optimal assignment: the Hungarian algorithm

When there are \( n \) robots and \( n \) tasks and each robot can take exactly one task, the problem is to choose a one-to-one assignment minimizing the total cost, for example travel distance or time. With a cost matrix \( C \) where \( C_{ij} \) is the cost for robot \( i \) to perform task \( j \), we choose binary variables \( x_{ij} \) to

The Hungarian algorithm, developed by Kuhn in 1955 from earlier work by Hungarian mathematicians, solves this exactly in \( O(n^3) \) time. It works by subtracting row and column minimums to create zeros, then finding the maximum set of independent zeros and adjusting the matrix until a complete assignment of zeros exists. Rectangular problems with more tasks than robots, or the reverse, are handled by padding with dummy rows or columns. Library implementations such as linear_sum_assignment in SciPy make this practical for hundreds of robots.

# Optimal versus greedy assignment of robots to tasks
import numpy as np
from scipy.optimize import linear_sum_assignment
rng = np.random.default_rng(9)
def compare(n, trials=200):
    gaps = []
    for _ in range(trials):
        robots, tasks = rng.uniform(0, 1000, (n, 2)), rng.uniform(0, 1000, (n, 2))
        C = np.linalg.norm(robots[:, None, :] - tasks[None, :, :], axis=2)
        r, c = linear_sum_assignment(C)
        opt = C[r, c].sum()
        free_r, free_t, greedy = set(range(n)), set(range(n)), 0.0
        while free_r:                    # repeatedly take the cheapest remaining pair
            i, j = min(((i, j) for i in free_r for j in free_t), key=lambda p: C[p])
            greedy += C[i, j]; free_r.remove(i); free_t.remove(j)
        gaps.append(greedy / opt - 1)
    return np.mean(gaps), np.max(gaps)
for n in (5, 10, 20, 40):
    mean_gap, worst = compare(n)
    print(f"{n:3d} robots: greedy is {mean_gap:5.1%} worse on average, {worst:5.1%} in the worst trial")

  5 robots: greedy is  7.8% worse on average, 47.8% in the worst trial
 10 robots: greedy is 11.2% worse on average, 40.3% in the worst trial
 20 robots: greedy is 15.2% worse on average, 37.2% in the worst trial
 40 robots: greedy is 18.3% worse on average, 36.0% in the worst trial

Greedy assignment is simple and often reasonable, but in this simulation it is 8 to 18 percent worse than optimal on average, and up to nearly 50 percent worse in unlucky cases, because an early cheap choice can force expensive later ones. When the cost matrix can be computed centrally, there is little reason not to use the optimal algorithm.

Market-based allocation and auctions

Centralized optimization needs a reliable link from every robot to a planner that knows all costs. In the field, links fail, robots discover new tasks, and conditions change, so decentralized methods are attractive. Market-based approaches treat tasks as goods and robots as bidders. In a single-item auction, an auctioneer, which may be any robot, announces a task; each robot computes its cost to add the task to its plan and bids; the lowest bidder wins. Sequential single-item auctions allocate tasks one at a time, each robot bidding its marginal cost given the tasks it already holds, which naturally handles time-extended problems. Combinatorial auctions let robots bid on bundles of tasks, capturing synergies such as two tasks being close together, at higher computational cost.

Auction methods are robust and simple: if a robot fails, its tasks can be re-auctioned, and new tasks can be auctioned as they appear. They are not generally optimal, but for some objectives their solutions come with performance guarantees relative to optimal. The consensus-based bundle algorithm (CBBA) combines bundle construction with a consensus phase in which robots exchange winning bids with neighbors until they agree, so it works without a central auctioneer and converges to a conflict-free assignment with guaranteed performance under some conditions. Practical systems often use auctions for initial allocation and repair, and local optimization to improve each robot's route.

# Sequential single-item auction for time-extended allocation (each robot builds a route)
import numpy as np
rng = np.random.default_rng(12)
depots = np.array([[0, 0], [1000, 0], [500, 900]], float)       # three robots start here
tasks = rng.uniform(0, 1000, (15, 2))
def route_cost(start, pts):
    pos, total = start, 0.0
    for p in pts:
        total += np.linalg.norm(p - pos); pos = p
    return total
def best_insertion(start, route, t):
    best = (np.inf, 0)
    for k in range(len(route) + 1):
        new = route[:k] + [t] + route[k:]
        best = min(best, (route_cost(start, [tasks[i] for i in new]) -
                          route_cost(start, [tasks[i] for i in route]), k))
    return best
def auction(objective):
    routes = [[] for _ in depots]
    for t in range(len(tasks)):                 # announce tasks one at a time
        bids = []
        for r, start in enumerate(depots):
            inc, k = best_insertion(start, routes[r], t)
            current = route_cost(start, [tasks[i] for i in routes[r]])
            bid = inc if objective == "total" else current + inc     # minmax: bid resulting route length
            bids.append((bid, r, k))
        bid, r, k = min(bids)
        routes[r].insert(k, t)
    lengths = [route_cost(s, [tasks[i] for i in rt]) for s, rt in zip(depots, routes)]
    return routes, lengths
for objective in ("total", "minmax"):
    routes, lengths = auction(objective)
    print(f"{objective:6s} bids: tasks per robot {[len(r) for r in routes]}, route lengths "
          f"{[round(x) for x in lengths]} m, total {sum(lengths):.0f} m, makespan {max(lengths):.0f} m")

total  bids: tasks per robot [8, 0, 7], route lengths [1845, 0, 1387] m, total 3231 m, makespan 1845 m
minmax bids: tasks per robot [4, 4, 7], route lengths [1086, 951, 1387] m, total 3424 m, makespan 1387 m

The choice of bidding rule changes the result. Bidding marginal cost tends to minimize total distance but may load well-placed robots with most of the work, and here it leaves the second robot idle; bidding the resulting route length balances the work and shortens the makespan, usually at the cost of more total distance. Which is better depends on the mission: total distance matters for energy and wear, while makespan matters when a weather window or a search for survivors sets a deadline.

Routing teams through many tasks

Time-extended allocation for many tasks resembles the multiple traveling salesman problem (mTSP) and vehicle routing problems from operations research. Each robot starts at a depot, visits a subset of tasks and may return to recharge; constraints can include battery capacity, time windows, task precedence and robot capabilities. Exact solutions with mixed-integer programming are feasible for small problems; field systems typically use heuristics such as insertion, savings algorithms and local search (two-opt and moves of tasks between robots), or metaheuristics such as large neighborhood search, with solvers re-run as conditions change. Energy constraints are especially important for field robots: a drone fleet surveying power lines must plan battery swaps, and an agricultural fleet must schedule returns to refill and recharge.

Coordinating paths and shared resources

Robots that each follow good individual plans may still collide, block narrow passages or queue at a single charging station. Multi-agent path finding (MAPF) computes collision-free paths for many agents on a graph. Prioritized planning plans robots one at a time, treating earlier robots' paths as moving obstacles; it is fast but can fail when a low-priority robot is boxed in. Conflict-based search finds optimal solutions by planning individually, detecting conflicts and branching on constraints that resolve them, and its bounded-suboptimal variants scale to hundreds of agents. In open fields, coordination is often simpler: robots are given separate areas or lanes, and traffic rules at headlands, gates and charging stations prevent conflicts. ROB-350 covered single-robot planning; MAPF builds on the same graph search ideas.

Sharing information: maps and beliefs

A team is more than the sum of its robots only if they share what they learn. Multi-robot SLAM merges maps from several robots, which requires finding the relative transformation between their maps from shared observations or rendezvous; ROB-340 introduced the graph-based formulations that extend naturally to inter-robot loop closures. Bandwidth limits mean robots often exchange compressed submaps, keyframe descriptors or object-level summaries rather than raw scans. Robots must also handle inconsistent or outdated information about task status: two robots may both believe a task is free and travel to it. Systems use acknowledgments, task locks, timeouts and periodic re-synchronization, and they plan for robots to reconnect after hours out of range, as lesson 11 discusses.

The DARPA Subterranean Challenge provided a demanding test. Teams deployed several ground robots and drones into unknown underground environments, with a single human supervisor and communication available only near the entrance or through radios dropped by the robots as they advanced. Successful teams combined autonomous exploration with frontier-based task allocation, map merging when robots came back into contact, and a supervisor who could reassign robots. Their experience shows that multi-robot coordination in the field is as much about resilient information sharing as about optimal allocation.