Skip to content
Preprint

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

Sep 2026 · 1 citation · 45 references
Computer Science

TL;DR

DGA and DMCHBA remained viable and stable in every tested condition, while ACBBA, PI, and DGA lost stability or viability as communication degraded, and Static and execution-integrated computation rankings diverged as task load increased.

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.

View source

Similar papers

Preprint Sep 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 of...

J. Lott, Vahraz Honary · 1 citation · ⚡1
Preprint Oct 2026

Embedded Evaluation of Task Admission Coalescing in Decentralized Multi-Robot Systems

Multi-robot task allocators in dynamic missions commonly admit newly released tasks immediately, potentially invoking allocation for each new arrival. We evaluate task-admission coalescing as a mechanism for controlling allocator processor work while accounting for target-service latency, using CBAA, ACBBA, PI, and HIP...

J. Lott, Vahraz Honary · 0 citations
#artificial intelligence Preprint Sep 2026

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

AssemblyGrid v1 is introduced, 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.

Fouad Bahrpeyma, David Heik, Dirk Reichelt · 0 citations
Open access Aug 2026

ICBBA-ACO-Based Multi-Robot Task Allocation for Smart Charging Stations

ICBBA-ACO provides the lowest mean objective among the compared methods that maintain full deadline compliance, demonstrating a favorable quality–runtime trade-off within the tested operating range.

Meiyu Chang, Zhaoyu Ku, Xuan-Yu Xing et al. · 0 citations
Preprint Sep 2026

CC-OPI: Online Distributed Task Allocation for UAV Swarms under Communication Constraints

It is established that CC-OPI terminates in finite time, free of stale-completion deadlock and of unbounded reassignment within the mission horizon, and within the tested settings, CC-OPI degrades gracefully as connectivity weakens and absorbs packet loss, terrain occlusion, and runtime task arrival.

Biao Liu, Tong Zhang · 0 citations
Preprint Aug 2026

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

This paper introduces the Grouping Auction-Consensus Algorithm (GACA), a decentralized MRTA framework that adopts the two-phase auction-consensus architecture of CBBA while fundamentally redesigning its bidding mechanism to reason over groups of spatially proximate tasks.

J. Rodriguez, Sven Koenig, Wen-Jie Dong et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.