Establishing Fault-Tolerant Connectivity of Mobile Robot Networks

Kazim Selim Engin, Volkan Isler

Research output: Contribution to journalArticlepeer-review

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 kconnected graph induced on the initial configuration of the robots. We then show that the approximation factor of our algorithm improves to O(√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.

Original languageEnglish (US)
Pages (from-to)667-677
Number of pages11
JournalIEEE Transactions on Control of Network Systems
Volume8
Issue number2
DOIs
StatePublished - Jun 1 2021

Bibliographical note

Publisher Copyright:
IEEE

Keywords

  • Approximation algorithms
  • fault tolerance
  • multi-robot systems
  • wireless sensor networks

Fingerprint

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

Cite this