Distributed Task Allocation

"A task was auctioned to the agent who wanted it least reluctantly. I bid my distance, lost to a closer rotor, and discovered I had been free all along."

An Agent That Bid Too High

In Section 39.2 the robots learned to hold formation and avoid collisions, treating coordination as a problem of motion. But a swarm is deployed to accomplish work: survey these twelve regions, deliver to those eight addresses, inspect each of these turbines. The work arrives as a set of tasks, and the team's effectiveness is decided long before any motor turns, at the moment each task is matched to an agent. That matching is the subject here. On a single machine it is a textbook assignment problem with a clean optimal solution. The difficulty, and the reason it belongs in this book, is that the team has no single machine: each robot knows its own position and capabilities, sees only its neighbors, and must arrive at a coherent team-wide assignment through local negotiation. The allocation is itself distributed, and the central thread of this section is that local bidding plus agreement can approximate a global optimum that no agent could compute alone.

1. The Multi-Robot Task-Allocation Problem Beginner

Multi-robot task allocation (MRTA) asks how to assign a set of tasks to a team of robots so that some team objective, usually total cost or total reward, is optimized, subject to each robot's capabilities and the structure of the tasks. The problem is so pervasive that it has a standard taxonomy, due to Gerkey and Mataric, along three binary axes. The first axis is single-task versus multi-task robots: can a robot work on one task at a time, or several at once? The second is single-robot versus multi-robot tasks: does a task need exactly one robot, or a coalition? The third is instantaneous versus time-extended assignment: do we assign the tasks available right now, or plan a schedule of future tasks per robot? The simplest and most studied corner, single-task robots, single-robot tasks, instantaneous assignment, is exactly the assignment problem, and it is where we anchor the theory before relaxing toward the realistic time-extended case.

Each axis multiplies the difficulty. Instantaneous single-assignment is solvable optimally in polynomial time, as the next subsection shows. The time-extended case, where each robot is given an ordered bundle of tasks to perform in sequence, is NP-hard, because the cost of adding a task to a robot depends on the other tasks already in its bundle and on their order. This is the same combinatorial explosion that makes cluster job-packing hard in Chapter 33, and it is why the realistic algorithms later in this section are greedy heuristics with provable guarantees rather than exact solvers. Table 39.3.1 lays out the taxonomy and where each cell is treated.

2. The Centralized Optimum as a Yardstick Intermediate

To judge any decentralized scheme we need the best possible answer to compare against, and for the simplest corner of the taxonomy that answer is computable exactly. Suppose there are $n$ agents and $n$ tasks, and let $c_{ij}$ be the cost for agent $i$ to perform task $j$, for instance the distance it must travel. An assignment is a permutation that pairs each agent with one task, encoded by binary variables $x_{ij} \in \{0, 1\}$ where $x_{ij} = 1$ means agent $i$ is assigned task $j$. The linear assignment problem minimizes total cost subject to each agent and each task being used exactly once,

Although the variables are binary, this problem has the remarkable property that its linear relaxation has integer optimal vertices, so it is solvable in polynomial time. The Hungarian algorithm of Kuhn and Munkres solves it in $O(n^3)$ time by manipulating the cost matrix until a zero-cost perfect matching appears in the reduced costs. It is the centralized optimum: a single process that holds the entire matrix $C = [c_{ij}]$ can compute the cost-minimizing assignment outright. The catch is precisely that it needs the entire matrix in one place. In our swarm, row $i$ lives on robot $i$ and no robot holds the whole matrix, so the Hungarian solution is a yardstick we measure against, not a procedure the team can run. It plays the same role here that the single-machine gradient played in Section 1.1: the exact centralized answer that the distributed method must approximate or match.

3. Decentralized Allocation by Auction Intermediate

Markets allocate scarce resources without a central planner, and a robot team can borrow the mechanism directly. In an auction-based allocation, each task is an item up for bid and each robot bids on the tasks it can do, using its own private cost. The bid that a self-interested agent should place is the marginal value of winning the task, the improvement to its own objective from adding that task to its current load. For a robot at position $p_i$ bidding on task $j$ at location $q_j$, the natural bid in the instantaneous single-task case is simply the negative travel cost, so that a closer robot bids higher,

The auction runs in rounds. Every unassigned robot announces a bid on its currently most attractive free task; for each task, the highest bid wins and that robot-task pair is fixed; the losers return to the next round and bid again on what remains. This is the auction algorithm of Bertsekas, and it is genuinely distributed: a bid is a local computation on private cost, and the only thing that crosses the network is the small message "I bid $b$ on task $j$." It connects directly to the negotiation and auction protocols of Chapter 29, where the Contract Net protocol casts task allocation as announce, bid, and award between agents. Figure 39.3.1 traces one round: agents broadcast bids, the conflict over a contested task is resolved in favor of the lowest cost, and a conflict-free assignment emerges.

For the time-extended corner of the taxonomy, where each robot is awarded an ordered bundle of tasks rather than a single one, the standard decentralized method is the consensus-based bundle algorithm (CBBA) of Choi, Brunet, and How. CBBA interleaves two phases that repeat until the team agrees. In the bundle-building phase, each robot greedily adds the task with the highest marginal score to its bundle, where the marginal score of inserting task $j$ accounts for where it best fits in the robot's existing route. In the consensus phase, robots exchange their winning-bid vectors with neighbors and apply deterministic conflict-resolution rules, so that whenever two robots claim the same task, the one with the higher bid keeps it and the loser releases it and any tasks it had added afterward. The marginal-score bid that robot $i$ places when inserting task $j$ at the best position in its current bundle $\mathcal{B}_i$ is

where $S_i$ is robot $i$'s reward for completing its bundle and $\oplus_k$ inserts $j$ at position $k$ in the route. CBBA provably converges to a conflict-free assignment within a bounded number of communication rounds on a connected network, and the result is within a constant factor of the optimal team reward when the scoring function is submodular, meaning each added task helps less the more a robot already has. The consensus phase is doing exactly the conflict-resolution work that Chapter 2 formalizes: agents must agree on a single consistent value (who owns each task) despite each starting from its own local view.

4. Response Thresholds: Allocation Without Bidding Intermediate

Auctions assume robots can exchange bids and run rounds of negotiation. A larger or more communication-starved swarm may not afford even that, and biology suggests a lighter mechanism. Social insects allocate labor with no negotiation at all, through response thresholds: each individual has a private threshold for each kind of task, and it engages a task only when the local stimulus for that task exceeds its threshold. As idle agents take on work, the stimulus falls; as work piles up, the stimulus rises until even high-threshold agents respond. This produces a stable division of labor with no messages exchanged, a mechanism developed in full in Chapter 31. The probability that an agent with threshold $\theta$ engages a task whose stimulus is $s$ follows the response-threshold function

so an agent almost ignores tasks whose stimulus is well below its threshold and almost certainly engages those well above it. Heterogeneous thresholds across the team yield specialization for free: low-threshold agents become the first responders for a task type, high-threshold agents the reserves that activate only under heavy demand. The trade-off against auctions is sharp. Threshold allocation needs no communication and degrades gracefully as the swarm grows, but it cannot guarantee the near-optimal global cost that bidding achieves, because no agent ever compares its cost against another's. The right mechanism depends on the regime: auctions when bandwidth permits and optimality matters, thresholds when the swarm is too large or too silent to bid.

5. Dynamic Reallocation Under Failure and Arrival Advanced

A static assignment computed once is a fiction in the field. Robots fail, batteries deplete, new tasks appear, and obstacles render a planned task unreachable. Distributed allocation earns its complexity precisely because it reallocates gracefully under these disturbances. When a robot drops out, its tasks become unclaimed; in the auction and CBBA formulations this is handled by the same machinery that built the assignment, because a released task simply re-enters the market and the remaining robots bid on it in the next round. When a new task arrives, it is announced to the team and folded into the next bundle-building phase. The decentralized structure that made allocation possible also makes it self-healing: there is no central assignment table to repair, only a fresh round of local bidding and consensus. This is the multi-robot counterpart of the elastic, fault-tolerant training of Chapter 18, where a worker leaving or joining triggers a re-formation of the group rather than a crash.

The multi-robot-task corner of the taxonomy, where a task needs a coalition rather than a single robot, layers coalition formation on top of bidding: agents bid jointly, and the consensus phase must agree not only on who owns a task but on which group covers it. Even here the principle holds: the team approximates a global optimum it cannot compute centrally by exchanging local bids and resolving conflicts by agreement. The distributed RL infrastructure of Chapter 20 reappears in this case study's training pipeline when the bidding policies themselves are learned rather than hand-designed, closing the loop between the swarm's behavior and the methods of Part IV.

The demonstration below makes the central comparison concrete. It builds a small instance of six agents and six tasks with travel-distance costs, computes the centralized Hungarian optimum as the yardstick, then runs the decentralized auction in which each free agent bids on its cheapest free task and conflicts are resolved by lowest cost, and finally reports the optimality gap. The auction never assembles the full cost matrix in one decision; each agent acts on its own row alone.

import numpy as np
from scipy.optimize import linear_sum_assignment

rng = np.random.default_rng(7)
n = 6  # agents and tasks
agents = rng.uniform(0, 100, size=(n, 2))
tasks = rng.uniform(0, 100, size=(n, 2))

# Cost matrix: c[i, j] = euclidean distance from agent i to task j.
C = np.linalg.norm(agents[:, None, :] - tasks[None, :, :], axis=2)

# Centralized optimum: Hungarian algorithm minimizes total assigned cost.
row, col = linear_sum_assignment(C)
opt_cost = C[row, col].sum()

# Decentralized auction: each unassigned agent bids on its cheapest free task.
# Rounds run until every agent holds one task. No central scheduler picks the
# global optimum; agents act on local cost only, resolving conflicts by lowest bid.
free_agents = list(range(n))
free_tasks = set(range(n))
assign = {}
rounds = 0
while free_agents:
    rounds += 1
    bids = {}  # task -> (cost, agent), keep the lowest-cost claimant
    for a in free_agents:
        j = min(free_tasks, key=lambda t: C[a, t])
        if j not in bids or C[a, j] < bids[j][0]:
            bids[j] = (C[a, j], a)
    for j, (cost, a) in bids.items():
        assign[a] = j
        free_tasks.discard(j)
        free_agents.remove(a)

auction_cost = sum(C[a, j] for a, j in assign.items())
gap = (auction_cost - opt_cost) / opt_cost * 100

print(f"agents/tasks         : {n}")
print(f"hungarian optimum    : {opt_cost:.2f}")
print(f"auction total cost   : {auction_cost:.2f}")
print(f"consensus rounds     : {rounds}")
print(f"optimality gap       : {gap:.2f}%")
print(f"conflict-free        : {len(set(assign.values())) == n}")

agents/tasks         : 6
hungarian optimum    : 169.46
auction total cost   : 193.91
consensus rounds     : 2
optimality gap       : 14.43%
conflict-free        : True

from scipy.optimize import linear_sum_assignment
row, col = linear_sum_assignment(C)        # optimal agent->task matching
optimal_total = C[row, col].sum()          # the cost no decentralized scheme can beat

6. When to Decentralize the Allocation Advanced

The optimality gap in Output 39.3.1 is not a defect to be apologized for; it is a deliberate trade. A central scheduler that gathers every cost and runs the Hungarian algorithm achieves the optimum, but it requires every robot to report to one place, makes that place a bottleneck and a single point of failure, and stops working the moment the network partitions. Decentralized allocation accepts a bounded loss of optimality in exchange for needing only neighbor-to-neighbor communication, surviving the loss of any agent, and scaling to teams far larger than a central solver could coordinate in real time. The decision mirrors the one in Chapter 33: a datacenter with reliable links and a trustworthy controller schedules centrally and reaps the optimum, while a field swarm with intermittent links and expendable members allocates locally and accepts the gap. The same problem, two answers, chosen by which constraint binds.

We now have the matching of agents to work as a distributed computation: a taxonomy that locates the problem, a centralized optimum that bounds the best case, and market, consensus, and threshold mechanisms that approximate it with only local information while reallocating gracefully as the team changes. The team can coordinate motion and divide labor; both rest on agents exchanging headings and bids, and what remains is to confront the range-limited, lossy radio that those messages actually cross. That is the subject of Section 39.4.