Establishing Fault-Tolerant Connectivity of Mobile Robot Networks

Kazim Selim Engin, Volkan Isler

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
JournalIEEE Transactions on Control of Network Systems
StatePublished - Jun 1 2021

Bibliographical note

Publisher Copyright:


  • Approximation algorithms
  • Control systems
  • Fault tolerance
  • Fault tolerant systems
  • Robot kinematics
  • Robot sensing systems
  • Robots


Dive into the research topics of 'Establishing Fault-Tolerant Connectivity of Mobile Robot Networks'. Together they form a unique fingerprint.

Cite this