cs.ROAug 16, 2026

Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems

Authors: Jose Rodriguez, Sven Koenig, Wenjie Dong, Qi Lu

Organizations: The University of Texas at Rio Grande Valley, Edinburg, Texas 78539, USA · University of California, Irvine, CA 92697, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: The optimal solution for 10 robots and 25 tasks in simulation
Figure 2: Percent optimality comparison between CBBA and GACA at varying robot team sizes.
Figure 3: Convergence speed comparison between CBBA and GACA at varying robot team sizes (communication cycles until convergence).
Figure 4: Mean percent optimality across the variety dataset, averaged over five world configurations per cell. Greener cells indicate higher optimality relative to the MILP ground truth.
Figure 5: Mean convergence iterations across the variety dataset, averaged over five world configurations per cell. Darker red indicates higher iteration counts.

Explore similar work

CardsList

  1. Auction-Consensus Algorithm with Learned Bidding Scheme for Multi-Robot Systems

    May 21, 2026Jose Rodriguez, Constantine Tarawneh, Sven Koenig +2Multi-Robot CoordinationMulti-Robot Task Allocation

    Department of Electrical and Computer Engineering, The University of Texas at Rio Grande Valley (UTRGV), Edinburg, USA · Department of Mechanical Engineering, UTRGV, Edinburg, TX, USA · Department of Computer Science, Donald Bren School of Information and Computer Sciences, University of California, Irvine +1

  2. Decentralized Multi-Robot Task Allocation Under Degraded Communication: A Benchmark of Performance, Reliability, and Computation

    Sep 12, 2026James Lott, Vahraz HonaryMulti-Robot Task Allocation

    Department of Electrical Engineering, University of San Diego, San Diego, CA 92110 USA

  3. Varying Bundle Size Reactive Multi-Task Assignment using Selective Cost Estimation for Multi-Agent Systems

    Jun 23, 2026Niklas Dahlquist, Shridhar Velhal, George NikolakopoulosMulti-Fidelity OptimizationMulti-Robot Task Allocation

    Luleå University of Technology, Luleå, SE-971 87 Sweden