|
|
|
|
RI | Publications | Proofs and Experiments in Scalable, Near-Optimal Search by Multiple Robots
|
|
Text only version of this site
Proofs and Experiments in Scalable, Near-Optimal Search by Multiple Robots
G. Hollinger and S. Singh
Robotics: Science and Systems, June, 2008.
Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference
| Download [Help] |
Adobe portable document format (pdf) [414 KB]
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: FRC
Associated project: EMBER
Number of pages: 8
Note: Accompanying video: http://www.frc.ri.cmu.edu/projects/emergencyresponse/movies/HollingerRSS08.mpg
| Text Reference |
G. Hollinger and S. 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",
note = "Accompanying video: http://www.frc.ri.cmu.edu/projects/emergencyresponse/movies/HollingerRSS08.mpg"
}