Collaborative Task Allocation for Heterogeneous Multi-Robot Systems Through Iterative Clustering
Organizations: Henry Samueli School of Engineering, Department of Electrical Engineering and Computer Science, University of California, Irvine. · Air Force Research Laboratory, Munitions Directorate, Eglin AFB, FL.
Abstract
Multi-robot systems face the challenge of efficiently allocating teams of heterogeneous robots to tasks. The task allocation problem is complicated by collaborative interactions between robots where teams of robots develop emergent capabilities that enable them to complete tasks that would be inefficient or impossible for individual robots. To address these challenges, we present an iterative clustering algorithm for collaborative task allocation in heterogeneous multi-robot systems. This approach partitions the computationally intractable global optimization problem into smaller, tractable subproblems by iteratively forming clusters of robots and tasks, then optimizing assignments within each cluster. By ensuring robots remain clustered with their currently assigned tasks, we guarantee monotonic improvement in overall utility with each iteration. We analyze the convergence of the algorithm and characterize how cluster size constraints determine which suboptimal assignments could trap the algorithm. In simulation, iterative clustering consistently outperforms simulated annealing, and a group-based auction in both computation time and solution quality, and outperforms a hedonic game approach in solution quality.
Figures & tables
| Method | Exact Optimal Matches (%) | Average Utility Ratio (%) |
|---|---|---|
| Random | 99.6 | 99.9 |
| Heuristic | 99.0 | 99.9 |
| Method | 0.1 seconds | 0.5 seconds | 2 seconds | ||||
|---|---|---|---|---|---|---|---|
| Avg | Avg | Avg | Max | ||||
| HC | 95.2 | 2.6 | 99.4 | 0.5 | 99.6 | 0.4 | 100.0 |
| RC | 87.4 | 3.4 | 99.1 | 0.6 | 99.6 | 0.4 | 100.0 |
| SA | 82.7 | 2.7 | 91.4 | 1.5 | 97.8 | 0.9 | 99.5 |
| GBA | 0.0 | 0.0 | 0.0 | 0.0 | 96.0 | 0.0 | 96.0 |
| HG | 71.7 | 2.8 | 71.7 | 2.8 | 71.7 | 2.8 | 78.1 |
Multi-Robot Task Allocation
Multi-robot task allocation assigns work across robot teams while balancing capabilities, costs, timing, and coordination constraints.
See all 123 papers