k連結性制約付き劣モジュラ最大化による故障に強いマルチロボット協調
Failure-Resilient Multi-Robot Coordination with $k$-Connectivity Constrained Submodular Maximization
ロボット故障時も通信ネットワークの連結性を保ちつつタスク性能を最大化するため、k連結性制約付き劣モジュラ最大化問題を定式化し、貪欲アルゴリズムと理論保証を提案した。
詳しい要約
1. どんなもの？
2. 先行研究と比べてどこがすごい？
3. 技術・手法の肝は？
4. どうやって有効だと検証した？
5. 議論はある？
6. 次に読むべき論文は？
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Yoonjae Hwang, Hojune Kim, Ellen Novoseller, Guangyao Shi, Gaurav S. Sukhatme
分類: cs.RO, cs.MA
原文アブストラクト
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.