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

In multi-robot systems, maintaining persistent communication graph connectivity is often overly restrictive, especially when robots have limited communication ranges but operate in large environments. Instead, allowing robots to temporarily disconnect and later reconnect is often more desirable for efficient task execution while still ensuring timely information sharing across the team. In this paper, we propose an adaptive prescribed-time control barrier function (adaptive PT-CBF) framework that enables robots to temporarily disconnect and re-enter the communication range within an adjustable and feasible prescribed time. Moreover, we introduce a reconnection triggering mechanism that jointly considers task execution and reconnection urgency, thereby providing a principled way to decide when reconnection should occur. Theoretical analysis justifies convergence to the satisfying reconnection within a prescribed finite time. Experimental results validate the performance of our proposed adaptive PT-CBF with improved task efficiency and satisfying reconnections.

Most multi-robot task allocation methods rely on communication to resolve conflicts and reach consistent assignments. In environments with limited bandwidth, degraded infrastructure, or adversarial interference, existing approaches degrade sharply. We introduce a learning-based framework that achieves high-quality task allocation without any robot-to-robot communication. The key idea is that robots coordinate implicitly by predicting teammates' bids: if each robot can anticipate competition for a task, it can adjust its choices accordingly. Our method predicts bid distributions to correct systematic errors in analytical mean-field approximations. While analytical predictions assume idealized conditions (uniform distributions, known bid functions), our learned approach adapts to task clustering and spatial heterogeneity. Inspired by Smart Predict-then-Optimize (SPO), we train predictors end-to-end to minimize Task Allocation Regret rather than prediction error. To scale to large swarms, we develop a mean-field approximation where each robot predicts the distribution of competing bids rather than individual bids, reducing complexity from $O(NT)$ to $O(T)$. We call our approach FORMICA: Field-Oriented Regret-Minimizing Implicit Coordination Algorithm. Experiments show FORMICA substantially outperforms a natural analytical baseline. In scenarios with 16 robots and 64 tasks, our approach improves system reward by 17% and approaches the optimal MILP solution. When deployed on larger scenarios (256 robots, 4096 tasks), the same model improves performance by 7%, demonstrating strong generalization. Training requires only 21 seconds on a laptop, enabling rapid adaptation to new environments.

Multi-robot task allocation usually assumes some combination of communication, known task models, or a coordinator. We study the opposite extreme, a regime common in practice but overlooked in theory, which we name Zero-Knowledge MRTA (ZK-MRTA): a robot team with no prior knowledge (no task models, not even the latent rank), no communication (no messages, no parameter sharing, no coordinator), and only a partial and privately-noisy view of a public stream of teammates' outcomes. A hidden low-rank structure governs which robot suits which task, and there are far more tasks than rounds, so most (robot, task) pairs are never attempted. Yet each robot can act well on tasks it never attempted, and onboard new tasks, by running online low-rank collaborative filtering over the broadcast (SwarmCF). The advantage over any structure-free learner is categorical, not a constant factor: a structure-free learner is provably at the prior-mean error floor on unseen pairs. We prove a matching per-robot sample complexity (Θ(d) versus Θ(n), in the rank d and the task count n), an anytime (cumulative-reward) separation under task scarcity, and a deterministic condition under which decentralized recovery from the masked broadcast is exact (validated empirically). Experiments quantify the value of the broadcast, a positive scaling law (per-robot unseen-pair skill rises with team size), and the strongest masking-robustness and anytime profile among low-rank methods, recovering most (about 80% on earned skill) of a centralized full-communication ceiling, and holding under capacity-1 contention and in a robotics-grounded sensing instance.