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, whereD 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(root 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.