マルチロボットシステムにおける堅牢な通信維持のための高速k連結性復元
Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
ロボット故障時に通信トポロジーを最小移動でk連結に修復する問題に対し、最適化定式化とスケーラブルなグラフ理論アルゴリズムを提案し、既存手法を30%上回る性能を示した。
著者: Md Ishat-E-Rabban, Guangyao Shi, Griffin Bonner, Pratap Tokekar
分類: cs.RO
原文アブストラクト
Maintaining a robust communication network plays an important role in the success of a multi-robot team jointly performing an optimization task. A key characteristic of a robust cooperative multi-robot system is the ability to repair the communication topology in the case of robot failure. In this paper, we focus on the Fast k-connectivity Restoration (FCR) problem, which aims to repair a network to make it k-connected with minimum robot movement. We develop a Quadratically Constrained Program (QCP) formulation of the FCR problem, which provides a way to optimally solve the problem, but cannot handle large instances due to high computational overhead. We therefore present a scalable algorithm, called EA-SCR, for the FCR problem using graph theoretic concepts. By conducting empirical studies, we demonstrate that the EA-SCR algorithm performs within 10 percent of the optimal while being orders of magnitude faster. We also show that EA-SCR outperforms existing solutions by 30 percent in terms of the FCR distance metric.
