Target assignment in robotic networks: Distance optimality guarantees and hierarchical strategies

Jingjin Yu, Soon Jo Chung, Petros G. Voulgaris

Research output: Contribution to journalArticle

Abstract

We study the problem of multi-robot target assignment to minimize the total distance traveled by the robots until they all reach an equal number of static targets. In the first half of the paper, we present a necessary and sufficient condition under which true distance optimality can be achieved for robots with limited communication and target-sensing ranges. Moreover, we provide an explicit, non-asymptotic formula for computing the number of robots needed to achieve distance optimality in terms of the robots' communication and target-sensing ranges with arbitrary guaranteed probabilities. The same bounds are also shown to be asymptotically tight. In the second half of the paper, we present suboptimal strategies for use when the number of robots cannot be chosen freely. Assuming first that all targets are known to all robots, we employ a hierarchical communication model in which robots communicate only with other robots in the same partitioned region. This hierarchical communication model leads to constant approximations of true distance-optimal solutions under mild assumptions. We then revisit the limited communication and sensing models. By combining simple rendezvous-based strategies with a hierarchical communication model, we obtain decentralized hierarchical strategies that achieve constant approximation ratios with respect to true distance optimality. Results of simulation show that the approximation ratio is as low as 1.4.

Original languageEnglish (US)
Article number6868245
Pages (from-to)327-341
Number of pages15
JournalIEEE Transactions on Automatic Control
Volume60
Issue number2
DOIs
StatePublished - Feb 1 2015

Keywords

  • Networked robots
  • Optimality

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Target assignment in robotic networks: Distance optimality guarantees and hierarchical strategies'. Together they form a unique fingerprint.

  • Cite this