Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies
Abstract
We study the problem of assigning a group of mobile robots to an equal number of distinct static targets, seeking to minimize the total distance traveled by all robots until each target is occupied by a robot. In the first half of our paper, the robots assume limited communication and target-sensing range otherwise, the robots have no prior knowledge of target locations. Under these assumptions, we present a necessary and sufficient condition under which true distance optimality can be achieved. Moreover, we provide an explicit, non-asymptotic formula for computing the number of robots needed for achieving distance optimality in terms of the robots' communication and target-sensing ranges with arbitrary guaranteed probabilities. We also show that the same bound is asymptotically tight. Because a large number of robots is required for guaranteeing distance optimality with high probability, in the second half of our study, we present suboptimal strategies when the number of robots cannot be freely chosen. Assuming that each robot is aware of all target locations, we first work under a hierarchical communication model such that at each hierarchy level, the workspace is partitioned into disjoint regions; robots can communicate with one another if and only if they belong to the same region. This communication model leads naturally to hierarchical strategies, which, under mild assumptions, yield constant approximations of true distance-optimal solutions. We then revisit the range-based communication model and show that combining hierarchical strategies with simple rendezvous-based strategies results in decentralized strategies which again achieve constant approximation ratios on distance optimality. Results from simulation show that the approximation ratio is as low as 1.4.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2013
- Accession Number
- ADA588801
Entities
People
- Jingjin Yu
- Petros G. Voulgaris
- Soon-Jo Chung
Organizations
- University of Illinois Urbana–Champaign