CS Paper Radar

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

Jose Rodriguez, Sven Koenig, Wenjie Dong, Qi Lu

cs.RO ·submitted 2026-08-16 18:17 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Collaborative Task Allocation for Heterogeneous Multi-Robot Systems Through Iterative Clustering

cs.RO ·2026-11-12 ·David R. Martin, Brooks A. Butler, Scott Nivison, Magnus Egerstedt, Mohammad Abdullah Al Faruque +1 more
top venuehighly cited similarity 0.68
Abstract · 8 pages, 4 figures, Published in IEEE Robotics and Automation Letters (RA-L) and presented at 2026 IEEE International Conference on Robotics…

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.

0.59

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

cs.RO ·2026-09-12 ·James Lott, Vahraz Honary
benchmark similarity 0.66
Abstract

Selecting a decentralized Multi-Robot Task Allocation (MRTA) method for embedded deployment on autonomous platforms requires considering more than route performance alone. We benchmark six decentralized MRTA allocators (CBAA, ACBBA, PI, HIPC, DMCHBA, and DGA) in the Collaborative Visit (CV) scenario to characterize tradeoffs among MinMax and MinSum travel, communication robustness and demand, allocation reliability, computational burden, and scale sensitivity. The core study uses 500 paired ten-target instances across 25 ideal and degraded communication conditions spanning Bernoulli loss, Gilbert--Elliott loss, and Rayleigh fading, with additional campaigns examining pre-allocation, execution-integrated computation, and sensitivity to grid size, robot density, and target load. Across the 24 impaired core conditions, DGA and DMCHBA achieved the lowest mean MinMax travel at 24.49 and 24.78 steps, respectively. HIPC narrowly led mean MinSum travel at 66.95 steps, followed by DGA at 67.22, with both methods occupying the top two in every impaired condition. DMCHBA had the lowest publication intensity at 2.08 publications per team step. In ten-target pre-allocation, HIPC and DMCHBA remained viable and stable in every tested condition, while ACBBA, PI, and DGA lost stability or viability as communication degraded. Under ideal delivery, median full-protocol computation $\Cterm$ in the primary ten-target comparison ranged from 4.88 ms for DMCHBA to 1.346 s for DGA. Static route quality preserved DGA and DMCHBA as the leading MinMax methods, while DGA led MinSum at three of four target loads and HIPC led at 50 targets. Static and execution-integrated computation rankings diverged as task load increased. The results identify distinct allocator operating regions across route objective, communication behavior, reliability, and computational constraints.

0.41

AssemblyGrid v1: A Benchmark for Multi-Robot Production with Temporary Coalitions, Local Information, and Geometric Constraints

cs.RO cs.AI ·2026-09-13 ·Fouad Bahrpeyma, David Heik, Dirk Reichelt
benchmarkcode/data similarity 0.65
Abstract · 11 figures and 23 tables, including appendices with the formal benchmark specification, evaluation protocol, conformance requirements, and e…

Flexible robotic production requires joint decisions on process progression, material routing, resource assignment, temporary cooperation, and simultaneous execution, since each decision can affect the feasibility of the others. The challenge is greater under decentralized control, where each robot acts from bounded local information while system progress depends on collective decisions, shared resources, material state, and workspace compatibility. These properties closely match cooperative multi-agent decision making under partial observability and resource contention. This paper introduces AssemblyGrid v1, a reproducible benchmark for repeated multi-robot production that combines explicit process progression, decentralized observations, material transfer, temporary multi-robot coalitions, productive concurrency, and geometry-dependent feasibility within one task-level formulation. The benchmark includes Flow, Coalition, and Concurrency workload families, each with three scenario levels. Task success and evaluation measures are defined independently of learning reward and solution method, allowing learning-based and non-learning methods to address the same production problem. AssemblyGrid v1 is evaluated through executable conformance checks, mechanism studies, and algorithmic experiments using a privileged centralized reference, structured decentralized controllers, and MARL methods including IPPO, MAPPO, and QMIX. Results demonstrate productive execution under centralized and decentralized control. The MARL experiments further show that decentralized policies can learn effective production behavior from local observations and actions, supporting AssemblyGrid as a controlled benchmark for studying cooperative decision making in flexible robotic production.

0.32

Dispersive Tree Agreements for Multi-Robot Coordination

cs.RO cs.MAmath.OC ·2026-10-22 ·Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How
similarity 0.65
Abstract · 18 pages, 5 figures, 7 tables

Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to joint constraints. Existing methods that approach joint optimality remain largely centralized and offline, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by a negotiation driven by decentralized column generation. In the quiescent limit, this negotiation is shown to settle on a near-optimal agreement. Our real-time protocol, WarpWeaver, runs the negotiation asynchronously over a receding horizon and closes on quiesced agreements even when deadlines cut it short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 16% against a decentralized real-time baseline, and outperforms a task-specific planner on networked navigation. Hardware experiments on six robots planning onboard demonstrate real-world implementability.

0.16

Distributed Marginal Return: A Communication-Efficient Algorithm for Multi-Agent Weapon Target Assignment

cs.MA ·2026-11-03 ·Kamal Mammadov, Glen Pearce, Helen Krause, Damith C. Ranasinghe
published similarity 0.65
Abstract · 12 pages, 6 figures. Published in the IEEE Systems Journal

The Weapon-Target Assignment (WTA) problem in distributed multi-agent systems is challenged by limited situational awareness and communication constraints. Existing distributed methods, such as auction-consensus algorithms, typically assume task-value independence, a simplification that fails to capture the coupled effects of multi-weapon assignments. This paper introduces the Distributed Marginal Return (DMR) algorithm, a novel decentralized approach that generalizes auction-consensus frameworks. DMR enables agents to compute bids based on marginal return and uses a consensus protocol to resolve conflicts, allowing multiple non-conflicting proposals to be accepted in parallel for cooperative optimization with minimal communication. A key theoretical contribution is our proof that the marginal returns of non-conflicting bids are additive, a property that ensures global consistency and validates our parallel acceptance mechanism. Extensive simulations demonstrate that DMR significantly outperforms baseline algorithms in both solution quality and communication efficiency, offering a scalable and robust solution for real-world distributed command and control applications.

0.31

Pass the Bucket: Efficient, Robust, Local Load Balancing for Teams of Heterogeneous Robots

cs.RO ·2026-08-27 ·Tobias Wallner, Dominik Krupke, Arne Schmidt, Sándor P. Fekete
similarity 0.62
Abstract · This paper was submitted to IROS 2026 on March 2nd and accepted on June 17th

We study the problem of decentralized, self-organized task sharing for a swarm of heterogeneous robots that collaborate in transportation or other objectives that require coordinated motion planning. To this end, we present theoretical and practical results for the simple but effective mechanism of \emph{bucket brigades} for load balancing, in which a team of heterogenous robots share a spatial task in a confined, one-dimensional space, while only being able to sense collisions with neighbors or walls. The goal is to optimize throughput of the overall system, without central control or information, aiming at an interval partition proportional to robot velocities. We address possible chaotic system behavior by developing a stabilization mechanism based on simple local aid, a ``token'', that temporarily decelerates robots after an encounter. This purely local change eliminates persistent oscillations, resulting in convergence towards a stable system state. We accelerate system convergence by comparing a single boundary token to ubiquitous two-directional tokens and optimizing the deceleration factor. Event-driven simulations report convergence times and robustness: For a large variety of perturbations (such as robot deletion, position or velocity jittering), the system reliably re-converges. The results suggest a local, practical mechanism for robust load balancing for heterogeneous teams of robots that promises an effective tool as basis for more complex scenarios.

0.30

Facultative Swarming: A Capability, Not a Category, for Multi-Robot Systems

cs.RO ·2026-10-23 ·Ning Zhou, Edmund R. Hunt
similarity 0.61
Abstract

Collective robotics is split by a long-standing but increasingly artificial boundary between centralised multi-robot systems that prioritise optimality and decentralised swarms that prioritise robustness and adaptivity. We propose a unified control framework, shifting from `obligate' swarms---systems constrained to pure self-organisation---to facultatively swarming systems: hybrid architectures that operate as centrally planned systems under permissive conditions yet degrade gracefully into decentralised swarming under environmental stress. By reframing swarming as a dynamic capability, rather than a rigid system category, we outline a pathway towards collective robotic systems that benefit from centralised optimality when conditions permit and from the flexibility of self-organisation when they do not.

0.28

AC-DC: Adaptive Communication for Scalable Dynamic Average Consensus in Multi-Robot Ergodic Search

cs.RO ·2026-09-21 ·Robin Inho Kee, Begum Cannataro, Vasileios Tzoumas
similarity 0.60
Abstract · 9 pages, 3 figures

We study scalable peer-to-peer dynamic average consensus (DC) for multi-robot systems under finite-range, finite-rate, and interference-constrained communication. We introduce Adaptive Communication for Dynamic Average Consensus (AC-DC), which jointly adapts Who communicates with whom, When, and over What parts of the consensus state, using local inputs and successfully received neighbor information. Each robot's consensus state estimates the current average of the robots' local inputs. AC-DC updates these estimates as local inputs change and averages the values exchanged between robot pairs. In AC-DC, robot pairs update without waiting for every robot to complete a communication round, and the selected-state messages carry consensus state coordinates independent of team size for a fixed state representation. We apply AC-DC to dynamic-priority multi-robot ergodic search: one consensus stream estimates team visitation for motion coordination, while the other fuses regional measurement information to update uncertainty maps and search targets. Across twelve settings with up to 80 robots and 20 paired trials per setting, AC-DC has the lowest mean (i) normalized covariance-trace area under the curve (AUC) and (ii) attempted modeled communication payload among the compared decentralized methods. Averaged across settings, AC-DC achieves paired AUC reductions of 27.5% relative to state-of-the-art baselines, with 8.7x less communication traffic. As the number of robots increases, we observe that AC-DC's communication payload approaches that of the ideal centralized baseline (one ground compute-station communicating directly with all robots): with 120 robots in a fixed 600 x 600 m scaling test, AC-DC uses 19.3 MB versus 19.2 MB for the ideal centralized baseline, while remaining peer-to-peer.

0.24