Fast Biconnectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
This addresses robust communication maintenance for multi-robot teams performing optimization tasks, representing an incremental improvement with a novel method for a known bottleneck.
The paper tackles the Fast Biconnectivity Restoration (FBR) problem in multi-robot systems to repair a connected network to biconnected quickly, developing an optimal QCP formulation and an approximation algorithm that performs close to optimal and significantly outperforms existing solutions.
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.