A survey on coverage path planning for robotics <s> Boustrophedon Decomposition <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> Boustrophedon Decomposition <s> 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. <s> BIB002
A drawback of the trapezoidal decomposition is that it generates many cells that, intuitively, can be merged together to form bigger cells. This is clearly inconvenient, as the more cells are present, the longer the final coverage path becomes, as shown in Fig. 3 . This happens because the trapezoidal decomposition creates only convex cells. However, non-convex cells can also be completely covered by simple motions. To overcome this limitation, Choset & Pignon proposed the boustrophedon cellular decomposition BIB001 BIB002 . The word "boustrophedon" comes from ancient Greek, and literally means "the way of the ox", signifying the pattern in which an ox drags a plough back and forth. The boustrophedon decomposition is similar to the trapezoidal decomposition introduced above, but it only considers vertices where a vertical segment can be extended both above and below the vertex. The vertices where this occurs are called critical points. By adhering to this strategy, the boustrophedon decomposition effectively reduces the number of cells in trapezoidal decomposition. Hence, shorter coverage paths are obtained. Notice that, as the trapezoidal decomposition, this method assumes polygonal obstacles and the terrain to be known a priori, and thus classifies as an off-line method.