A survey on coverage path planning for robotics <s> Trapezoidal Decomposition <s> 1 Introduction and Overview.- 2 Configuration Space of a Rigid Object.- 3 Obstacles in Configuration Space.- 4 Roadmap Methods.- 5 Exact Cell Decomposition.- 6 Approximate Cell Decomposition.- 7 Potential Field Methods.- 8 Multiple Moving Objects.- 9 Kinematic Constraints.- 10 Dealing with Uncertainty.- 11 Movable Objects.- Prospects.- Appendix A Basic Mathematics.- Appendix B Computational Complexity.- Appendix C Graph Searching.- Appendix D Sweep-Line Algorithm.- References. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Trapezoidal Decomposition <s> In this article, a coverage path planning problem is discussed in the case of agricultural fields and agricultural machines. Methods and algorithms to solve this problem are developed. These algorithms are applicable to both robots and human-driven machines. The necessary condition is to cover the whole field, and the goal is to find as efficient a route as possible. As yet, there is no universal algorithm or method capable of solving the problem in all cases. Two new approaches to solve the coverage path planning problem in the case of agricultural fields and agricultural machines are presented for consideration. Both of them are greedy algorithms. In the first algorithm the view is from on top of the field, and the goal is to split a single field plot into subfields that are simple to drive or operate. This algorithm utilizes a trapezoidal decomposition algorithm, and a search is developed of the best driving direction and selection of subfields. This article also presents other practical aspects that are taken into account, such as underdrainage and laying headlands. The second algorithm is also an incremental algorithm, but the path is planned on the basis of the machine's current state and the search is on the next swath instead of the next subfield. There are advantages and disadvantages with both algorithms, neither of them solving the problem of coverage path planning problem optimally. Nevertheless, the developed algorithms are remarkable steps toward finding a way to solve the coverage path planning problem with nonomnidirectional vehicles and taking into consideration agricultural aspects. © 2009 Wiley Periodicals, Inc. <s> BIB002
One of the simplest exact cellular decomposition techniques which can yield a complete coverage path is the trapezoidal decomposition BIB001  , which handles only planar, polygonal spaces. This method can be classified as off-line. In the trapezoidal decomposition, each cell is a trapezoid, as shown in Fig. 2 . Thereby, simple back-and-forth motions can be used to cover each cell. Complete coverage is guaranteed by finding an exhaustive walk through the adjacency graph associated to the decomposition (overlaid on the decomposition in Fig. 2 ). Finally, a specific zigzag path to cover each cell is generated. The exhaustive walk determines the order in which the cells are visited to achieve complete coverage. Finally, specific paths to cover each cell are generated, typically using back-and-forth motions in a "mowing the lawn" manner. As an application example, BIB002 proposed an off-line algorithm based on the trapezoidal decomposition for coverage path planning in the case of agricultural fields and agricultural machines. Their algorithm applies a trapezoidal decomposition of the field followed by a cell merging procedure. The resulting cells are similar to those produced by the boustrophedon decomposition, introduced in the next section (2.2). To optimize the path, they use a path-based cost function to assess the largest cell arising in six different trapezoidal decompositions obtained by using a sweep line inclinated at 30 • intervals. Then, the three most favorable directions are selected and the process is repeated, with additional decompositions at 15 • either side of the selected headings. The process continues iteratively until the improvement per step falls below a threshold, which for their application was achieved after 5 steps (about 1 • accuracy), requiring 36 separate decompositions. Then, the largest cell in the minimum-cost decomposition is removed from the target area, and the process is repeated for the remainder of the field until all the area is covered by the path. This scheme produces effectively optimal coverage paths for a convex field and highquality paths for a field whose boundaries consist of long, straight segments as well.