A survey on coverage path planning for robotics <s> Classical Exact Cellular Decomposition Methods <s> Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applica­ tions include vacuuming, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cel­ lular decomposition approach, for the purposes of coverage. Each cell in the boustrophedon is covered with simple back and forth motions. Once each cell is covered, then the entire envi­ ronment is covered. Therefore, coverage is re­ duced to finding an exhaustive path through a graph which represents the adjacency relation­ ships of the cells in the boustrophedon decom­ position. This approach is provably complete and Experiments on a mobile robot validate this approach. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Classical Exact Cellular Decomposition Methods <s> Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of 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. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo... <s> BIB002
Exact cellular decomposition methods break the free space (i.e., the space free of obstacles) down into simple, non-overlapping regions called cells. The union of all the cells exactly fills the free space. These regions, where no obstacles lay in, are "easy" to cover and can be swept by the robot using simple motions. For instance, each cell could be covered using a zigzag, "mowing the lawn" pattern like the one shown in Fig. 1 . Generation of these zigzag motions, also called Seed Spreader motions, is well documented in the literature  BIB001 BIB002 . Figure 1: Typical zigzag path. Shaded area indicates the area covered already (darker) and the area that will be covered (lighter) when the robot finishes following the zigzag path. Two cells are said to be adjacent if they share a common boundary. An adjacency graph can be used to represent the cellular decomposition, where a node represents a cell and an edge represents an adjacency relationship between two cells (see Fig. 2 ). Exact cell decompositions can be generated by sweeping a line through the space (e.g. from left to right). The cell boundaries are then formed when some event is encountered by the sweep line. For instance, a change on the number of times the sweep line intersects with obstacle boundaries can be used as an event. Typically, a planner based on exact cellular decomposition generates a coverage path in two steps. First, it decomposes the free space into cells and stores the decomposition as an adjacency graph. Next, it computes an exhaustive walk through the adjacency graph (i.e., a sequence that visits each node in the graph exactly once). It is worth noting that the exhaustive walk obtained is a sequence of nodes (i.e., a sequence of cells), and not an actual coverage path. Therefore, an explicit path for covering each cell must be derived. Next, two popular off-line cellular decomposition approaches (Subsec. 2.1 and Subsec. 2.2) that laid down the foundations for more novel approaches are discussed.