Minimizing Movement to Establish the Connectivity of Randomly Deployed Robots

Book One

Volume

Proceedings of the International Conference on Automated Planning and Scheduling, 28

Robotics Track

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.

10.1609/icaps.v28i1.13926