2020/11/02 by Ishat-E-Rabban, Md, Guangyao Shi, Pratap Tokekar +2 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Advanced biosensing and bioanalysis techniques #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2011.00685
openalex publication_date 2020/11/02 · openalex created_date 2020/11/23 · openalex updated_date 2026/07/28
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.