arXiv cs.MA· Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme·· 6 天前AI 评分18
基于 k-连通约束子模最大化的容错多机器人协同
Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization
AI 导读
研究者提出 Resilient k-Connected Submodular Maximization，将任务性能、容错性与通信连通性纳入统一框架，解决机器人失效导致幸存团队通信断连、无法继续协同的问题。
正文 · 原文
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 $\rho$. Our method achieves a worst-case post-failure objective within a factor of $[\max(1-\nu_f(\mathcal{I}),h(N,\beta))]^2 \rho \frac{1}{\kappa_f}(1-e^{-\kappa_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.
| Subjects: | Robotics (cs.RO); Multiagent Systems (cs.MA) |
| Cite as: | arXiv:2610.13049 [cs.RO] |
| (or arXiv:2610.13049v1 [cs.RO] for this version) | |
| https://doi.org/10.48550/arXiv.2610.13049 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yoonjae Hwang [view email]
[v1]
Fri, 9 Oct 2026 06:04:45 UTC (3,708 KB)
来源：arXiv cs.MA · arxiv.org