Home/Efficient Multi-Robot Search for a Moving Target

Efficient Multi-Robot Search for a Moving Target

Geoffrey Hollinger, Sanjiv Singh, Joseph Djugash and Athanasios Kehagias
Journal Article, Carnegie Mellon University, The International Journal of Robotics Research, Vol. 28, No. 2, pp. 201-219, February, 2009

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


This paper examines the problem of locating a mobile, non-adversarial target in an indoor environment using multiple robotic searchers. One way to formulate this problem is to assume a known environment and choose searcher paths most likely to intersect with the path taken by the target. We refer to this as the Multi-robot E±cient Search Path Planning (MESPP) problem. Such path planning problems are NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We present an approximation algorithm that utilizes finite-horizon planning and implicit coordination to achieve linear scalability in the number of searchers. We prove that solving the MESPP problem requires maximizing a nondecreasing, submodular objective function, which leads to theoretical bounds on the performance of our approximation algorithm. We extend our analysis by considering the scenario where searchers are given noisy non-line-of-sight ranging measurements to the target. For this scenario, we derive and integrate online Bayesian measurement updating into our framework. We demonstrate the performance of our framework in two large-scale simulated environments, and we further validate our results using data from a novel ultra-wideband ranging sensor. Finally, we provide an analysis that demonstrates the relationship between MESPP and the intuitive average capture time metric. Results show that our proposed linearly scalable approximation algorithm generates searcher paths competitive with those generated by exponential algorithms.

BibTeX Reference
title = {Efficient Multi-Robot Search for a Moving Target},
author = {Geoffrey Hollinger and Sanjiv Singh and Joseph Djugash and Athanasios Kehagias},
booktitle = {The International Journal of Robotics Research},
keyword = {multi-robot coordination, autonomous search, approximation algorithms, range-only sensing, decentralized computation, POMDPs},
notes = {The final, definitive version of this paper has been published in The International Journal of Robotics Research, Vol. 28, No. 2, Feb. 2009 by Sage Publications Ltd. All rights reserved. Copyright SAGE Publications Ltd, 2009. It is available at: http://online.sagepub.com/},
publisher = {Sage Publications Ltd},
school = {Robotics Institute , Carnegie Mellon University},
month = {February},
year = {2009},
volume = {28},
number = {2},
pages = {201-219},
address = {Pittsburgh, PA},