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

Jingjin Yu, Soon Jo Chung, Petros G. Voulgaris

Research output: Contribution to journalConference article

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Article number6906991
Pages (from-to)1098-1105
Number of pages8
JournalProceedings - IEEE International Conference on Robotics and Automation
DOIs
StatePublished - Sep 22 2014
Externally publishedYes
Event2014 IEEE International Conference on Robotics and Automation, ICRA 2014 - Hong Kong, China
Duration: May 31 2014Jun 7 2014

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Distance optimal target assignment in robotic networks under communication and sensing constraints'. Together they form a unique fingerprint.

  • Cite this