Coverage path planning determines a path that passes a robot, a detector, or some type of effector over all points in the environment. Prior work in coverage tends to fall into one of two extremes: coverage with an effector the same size of the robot, and coverage with an effector that has infinite range. In this paper, we consider coverage in the middle of this spectrum: coverage with a detector range that goes beyond the robot, and yet is still finite in range. We achieve coverage in two steps: The first step considers vast, open spaces, where the robot can use the full range of its detector; the robot covers these spaces as if it were as big as its detector range. Here we employ previous work in using Morse cell decompositions to cover unknown spaces. A cell in this decomposition can be covered via simple back-and-forth motions, and coverage of the vast space is then reduced to ensuring that the robot visits each cell in the vast space. The second step considers the narrow or cluttered spaces where obstacles lie within detector range, and thus the detector "fills" the surrounding area. In this case, the robot can cover the cluttered space by simply following the generalized Voronoi diagram (GVD) of that space. In this paper, we introduce a hierarchical decomposition that combines the Morse decompositions and the GVDs to ensure that the robot indeed visits all vast, open, as well as narrow, cluttered, spaces. We show how to construct this decomposition online with sensor data that is accumulated while the robot enters the environment for the first time.

This paper presents a planner that determines a path such that the robot does not have to heavily rely on odometry to reach its goal. The planner determines a sequence of obstacle boundaries that the robot must follow to reach the goal. Since this planner is used in the context of a coverage algorithm already presented by the authors, we assume that the free space is already, completely or partially, represented by a cellular decomposition whose cell boundaries are defined by critical points of Morse functions (isolated points at obstacle boundaries). The topological relationship among the cells is represented by a graph where nodes are the critical points and edges connect the nodes that define a common cell (i.e., the edges correspond to the cells themselves). A search of this graph yields a sequence of cells that directs the robot from a start to a goal. Once a sequence of cells and critical points are determined, a robot traverses each cell by mainly following the boundary of the cell along the obstacle boundaries and minimizes the accumulated dead-reckoning error at the intermediate critical points. This allows the robot to reach the goal robustly even in the presence of dead-reckoning error.

We address the task of covering a closed orientable surface embedded in /spl Rfr//sup 3/ without any prior information about the surface. For applications such as paint deposition, the effector (the paint atomizer) does not explicitly cover the target surface, but instead covers an offset surface-a surface that is a fixed distance away from the target surface. Just as Canny and others use critical points to look for changes in connectivity of the free space to ensure completeness of their roadmap algorithms, we use critical points to identify changes in the connectivity of the offset surface to ensure full surface coverage. The main contribution of this work is a method to construct unknown offset surfaces using a procedure, also developed in this paper, to detect critical points.

Sensor-based coverage uses sensor information to determine a path that passes a detector or some effectors over all points in an unknown space. This work identifies features of a provably complete coverage algorithm to reject "bad" sensor readings in unstructured environments without performing complicated sensor-data processing. First, we briefly review our provably complete sensor-based coverage algorithm that uses an exact cellular decomposition in terms of critical points of Morse functions. Then we present features of the algorithm that are used to overcome failures due to bad sensor data. We verified our approach by performing experiments using a mobile robot that has 16 ultrasonic sensors.

Sensor-based coverage uses sensor information to determine a path that passes a detector over all points in an unknown space. Our prior work in coverage prescribed a path for a circular robot of radius r to pass over all points in unknown spaces; in this case we set the detector range /spl delta/ to be equal to the robot's radius, r. Our prior work in Voronoi diagrams prescribed a path for a circular robot with infinite detector range (/spl delta/=/spl infin/) to pass its detector over all points in an unknown bounded space. This work combines these, results to consider "efficient" coverage with a finite-range detector with r</spl delta/

One way to improve the efficiency of mine search, compared with a complete coverage algorithm, is to direct the search based on the spatial distribution of the minefield. The key for the success of this probabilistic approach is to efficiently extract the spatial distribution of the minefield during the process of the search. In our research, we assume that a minefield follows a regular pattern, which belongs to a family of known patterns. A Bayesian approach to the pattern extraction is developed to extract the underlying pattern of the minefield. The algorithm performs well in its ability to catch the "actual" pattern in the situation where placement and detector errors exist, and the algorithm is efficient, therefore, online implement of the algorithm on a mobile robot is possible. Compared to the likelihood approach, the advantage of using a Bayesian approach is that this approach provides information about the uncertainty of the extracted "actual" pattern.

Many motion planning algorithms use Morse functions to characterize the free space. Specifically, these algorithms look at the critical points of a Morse function to denote the topological changes in the free space. This paper introduces methods to sense critical points and ensure all critical points are "seen" by a coverage algorithm. Experimental results performed on a mobile robot are also presented.

Exact cellular decompositions are structures that globally encode the topology of a robot's free space, while locally describing the free space geometry. These structures have been widely used for path planning between two points, but can be used for mapping and coverage of robot free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. In this paper, we derive a general framework for defining decompositions in terms of critical points and then give examples, each corresponding to a different task. All of the results in this paper are derived in an m-dimensional Euclidean space, but the examples depicted in the figures are 2D and 3D for ease of presentation.