학술논문
Establishing Fault-Tolerant Connectivity of Mobile Robot Networks
Document Type
Periodical
Author
Source
IEEE Transactions on Control of Network Systems IEEE Trans. Control Netw. Syst. Control of Network Systems, IEEE Transactions on. 8(2):667-677 Jun, 2021
Subject
Language
ISSN
2325-5870
2372-2533
2372-2533
Abstract
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.