Minimum k-Connectivity Maintenance for Robust Multi-Robot Systems

Abstract

In many multi-robot applications, it is critical to maintain connectivity within the robotic team to allow for information exchange and coordination. While most of the existing works focus on connectivity control that ensures robotic team remain connected as one component without faults, we consider the problem of robust connectivity maintenance that seeks to maintain emph{$k-$connectivity}, such that the multi-robot network could stay connected with the removal of fewer than $k$ robots. In this paper, we propose provably minimum $k-$connectivity maintenance algorithms for multi-robot systems. This ensures the robustness of the multi-robot network connectivity at all time and also in a flexible and optimal way to provide the highest freedom for robots task-related controllers. Particularly, we propose a $k-$Connected Minimum Constraints Subgraph ($k$-CMCS) algorithm that activates the minimum $k-$connectivity constraints to the original controllers, and then revise the original controllers in a textit{minimally invasive fashion}. We demonstrate the effectiveness of our approach via simulations of up to 40 robots in the presence of multiple behaviors.