Establishing Fault-Tolerant Connectivity of Mobile Robot Networks

This article considers the problem of establishing fault-tolerant mobile networks. In settings where $n$ robots with bounded communication ranges are dispersed over a large area, we seek to solve the problem of relocating the robots so that they form a $k$ -connected network as quickly as possible. For this problem, we present an algorithm, whose performance is at most $O(D)$ times worse than that of the optimal strategy if the robots are deployed arbitrarily, where $D$ is the diameter of the smallest k -connected graph induced on the initial configuration of the robots. We then show that the approximation factor of our algorithm improves to $O(\sqrt{n/\log n})$ , for the case where the starting locations of the robots are chosen uniformly at random. Finally, we verify our results with large-scale simulations and demonstrate our method on the Robotarium experimental multirobot platform.