Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces the Grouping Auction-Consensus Algorithm (GACA), a novel decentralized framework for multi-robot task allocation that enhances the Consensus-Based Bundle Algorithm (CBBA) by redesigning its bidding mechanism to focus on groups of spatially proximate tasks. By implementing a nearest-neighbor preprocessing step, GACA allows agents to propose structured group-level actions, leading to significantly improved allocation efficiency. Experimental results demonstrate that GACA achieves a median percent optimality of approximately 97%, outperforming CBBA's 81-84% across various swarm sizes and problem configurations, while also converging in equal or fewer iterations.
GACA redefines multi-robot task allocation by optimizing group-level bidding, achieving nearly perfect allocation efficiency in decentralized systems.
Decentralized multi-robot task allocation (MRTA) is essential for scalable and resilient autonomous systems. The Consensus-Based Bundle Algorithm (CBBA) is a widely adopted decentralized baseline. However, its individual task-level bidding is poorly aligned with the min-sum objective of minimizing total team travel distance, leading to suboptimal allocations in spatially distributed environments. This paper introduces the Grouping Auction-Consensus Algorithm (GACA). This decentralized MRTA framework adopts the two-phase auction-consensus architecture of CBBA while fundamentally redesigning its bidding mechanism to reason over groups of spatially proximate tasks. A nearest-neighbor preprocessing step partitions tasks into spatially coherent groups before allocation. Agents then iteratively propose structured group-level actions: claiming unassigned groups, acquiring partial groups, or contesting groups held by other agents. Competing actions are resolved through a consensus phase. Operating in the MT-SR-IA problem class, GACA is evaluated against CBBA using a Mixed-Integer Linear Program as the ground-truth optimality reference. Across four swarm sizes and 4,000 test worlds, GACA achieves a median percent optimality of approximately 97% compared to 81--84% for CBBA, while converging in equal or fewer iterations. A scalability evaluation over 3,280 additional problem instances spanning swarm sizes of 5 to 20 agents and task counts of 10 to 50 confirms that these gains generalize robustly across a wide range of problem configurations.