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

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.