Efficient Multi-Robot Search for a Moving Target

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


Download
  • Adobe portable document format (pdf) (560KB)
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.

Abstract
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.

Keywords
multi-robot coordination, autonomous search, approximation algorithms, range-only sensing, decentralized computation, POMDPs

Notes
Associated Center(s) / Consortia: Field Robotics Center
Associated Project(s): EMBER
Number of pages: 19
Note: 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/

Text Reference
Geoffrey Hollinger, Sanjiv Singh, Joseph Djugash, and Athanasios Kehagias, "Efficient Multi-Robot Search for a Moving Target," The International Journal of Robotics Research, Vol. 28, No. 2, March, 2009, pp. 201-219.

BibTeX Reference
@article{Hollinger_2009_6282,
   author = "Geoffrey Hollinger and Sanjiv Singh and Joseph Djugash and Athanasios Kehagias",
   editor = "John Hollerbach",
   title = "Efficient Multi-Robot Search for a Moving Target",
   journal = "The International Journal of Robotics Research",
   pages = "201-219",
   publisher = "Sage Publications Ltd",
   month = "March",
   year = "2009",
   volume = "28",
   number = "2",
   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/"
}