Distance optimal target assignment in robotic networks under communication and sensing constraints

We study the problem of minimizing the total distance incurred in assigning a group of mobile robots to an equal number of static targets. Assuming that the robots have limited, range-based communication and target-sensing capabilities, we present a necessary and sufficient condition for ensuring distance optimality when robots and targets are uniformly randomly distributed. We then provide an explicit, non-asymptotic formula for computing the number of robots needed for guaranteeing optimality in terms of the robots´ sensing and communication capabilities with arbitrarily high probabilities. The bound given in the formula is also asymptotically tight. Due to the large number of robots needed for high-probability optimality guarantee, we continue to investigate strategies for cases in which the number of robots cannot be freely chosen. We show that a properly designed strategy can be asymptotically optimal or suboptimal with constant approximation ratios.