Multi-robot coordination requires maintaining network connectivity, especially in critical operations such as search and rescue, where network robustness is paramount. In this paper, we study the Fast k-connectivity Restoration problem (FCR), which aims to minimize the maximum distance required to restore connectivity. Recent works have proposed scalable solutions, but they rely on a centralized architecture or a learning-based solution to transfer the observable policies from centralized to distributed variants. However, computing node connectivity in a distributed setting is challenging, and performing such operations in a deterministic, algorithmic manner is critical for generalizability and persistent deployment in diverse, unknown environments. We propose a distributed control approach for improving and restoring connectivity. Using local neighborhood interactions and information, our algorithm improves the degrees of individual robots by augmenting 1-hop edges based on their distances, achieving the desired level of node connectivity and yielding comparable performance to achieve sparse connectivity improvements and up to 58% reduction in movements required to achieve dense connectivity over the state-of-the-art algorithms.
Figure 1. Depiction of the FCR problem showing the initial configuration and the final configuration after augmented edges (links) to restore k-connectivity to K = 4 or 6.
Figure 2. This figure depict the working of the proposed approaches and baselines. The figures illustrate the final positions of the robots after edge augmentation and displacement. The edges in red represent the augmented edges.
Figure 3. Real-word experiment showcasing DEA-DR-k on our in-house swarm robotics testbed with a team of N = 8 robots, sensing radius = 0.5 m.