Optimal coverage of a known arbitrary environment

The problem of coverage of known space by a mobile robot has many applications. Of particular interest is providing a solution that guarantees the complete coverage of the free space by traversing an optimal path, in terms of the distance travelled. In this paper we introduce a new algorithm based on the Boustrophedon cellular decomposition. The presented algorithm encodes the areas (cells) to be covered as edges of the Reeb graph. The optimal solution to the Chinese Postman Problem (CPP) is used to calculate an Euler tour, which guarantees complete coverage of the available free space while minimizing the path of the robot. In addition, we extend the classical solution of the CPP to account for the entry point of the robot for cell coverage by changing the weights of the Reeb graph edges. Proof of correctness is provided together with experimental results in different environments.

I. Introduction

The task of covering a bounded region of space is common to many problems such as de-mining, vacuum cleaning, lawn mowing and automated painting. One coverage application that has proven to be extremely successful is the task of robotic vacuum cleaning. The iRobot¹

http://www.irobot.com/

Roomba vacuum cleaning robot uses a variety of different strategies, such as random walk, wall-following, and the seed-spreader algorithm [1], to achieve, probabilistically, coverage of the whole floor space. The sale of more than two million robots highlights the importance and impact of this application. In the above described applications the problem of robotic coverage of free space is defined as follows: the robot has to pass an end effector, or a sensor, which in most cases is the body of the mobile robot, over all available free space. For example, during mine detection, the robot has to ensure that every location that is not covered by an obstacle is inspected and the position of the discovered mines recorded. In such an application it is of paramount importance to ensure completeness; no accessible area should be left uncovered.