A Caltech Library Service

Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies

Yu, Jingjin and Chung, Soon-Jo and Voulgaris, Petros G. (2015) Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies. IEEE Transactions on Automatic Control, 60 (2). pp. 327-341. ISSN 0018-9286.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Chung, Soon-Jo0000-0002-6657-3907
Additional Information:© 2014 IEEE. Manuscript received July 17, 2013; revised January 28, 2014; accepted July 5, 2014. Date of publication July 30, 2014; date of current version January 21, 2015. This work was supported in part by AFOSR Grant FA95501210193, NSF Grant IIS-1253758, and NSF Grant ECCS 10-27437. Recommended by Associate Editor E. Frazzoli. The authors wish to thank the anonymous reviewers and S. Har-Peled and A. Nayyeri for their constructive comments.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA95501210193
NSFECCS 10-27437
Subject Keywords:Networked robots, optimality
Issue or Number:2
Record Number:CaltechAUTHORS:20161221-081248601
Persistent URL:
Official Citation:J. Yu, S. J. Chung and P. G. Voulgaris, "Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies," in IEEE Transactions on Automatic Control, vol. 60, no. 2, pp. 327-341, Feb. 2015. doi: 10.1109/TAC.2014.2344291
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73052
Deposited By: Ruth Sustaita
Deposited On:21 Dec 2016 18:11
Last Modified:03 Oct 2019 16:24

Repository Staff Only: item control page