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

Abstract

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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Robotics

• arXiv preprint · 5 September 2026

  Counter-Swarm Doctrine: Containing Coordinated Agent Intrusions

  Gregory N Frank
• arXiv preprint · 6 September 2026

  Adaptive stabilization of a leaderless bearing-constrained formation with disturbances

  Minh Hoang Trinh, Chuong Van Nguyen, Quoc Van Tran and 1 other
• arXiv preprint · 6 September 2026

  CAPMAS: Capability-Based Delegation of Privileges in Multi-Agent Systems

  Rasmus Moorits Veski, Rachid Guerraoui and David Froelicher
• arXiv preprint · 4 September 2026

  MIVAIS: A Study Environment for Multi-Agent Mixed-Initiative Visual Analytics Applications

  Tobias Stähle, Simon Schneider, Rita Sevastjanova and 1 other
• arXiv preprint · 6 September 2026

  Certifying cooperation: a novel approach to cooperative multi-agent task generation

  Yannick Molinghen, Hugo Charels and Tom Lenaerts

All new papers in Robotics