The Robotics Institute

Carnegie Mellon Robotics Institute

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

In this paper, we examine the problem of locating a non-adversarial target using multiple robotic searchers. This problem is relevant to many applications in robotics including emergency response and aerial surveillance. Assuming a known environment, this problem becomes one of choosing searcher paths that are 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 a finite-horizon path enumeration algorithm for solving the MESPP problem that utilizes sequential allocation to achieve linear scalability in the number of searchers. We show that solving the MESPP problem requires the maximization of a nondecreasing, submodular objective function, which directly leads to theoretical guarantees on paths generated by sequential allocation. We also demonstrate how our algorithm can run online to incorporate noisy measurements of the target's position during search. We verify the performance of our algorithm both in simulation and in experiments with a novel radio sensor capable of providing range through walls. Our results show that our linearly scalable MESPP algorithm generates searcher paths competitive with those generated by exponential algorithms.

Notes

Associated Center(s) / Consortia: Field Robotics Center

Associated Project(s): EMBER

Number of pages: 8

Note: Accompanying video: http://www.frc.ri.cmu.edu/projects/emergencyresponse/movies/HollingerRSS08.mpg

Text Reference

Geoffrey Hollinger and Sanjiv Singh, "Proofs and Experiments in Scalable, Near-Optimal Search by Multiple Robots," Robotics: Science and Systems, June, 2008.

BibTeX Reference

@inproceedings{Hollinger_2008_6084,
   author = "Geoffrey Hollinger and Sanjiv Singh",
   title = "Proofs and Experiments in Scalable, Near-Optimal Search by Multiple Robots",
   booktitle = "Robotics: Science and Systems",
   month = "June",
   year = "2008",
   Notes = "Accompanying video: http://www.frc.ri.cmu.edu/projects/emergencyresponse/movies/HollingerRSS08.mpg"
}

The Robotics Institute

Menu