Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance
<|reference_start|>Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance: 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.<|reference_end|>
@article{ishat-e-rabban2024fast,
    title={Fast k-connectivity Restoration in Multi-Robot Systems for Robust
  Communication Maintenance},
    author={Md Ishat-E-Rabban, Guangyao Shi, Griffin Bonner, Pratap Tokekar},
    journal={arXiv preprint arXiv:2404.03834},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.03834},
    primaryClass={cs.RO}
}