Collaborative Task Allocation for Heterogeneous Multi-Robot Systems through Iterative Clustering
David R. Martin, Brooks A. Butler, Scott Nivison, Magnus Egerstedt, Mohammad Abdullah Al Faruque, Pramod Khargonekar
AI summary
Problem
Existing multi-robot task allocation methods struggle to model collaborative synergy and variable team sizes, making the global optimization problem computationally intractable for large heterogeneous systems.
Approach
The method partitions the intractable global problem into smaller subproblems by iteratively clustering robots and tasks, then optimizing assignments within each cluster while keeping currently assigned robots together.
Key results
- Guarantees monotonic utility improvement across iterations
- Achieves 99.9% of optimal utility on small-scale problems
- Outperforms simulated annealing, auctions, and hedonic games in speed and quality
- Scales to problems with up to 1000 robots and 500 tasks
Why it matters
Enables efficient, scalable coordination for real-world multi-robot applications like disaster response and construction where team synergy is critical.
Abstract
Multi-robot systems face the challenge of efficiently allocating teams of heterogeneous robots to tasks. The task alloca- tion 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 impos- sible 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 subopti- mal 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.