Traveled distance minimization and hierarchical strategies for robotic networks
We study the distance optimal assignment of n mobile robots to an equal number of targets under communication and target-sensing constraints. Extending previous results over uniform distributions, we show that when the robots and targets assume the same but arbitrary distribution over the unit square, a carefully designed distributed hierarchical strategy has expected travel distance that matches the best known upper bound assuming global communication and infinite target-sensing range. In a sense, our result shows that for target assignment problems in robotic networks, local optimality also offers good guarantees on global optimality.
© 2014 IEEE. Date of Conference: 21-23 May 2014. Date Added to IEEE Xplore: 14 August 2014. This work was supported in part by AFOSR grant FA95501210193 and NSF grant IIS-1253758.