Fast k-connectivity Restoration in Multi-Robot Systems for Robust Communication Maintenance: Algorithmic and Learning-based Solutions

Maintaining a robust communication network is crucial for the success of multi-robot online task planning. A key capability of such systems is the ability to repair the communication topology in the event of robot failures, thereby ensuring continued coordination. In this paper, we address the Fast k-Connectivity Restoration (FCR) problem, which seeks to restore a network’s k-connectivity with minimal robot movement. Here, a k-connected network refers to a topology that remains connected despite the removal of up to k − 1 nodes. We first formulate the FCR problem as a Quadratically Constrained Program (QCP), which yields optimal solutions but is computationally intractable for large-scale instances. To overcome this limitation, we propose EA-SCR, a scalable algorithm grounded in graph-theoretic principles, which leverages global network information to guide robot movements. Furthermore, we develop a learning-based approach, GNN-EA-SCR, which employs aggregation graph neural networks to learn a decentralized counterpart of EA-SCR, relying solely on local information exchanged among neighboring robots. Through empirical evaluation, we demonstrate that EA-SCR achieves solutions within 10% of the optimal while being orders of magnitude faster. Additionally, EA-SCR surpasses existing methods by 30% in terms of the FCR distance metric. For the learning-based solution, GNN-EA-SCR, we show it attains a success rate exceeding 90% and exhibits comparable maximum robot movement to EA-SCR.