A Coverage Algorithm for Multi-robot Boundary Inspection
- Creators
- Easton, Kjerstin
- Burdick, Joel W.
Abstract
This paper introduces the multi-robot boundary coverage problem, wherein a group of k robots must inspect every point on the boundary of a 2-dimensional test environment. Using a simplified sensor model, this inspection problem is converted to an equivalent graph representation. In this representation, the coverage problem can be posed as the k- Rural Postman Problem (kRPP). We present a constructive heuristic which finds a solution to the kRPP, then use that solution to plan the robots' inspection routes. These routes provide complete coverage of the boundary and also balance the inspection load across the k robots. Simulations illustrate the algorithm's performance and characteristics.
Additional Information
© 2005 IEEE. Issue Date: 18-22 April 2005. Date of Current Version: 10 January 2006. This work has been supported by a National Science Foundation fellowship, a grant from NASA Glenn, and by NSF grants NSF-0428075 and NSF-0325017. The authors would like thank Elon Rimon and Eric Klavins for valuable discussions regarding graph-based approaches to multi-robot coverage and Howie Choset for the use of his planar GVG construction software, which was the basis for the graph construction step in our simulations.Attached Files
Published - Easton2005p95222008_Ieee_International_Conference_On_Robotics_And_Automation_Vols_1-9.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:5281fb95cb3f79ea8f96773719544583
|
702.9 kB | Preview Download |
Additional details
- Eprint ID
- 24535
- Resolver ID
- CaltechAUTHORS:20110725-155321248
- NSF Graduate Research Fellowship
- NSF
- CMMI-0428075
- NSF
- CNS-0325017
- Created
-
2011-07-27Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field