Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
| Autor: | Ishat-E-Rabban, Md, Shi, Guangyao, Bonner, Griffin, Tokekar, Pratap |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 17 pages, 6 figures, 3 algorithms. arXiv admin note: text overlap with arXiv:2011.00685 |
| Databáze: | arXiv |
| Externí odkaz: |
|