Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots

Authors

  • K. Engin University of Minnesota
  • Volkan Isler University of Minnesota

DOI:

https://doi.org/10.1609/icaps.v28i1.13926

Keywords:

multi-robot systems, robot planning and plan execution, networked robot systems

Abstract

We study the following connectivity formation problem: Robots equipped with radio transmitters with a bounded communication range are scattered over a large area. They would like to relocate so as to form a connected network as soon as possible. Where should each robot move? We present an $O(\sqrt{n})$-factor approximation algorithm for this problem when $n$ robots are initially distributed uniformly at random in a bounded area. In addition to analytical proofs, we verify the performance of our algorithm through simulations.

Downloads

Published

2018-06-15

How to Cite

Engin, K., & Isler, V. (2018). Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 451-458. https://doi.org/10.1609/icaps.v28i1.13926