ロボット故障時にも通信を維持する高速二重連結修復法
Fast Biconnectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
マルチロボット系で1台故障しても通信網が切れないよう最短で修復する問題を定式化し、グラフ理論に基づく近似解法を提案した。
著者: Md Ishat-E-Rabban, Guangyao Shi, 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 multi-robot system is the ability to repair the communication topology itself in the case of robot failure. In this paper, we focus on the Fast Biconnectivity Restoration (FBR) problem, which aims to repair a connected network to make it biconnected as fast as possible, where a biconnected network is a communication topology that cannot be disconnected by removing one node. We develop a Quadratically Constrained Program (QCP) formulation of the FBR problem, which provides a way to optimally solve the problem. We also propose an approximation algorithm for the FBR problem based on graph theory. By conducting empirical studies, we demonstrate that our proposed approximation algorithm performs close to the optimal while significantly outperforming the existing solutions.
