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

James Lott; Vahraz Honary

cs.ROSep 12, 2026

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

Authors: James Lott, Vahraz Honary

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

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.

Figures & tables

Dimension	Nayak et al. [ 5 ]	Cao et al. [ 6 ]	This work
Algorithms	CBAA, ACBBA, DHBA, HIPC, PI	CBAA, CBBA, DHBA, HIPC, PI, DGA	CBAA, ACBBA, PI, HIPC, DMCHBA, DGA
Execution	Repeated allocation and communication at a common 0.1-s cadence	Synchronous pre-allocation and periodic asynchronous dynamic allocation	Event-driven mission execution with separate strict-barrier pre-allocation and execution-timing studies
Communication	Bernoulli, Gilbert–Elliott, and Rayleigh fading	Packet loss, bit errors, and one-hop delay	Bernoulli, Gilbert–Elliott, and Rayleigh fading
Design	50 randomized trials per principal condition	100 Monte Carlo trials at two agent–target scales	500 paired core instances per condition with separate paired pre-allocation, execution-timing, and scale-sensitivity campaigns
Outcomes	MinMax travel and maximum-agent messages	MinMax path quality, allocation reliability, payload-aware overhead, and runtime	MinMax and MinSum travel, duplicate work, workload concentration, communication demand, allocation reliability, static and execution-integrated computation, and scale continuity

TABLE I: Comparison with prior Collaborative Visit benchmarks.

Method	Planning scope	Local allocation mechanism	Allocator communication and repair
CBAA [ 13 ]	One current target	Highest locally feasible distance-based bid	Delta winner–bid records, deterministic tie breaking, and rebidding after ownership loss
ACBBA [ 14 ]	Ordered bundle	Marginal route-insertion bids	Timestamped delta deconfliction and release of a lost target with its dependent suffix
PI [ 19 ]	Ordered path	Marginal route significance, with lower significance preferred	Owner, significance, and path records with local removal and rescoring after ownership loss
HIPC [ 20 ]	Local team plan	Greedy planning over the local robot and predictable peers	Path claims, prediction checking, stale-claim cleanup, and neighborhood pruning after repeated mismatch
DMCHBA [ 26 ]	Clone-expanded assignment	Hungarian matching followed by local route ordering	No allocator-specific bid or assignment messages, with allocation reconstructed from locally available team state
DGA [ 28 ]	Complete team plans	Population search with selection, crossover, mutation, repair, and elitism	Changed owner-route information is exchanged and valid received plans enter the local population

TABLE II: Benchmark allocation and communication mechanisms.

Campaign	Algorithms	Conditions	Sampling	Purpose
Asynchronous core	Six	Ten targets under ideal delivery and 24 degraded communication conditions	500 per condition, 112,500 unique simulations	Realized travel, communication, coordination, and degradation response
Synchronous pre-allocation	Five multi-task methods	5, 10, 25, and 50 targets under selected ideal and degraded treatments	50, 100, 50, and 25 per condition, 4,500 trials	Viable and stable allocation, $C_{\mathrm{term}}$ , and achieved route quality
Asynchronous computation	Six	5, 10, 25, and 50 targets under ideal delivery	1,350 primary records plus 675 objective-specific checks	Execution-integrated computation and allocator-call frequency
Scale sensitivity	Six	Grid-size/robot-density sweep and fixed-grid target-load/robot-count sweep	14,400 grid/density simulations plus 3,200 target/team simulations	MinMax and MinSum ranking continuity across scale

TABLE III: Experimental campaigns.

Fig. 1: Collaborative Visit travel across ideal and degraded communication. Panels (a)–(c) show realized MinMax travel

S_{\max}

, and panels (d)–(f) show realized MinSum travel

S_{\Sigma}

. Each objective uses the corresponding algorithm settings. Points are paired-scenario means with 95% bootstrap confidence intervals.

Method	$\boldsymbol{S_{\max}}$	Leads	Top two	$\boldsymbol{M_{\mathrm{step}}}$
CBAA	26.02	0	0	5.19
ACBBA	26.91	0	0	3.71
PI	29.05	0	0	2.48
HIPC	25.12	4	8	2.61
DMCHBA	24.78	2	19	2.08
DGA	24.49	18	21	3.38

TABLE IV: Impaired-condition asynchronous MinMax summary.

Fig. 2: Realized MinMax travel versus publication intensity under ideal delivery and Bernoulli loss at

p_{\mathrm{drop}}=0.20

and

0.40

. Lower values on both axes are preferred. Error bars are 95% paired-scenario bootstrap confidence intervals.

Fig. 3: MinMax communication-degradation summaries. Columns B, GE, and R denote Bernoulli, Gilbert–Elliott, and Rayleigh fading communication. Lower PRDS indicates less within-algorithm degradation. Negative PRDA indicates improving position relative to the six-algorithm field.

Fig. 4: Ten-target pre-allocation reliability across five communication treatments. Panels (a) and (b) report viable and stable allocations, respectively, out of 100 paired attempts.

Method	Viable /100	Stable /100	$\boldsymbol{C_{\mathrm{term}}}$ (ms)	MinMax	MinSum
ACBBA	100	98	86.62	40.0	61.5
PI	97	70	166.06	48.0	56.0
HIPC	100	100	52.65	40.0	51.5
DMCHBA	100	100	4.88	22.5	70.0
DGA	100	100	1345.60	21.0	50.0

TABLE V: Ten-target ideal pre-allocation summary.

Fig. 5: Median full-protocol computation

C_{\mathrm{term}}

. Panel (a) compares ten-target communication treatments, and panel (b) shows ideal-condition scaling with target count. Error bars are 95% bootstrap confidence intervals. The vertical axis is logarithmic.

Fig. 6: Execution-integrated allocator computation under ideal communication using the primary MinMax settings. Panel (a) shows cumulative team allocator time and panel (b) allocator calls per mission across target loads. Error bars are 95% paired-scenario bootstrap confidence intervals.

Fig. 7: Grid-size and robot-density sensitivity of mean realized MinMax travel $S_{\max}$ under ideal communication. Each cell contains ten targets, with $N_{R}=\lceil g^{2}/\delta\rceil$ robots. Annotations report means over retained complete six-algorithm blocks.

Explore similar work

Sep 5, 2026

Bundle Length Tradeoffs in Decentralized Multi-Robot Task Allocation Under Degraded Communications

Bundle length B is commonly fixed when configuring multi-task multi-robot task allocation (MRTA) algorithms. MinSum and MinMax are known to favor different task distributions, but the role of B in this objective tradeoff has not been systematically characterized. Additionally, degraded-communication evaluations also often retain settings selected under ideal communication, leaving whether nominal bundle-length tuning transfers under message loss unresolved. We examine both questions for ACBBA, PI, and HIPC across six bundle lengths in 300 paired ten-target Collaborative Visit scenarios under ideal communication and 25% Bernoulli packet loss. Under ideal communication, increasing B from 1 to 12 reduces MinSum cost by 19.0%, 23.0%, and 31.8% for ACBBA, PI, and HIPC, respectively, while increasing MinMax cost by 45.6%, 94.3%, and 67.6%. Under packet loss, the lowest-mean MinSum setting shifts from B = 12 to B = 2 for ACBBA and PI. Repeated paired cross-fitting shows that retaining the ideal-network setting incurs held-out MinSum penalties of 14.4% and 7.2%, respectively, and increases MinMax cost by 30.0% and 41.8% relative to the loss-conditioned MinSum setting. HIPC retains a deep MinSum operating region, while the MinMax setting remains stable for all three allocators. Experiments at two additional target loads reproduce the ACBBA and PI MinSum shifts.

James Lott, Vahraz Honary

Shiley Marcos School of Engineering University of San Diego San Diego, United States of America

Multi-Robot Task Allocation Multi-Robot Coordination

Ask PDF

Aug 16, 2026

Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot 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.

Jose Rodriguez, Sven Koenig, Wenjie Dong +1

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

Multi-Robot Task Allocation Multi-Agent Consensus

Ask PDF

Apr 13, 2026

Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

We study dynamic multi-robot task allocation under uncertain task completion, time-window constraints, and incomplete information. Tasks arrive online over a finite horizon and must be completed within specified deadlines, while agents operate from distributed hubs with limited sensing and communication. We model incomplete information through hub-based sensing regions that determine task visibility and a communication graph that governs inter-hub information exchange. Using this framework, we propose Iterative Best Response (IBR), a decentralized policy in which each agent selects the task that maximizes its marginal contribution to the locally observed welfare. We compare IBR against three baselines: Earliest Due Date first (EDD), Hungarian algorithm, and Stochastic Conflict-Based Allocation (SCoBA), on a city-scale package-delivery domain with up to 100 drones and varying task arrival scenarios. Under full and sparse communication, IBR achieves competitive task-completion performance with lower computation time.

Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson +1

Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA, United States · Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, United States · Thayer School of Engineering, Dartmouth College, Hanover, NH, United States

Multi-Robot Task Allocation Multi-Agent Systems Multi-Robot Coordination

Ask PDF