Abstract
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.
Original language | English (US) |
---|---|
Journal | IEEE Transactions on Control of Network Systems |
DOIs | |
State | Published - Jun 1 2021 |
Bibliographical note
Publisher Copyright:IEEE
Keywords
- Approximation algorithms
- Control systems
- Fault tolerance
- Fault tolerant systems
- Robot kinematics
- Robot sensing systems
- Robots