Multi-robot coordination resilient to failures and communication breaks
Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization
RoboticsMultiagent Systems
Summary
When teams of robots work together, they must both perform their tasks well and keep in touch with each other to coordinate. The authors looked at ways to plan robot actions so the team still works well even if some robots fail or lose contact. They developed a new mathematical approach that balances doing the job, surviving failures, and staying connected. Tests showed their method helps robot teams keep tracking targets effectively, even if some connections break.
What this means in practice
- •For robotics engineers: Schedule robot team actions that keep coordinated and connected even after some robot failures in field surveillance tasks.
- •For network planners: Design communication-aware deployment strategies for mobile sensor networks requiring fault-tolerant connectivity.
Authors
Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme
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.