TY - GEN
T1 - Distance optimal target assignment in robotic networks under communication and sensing constraints
AU - Yu, Jingjin
AU - Chung, Soon Jo
AU - Voulgaris, Petros G.
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/9/22
Y1 - 2014/9/22
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84906755716&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906755716&partnerID=8YFLogxK
U2 - 10.1109/ICRA.2014.6906991
DO - 10.1109/ICRA.2014.6906991
M3 - Conference contribution
AN - SCOPUS:84906755716
T3 - Proceedings - IEEE International Conference on Robotics and Automation
SP - 1098
EP - 1105
BT - Proceedings - IEEE International Conference on Robotics and Automation
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Conference on Robotics and Automation, ICRA 2014
Y2 - 31 May 2014 through 7 June 2014
ER -