This Article Full Text (PDF) Multimedia References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Hollinger, G. Articles by Kehagias, A. Search for Related Content Social Bookmarking                         What's this?

Efficient Multi-robot Search for a Moving Target

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA, gholling{at}ri.cmu.edu

Sanjiv Singh

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA, ssingh{at}ri.cmu.edu

Joseph Djugash

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15217, USA, josephad{at}ri.cmu.edu

Athanasios Kehagias

Division of Mathematics, Department of Mathematics, Physics, and Computer Sciences Aristotle University of Thessaloniki, Thessaloniki GR54124, Greece, kehagiat{at}gen.auth.gr

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 efficient 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 non-decreasing, 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 that are competitive with those generated by exponential algorithms.

Key Words: multi-robot coordination • autonomous search • approximation algorithms • range-only sensing • decentralized computation • POMDPs

The International Journal of Robotics Research, Vol. 28, No. 2, 201-219 (2009)
DOI: 10.1177/0278364908099853


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?