Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots
DOI:
https://doi.org/10.1609/icaps.v28i1.13926Keywords:
multi-robot systems, robot planning and plan execution, networked robot systemsAbstract
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
Issue
Section
Robotics Track