A Caltech Library Service

A Coverage Algorithm for Multi-robot Boundary Inspection

Easton, Kjerstin and Burdick, Joel W. (2005) A Coverage Algorithm for Multi-robot Boundary Inspection. In: 2005 IEEE International Conference on Robotics and Automation (ICRA). IEEE , Piscataway, NJ, pp. 727-734. ISBN 0-7803-8914-X.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Subject Keywords:robot coverage; multiple robots; planning algorithms
Record Number:CaltechAUTHORS:20110725-155321248
Persistent URL:
Official Citation:Easton, K.; Burdick, J.; , "A Coverage Algorithm for Multi-robot Boundary Inspection," Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on , vol., no., pp. 727- 734, 18-22 April 2005 doi: 10.1109/ROBOT.2005.1570204 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24535
Deposited By: Tony Diaz
Deposited On:27 Jul 2011 23:16
Last Modified:09 Nov 2021 16:24

Repository Staff Only: item control page