CS Paper Radar

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

James Lott, Vahraz Honary

cs.RO cs.MA ·submitted 2026-09-05 21:53 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.75
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.42

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

cs.RO ·2026-09-11 ·Ben Rossano, Jaein Lim, Jonathan P. How
similarity 0.59
Abstract · 8 pages, 6 figures

Exploring unknown environments with multi-robot teams can improve efficiency by allowing robots to explore in parallel. However, realizing these gains requires effective information sharing. When communication is intermittent, robots must balance the benefits of sharing information against the cost of diverting from exploration to establish communication. This paper introduces MACE, a decentralized exploration framework that actively evaluates whether establishing communication is worthwhile. At scheduled communication windows, robots estimate the cost of reaching previously identified communication locations. By formulating this decision as a variant of the Vehicle Orienteering Problem, robots evaluate routes based on the travel required to establish communication and the exploration that can be completed along the way. This approach enables robots to communicate more frequently than under purely opportunistic strategies while reducing the unnecessary travel associated with fixed rendezvous strategies. Across a set of simulated environments with varying size and geometry, we demonstrate that MACE reduces the total exploration time by up to 23% compared to existing communication-constrained exploration strategies.

0.21

Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization

cs.RO cs.MA ·2026-10-09 ·Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme
similarity 0.58
Abstract

Multi-robot coordination is essential in applications such as coverage, target tracking, and information gathering, where robots must jointly select actions to maximize team performance. Submodular maximization provides an effective framework for such coordination, and resilient variants further account for robot failures or adversarial removals. However, existing methods typically overlook the impact of robot loss on the communication network, which may disconnect the surviving team and prevent continued coordination. To address this issue, we introduce Resilient $k$-Connected Submodular Maximization, which jointly considers task performance, resilience, and communication connectivity. The resulting feasible family is not a matroid, preventing the direct application of classical curvature-greedy guarantees. We overcome this challenge through a Menger-based connectivity reduction, a connectivity-aware greedy algorithm with a feasibility-preserving fallback, and a new curvature-based analysis that captures the cost of enforcing connectivity through a single factor $ρ$. Our method achieves a worst-case post-failure objective within a factor of $[\max(1-ν_f(\mathcal{I}),h(N,β))]^2 ρ\frac{1}{κ_f}(1-e^{-κ_f})$ of the optimal connectivity-respecting resilient assignment, while recovering the classical unconstrained guarantee in the appropriate limits. Experiments on multi-robot target tracking validate the proposed method and characterize the practical impact of connectivity constraints.

0.19

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

cs.RO ·2026-10-06 ·James Lott, Vahraz Honary
similarity 0.57
Abstract

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 HIPC as a representative MRTA suite. The study comprises a 3,000-mission AGX Orin campaign with measured computation delay, 3,000 paired zero-compute missions, and a 96-mission Pololu 3pi+ RP2040 allocator hardware-in-the-loop campaign. Immediate (Eager) admission is compared with thresholds of two, four, and eight tasks and a four-task policy with a 10-s waiting bound across three arrival rates. Across the AGX experiments, coalescing reduces both allocator calls and processor work in 31 of 48 evaluated conditions, although the magnitude of the saving varies by allocator. The principal cost appears under sparse arrivals, where four-task batching increases online-target mean latency by 20.08-23.57 s, predominantly through admission waiting. Bounded admission reduces mean work in ten of twelve allocator-load conditions, including a 19.35% reduction with a 1.40-s mean latency increase for high-arrival HIPC. RP2040 experiments show that this tradeoff can become more favorable as processor constraints tighten. Across four matched medium-arrival HIPC scenarios, Count b=4 reduces mean RP2040 work by 59.85% and service latency by 39.47%, while the corresponding AGX cases increase latency by 27.69%. These results show that the usefulness of task-admission coalescing depends on arrival intensity, allocator-specific behavior, and the relative cost of computation on the execution platform.

0.19

Communication-Free Distributed Multi-Robot Task Allocation under Partial Observations Using Labeled Multi-Bernoulli Filtering

cs.RO eess.SY ·2026-09-30 ·Takumi Ito, Akiya Kamimura
similarity 0.56
Abstract · This paper has been submitted to IEEE ICRA 2027 for possible publication

This paper proposes a communication-free multi-robot task allocation framework based solely on local observations. In this study, tasks are defined as reaching target locations. Each robot estimates the positions of neighboring robots using a Labeled Multi-Bernoulli (LMB) filter and independently assigns tasks through a greedy auction-based strategy. By continuously updating state estimates and reallocating tasks during execution, the proposed method enables decentralized coordination without explicit communication. Monte Carlo simulations demonstrate that the proposed method enables effective cooperative task allocation without inter-robot communication while remaining robust to measurement clutter and observation uncertainty.

0.37

Minimum Sufficient Communication for Independent Behaviour Tree Robot Teams

cs.RO ·2026-10-28 ·Sherry Jiang, Oliver Obst
top venuetheory similarity 0.55
Abstract · 10 pages; accepted for presentation at the Australasian Conference on Robotics and Automation (ACRA 2026)

We present an experimental framework for determining sufficient communication in robot teams running fixed, independent Behaviour Trees with private blackboards. Within a declared policy family, we vary message content and admission frequency and measure traffic in recipient-weighted bits per robot decision. A dense sweep identifies candidate policies for comparison with full-state communication. We retest selected candidates and the reference on fresh, paired scenarios, using one-sided simultaneous confidence bounds to assess whether success remains within five percentage points of the full-state reference. The bounds also assess whether tested cheaper policies can be ruled out as insufficient. Depending on the evidence, the framework reports an exact minimum, a positive bracket, a sufficient upper bound, or an unresolved boundary. Experiments with eight content policies across four warehouse conditions identify zero communication as the exact minimum under low contention. In the scaled condition, the no-release policy at gate $q=0.992222$ is confirmed sufficient, achieving 96.33% success at an estimated rate of 738.55 bits per robot decision, or 0.544% of full-state traffic. The positive minimum remains unresolved. These claims apply only to the declared policy family, sampled gate values and operating conditions.

0.52

Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration

cs.RO cs.MA ·2026-10-13 ·Changxuan Yao, Sandilya Sai Garimella, Lu Gan, Panagiotis Tsiotras
published similarity 0.54
Abstract · 5 pages, 3 figures. Accepted to the IROS 2026 SeMaNa Workshop. The first two authors contributed equally

Multi-robot exploration under communication and mobility constraints requires balancing information gain with reachability. We present a distributed semantic exploration framework that combines Dirichlet mapping, budget-constrained trajectory selection, and Resource-Aware distributed Greedy (RAG) coordination. Each robot clusters frontiers, computes terrain- and heading-aware least-cost paths with a single budget-limited Dijkstra search, and selects feasible paths by marginal information gain, represented by the expected reduction in Dirichlet entropy. Each robot's per-round selection is exact, the team's joint per-round information gain is at least half the centralized optimum, and the bound degrades gracefully under limited communication. Ten-run gridworld ablations show improved coverage, semantic mIoU, and map certainty with lower entropy and traversal cost per unit distance than shortest-distance frontier selection. Budget-sensitivity experiments show that an intermediate budget best balances path reach and receding-horizon execution. In photorealistic full-system simulation against five coordination rules run in their native published forms, the proposed method attains the highest mean coverage and semantic accuracy while being the only one that respects the per-trajectory mobility budget.

0.19

VLA Handover: Failure-Prediction-Based Switching from On-Robot to Server VLA Models

cs.RO cs.LGcs.NI ·2026-11-06 ·Takayuki Nishio
similarity 0.53
Abstract · 6 pages, 4 figures, 3 tables. Submitted to IEEE ICC 2027

Large vision-language-action (VLA) models generalize well but are difficult to run in real time on a robot, and small VLAs that run there fail more often. Remote inference over beyond-5G and 6G networks lets a robot use a large VLA on a server, but querying the server for every action chunk limits the number of robots per server. We propose VLA handover: the robot runs a small VLA (S-VLA) and switches to a large VLA (L-VLA) on a server only when the S-VLA is likely to fail. We formulate the switching as minimizing the request cost under a required success probability and, since this problem cannot be solved directly, propose a heuristic framework that retrains neither VLA. In simulation with SmolVLA and $π_{0.5}$ on three of the four LIBERO suites, VLA handover raised the success rate by 11-22 percentage points over the S-VLA alone and sent 49-77% fewer requests than server-only control at a 2-4 percentage-point lower success rate, and its completion time grew less with the network latency.

0.13