Establishing Fault-Tolerant Connectivity of Mobile Robot Networks

This paper 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 <formula><tex>$k$</tex></formula>-connected network as quickly as possible. For this problem, we present an algorithm whose performance is at most <formula><tex>$O(D)$</tex></formula> 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 <formula><tex>$O(\sqrt{n/\log n})$</tex></formula>, for the case where the starting locations of the robots are chosen uniformly at random. Finally, we verify our results for large scale in simulations and demonstrate our method on a multi-robot system.