Sensor based coverage of unknown environments

This paper introduces a sensor based coverage algorithm and an overview of a mobile robot sys-tem for demining. The algorithm is formulated in terms of critical points which are the points where the topology of an environment changes. We developed a provably complete coverage algo-rithm which makes a robot pass over all possible points of an unknown environment. Overview of The Coverage Algorithm Conventional path planning determines a path be-tween two points. This type of planning is suitable for guidance, pick and place operations etc.. Applica-tions such as vacuum cleaning, floor scrubbing, area surveying, demining (Land & Choset 1998) and har-vesting (Ollis & Stentz 1996) require more than point to point planning. They require a coverage algorithm which determines a path that passes the robot over all possible points in an environment. In many scenarios, the robot may not know its en-vironment a priori, and thus a sensor based coverage algorithm is necessary. Sensor based coverage deter-mines a path for a robot such that it passes over all possible points in an unknown environment. Com-pleteness of such a coverage algorithm is of utmost importance. As an example, all possible points of a minefield should be covered to guarantee not to miss a single mine. Different types of coverage algorithms were devel-oped by several researchers. Some of the algorithms are grid based (Zelinsky et al. 1993), (Pirzadeh Snyder 1990) and some of them are cellular decom-position based (Cao, Huang, & Hall 1988), (Vladimi