robotics//fleet//task allocation
Task allocation is the problem of deciding which agent of a fleet performs which task (which drone inspects which tower, which robot takes which order), and in its distributed form, solving it without any single agent seeing the whole table of agent-task values. With a server it is an assignment problem solved centrally; without one, the standard tool is the auction.
Task allocation is the problem of deciding which agent of a fleet performs which task (which drone inspects which tower, which robot takes which order), and in its distributed form, solving it without any single agent seeing the whole table of agent-task values. With a server it is an assignment problem solved centrally; without one, the standard tool is the auction.
Auctions borrow a market idea. Each task has a price, each agent bids for the task worth most to it once the price is subtracted, and prices rise until no two agents want the same task. In Bertsekas's auction algorithm, agent iii values task jjj at aija_{ij}aij, picks the task with the largest net value aij−pja_{ij}-p_jaij−pj, and raises its price by the gap between its best and second-best net values plus a small ε>0\varepsilon>0ε>0 that prevents endless ties. The result is within NεN\varepsilonNε of the optimum, and exact with integer values and ε<1/N\varepsilon<1/Nε<1/N. Each agent needs only its own values and the current prices, which spread through the fleet by max-consensus in as many rounds as the graph's diameter (consensus protocol).
Auctions share out work without a server; with a server, the Hungarian method or a greedy rule is enough.
SciPy's linear_sum_assignment solves a 1,000 by 1,000 problem in under a second on a laptop (Hungarian algorithm), and under light load the new task goes to the nearest free robot works surprisingly well (greedy algorithm). Distributed auctions earn their complexity when there is no server; reluctance to set one up is a poor reason.
When each agent does several tasks in a row (five towers to inspect in one sortie), order matters. The consensus-based bundle algorithm (CBBA; Choi, Brunet and How, 2009) alternates two phases: each agent greedily fills its bundle with the tasks that most increase its value, then neighbours resolve conflicts by keeping the highest bid, and an agent that loses a task also releases those it added after it. It converges without conflicts, tolerates agents seeing the world somewhat differently and, when the marginal value of tasks diminishes (submodular function), guarantees at least half the optimum. The auction is a foundation; CBBA and its variants are mostly research.
The failure this machinery prevents is the inconsistent view of communication constraints: two robots that each believe a task is theirs. Whether to distribute at all is fleet architecture.
Estimating together has its own trap. When drones exchange estimates, the hard part is avoiding counting the same information twice, which shrinks the covariance without any new measurement (covariance intersection, distributed Kalman filter).