CCR: A Complete Algorithm for Contact-Sensor Based Coverage of Rectilinear Environments

October 1998

CCR: A Complete Algorithm for Contact-Sensor Based Coverage of Rectilinear Environments

Authors:

Zack Butler
Technical Report
CMU-RI-TR-98-27

Abstract:

Sensor-based coverage is a powerful tool for robots to use to discover their environment, especially in cases when complete knowledge of the environment is required. Current methods have demonstrated the ability to cover virtually arbitrary planar areas but require a remote sensor of finite range, such as sonar. The work presented here handles the case of robots that use only contact sensing to determine the boundaries of their environment. An algorithm CCR is presented that works in a wide range of rectilinear geometries. A proof of completeness is presented for CCR which shows that it always causes the robot executing it to cover its environment. Also, possible extensions of CCR to incorporate a wider variety of environments are discussed.
@techreport{Butler-1998-14790,
author = {Zack Butler},
title = {CCR: A Complete Algorithm for Contact-Sensor Based Coverage of Rectilinear Environments},
year = {1998},
month = {October},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-98-27},
}
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.