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

Bundle Length Tradeoffs in Decentralized Multi-Robot Task Allocation Under Degraded Communications
Sep 5, 2026James Lott, Vahraz HonaryMulti-Robot Task Allocation Multi-Robot Coordination
Shiley Marcos School of Engineering University of San Diego San Diego, United States of America
Grouping Auction-Consensus Algorithm for Decentralized Task Allocation in Multi-Robot Systems
Aug 16, 2026Jose Rodriguez, Sven Koenig, Wenjie Dong +1Multi-Robot Task Allocation Multi-Agent Consensus
The University of Texas at Rio Grande Valley, Edinburg, Texas 78539, USA · University of California, Irvine, CA 92697, USA
Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach
Apr 13, 2026Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson +1Multi-Robot Task Allocation Multi-Agent Systems
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

Sep 5, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

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

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