Overview

Next, we consider a different type of representation of the free space called an exact cell decomposition. These structures represent the free space by the union of simple regions called cells. The shared boundaries of cells often have a physical meaning such as a change in the closest obstacle or a change in line of sight to surrounding obstacles. Two cells are adjacent if they share a common boundary. An adjacency graph, as its name suggests, encodes the adjacency relationships of the cells, where a node corresponds to a cell and an edge connects nodes of adjacent cells.

Assuming the decomposition is computed, path planning with a cell decomposition is usually done in two steps: first, the planner determines the cells that contain the start and goal, respectively, and then the planner searches for a path within the adjacency graph. Note that the adjacency graph could serve as a roadmap of the free space as well. Therefore, mapping can be achieved by incrementally constructing the adjacency graph.

Cell decompositions, however, distinguish themselves from other methods in that they can be used to achieve coverage. A coverage path planner determines a path that passes an effector (e.g., a robot, a detector, etc.) over all points in a free space. Since each cell has a simple structure, each cell can be covered with simple motions such as back-and-forth farming maneuvers; once the robot visits each cell, coverage is achieved. In other words, coverage can be reduced to...