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(√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.
|Original language||English (US)|
|Number of pages||8|
|Journal||Proceedings International Conference on Automated Planning and Scheduling, ICAPS|
|State||Published - Jan 1 2018|
|Event||28th International Conference on Automated Planning and Scheduling, ICAPS 2018 - Delft, Netherlands|
Duration: Jun 24 2018 → Jun 29 2018