A survey on coverage path planning for robotics <s> Optimal Coverage <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> Optimal Coverage <s> Robotic coverage is the problem of moving a sensor or actuator over all points in given region. Ultimately, we want a coverage path that minimizes some cost such as time. We take the approach of decomposing the coverage region into subregions, selecting a sequence of those subregions, and then generating a path that covers each subregion in turn. We focus on generating decompositions based upon the planar line sweep. After a general overview of the coverage problem, we describe how our assumptions lead to the optimality criterion of minimizing the sum of subregion altitudes (which are measured relative to the sweep direction assigned to that subregion). For a line-sweep decomposition, the sweep direction is the same for all subregions. We describe how to find the optimal sweep direction for convex polygonal worlds. We then introduce the minimal sum of altitudes (MSA) decomposition in which we may assign a different sweep direction to each subregion. This decomposition is better for generating an optimal coverage path. We describe a method based on multiple line sweeps and dynamic programming to generate the MSA decomposition. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Optimal Coverage <s> Path planning problems involve computing or finding a collision free path between two positions. A special kind of path planning is complete coverage path planning, where a robot sweeps all area of free space in an environment. There are different methods to cover the complete area; however, they are not designed to optimize the process. This paper proposes a novel method of complete coverage path planning based on genetic algorithms. In order to check the viability of this approach the optimal path is tested in a virtual environment. The simulation results confirm the feasibility of this method. <s> BIB003 </s> A survey on coverage path planning for robotics <s> Optimal Coverage <s> The problem of coverage of known space by a mobile robot has many applications. Of particular interest is providing a solution that guarantees the complete coverage of the free space by traversing an optimal path, in terms of the distance travelled. In this paper we introduce a new algorithm based on the Boustrophedon cellular decomposition. The presented algorithm encodes the areas (cells) to be covered as edges of the Reeb graph. The optimal solution to the Chinese Postman Problem (CPP) is used to calculate an Euler tour, which guarantees complete coverage of the available free space while minimizing the path of the robot. In addition, we extend the classical solution of the CPP to account for the entry point of the robot for cell coverage by changing the weights of the Reeb graph edges. Proof of correctness is provided together with experimental results in different environments. <s> BIB004 </s> A survey on coverage path planning for robotics <s> Optimal Coverage <s> We present the adaptation of an optimal terrain coverage algorithm for the aerial robotics domain. The general strategy involves computing a trajectory through a known environment with obstacles that ensures complete coverage of the terrain while minimizing path repetition. We introduce a system that applies and extends this generic algorithm to achieve automated terrain coverage using an aerial vehicle. Extensive experimental results in simulation validate the presented system, along with data from over 100 kilometers of successful coverage flights using a fixed-wing aircraft. <s> BIB005 </s> A survey on coverage path planning for robotics <s> Optimal Coverage <s> We present several new contributions in sampling-based coverage path planning, the task of finding feasible paths that give 100% sensor coverage of complex structures in obstacle-filled and visually occluded environments. First, we establish a framework for analyzing the probabilistic completeness of a sampling-based coverage algorithm, and derive results on the completeness and convergence of existing algorithms. Second, we introduce a new algorithm for the iterative improvement of a feasible coverage path; this relies on a sampling-based subroutine that makes asymptotically optimal local improvements to a feasible coverage path based on a strong generalization of the RRT* algorithm. We then apply the algorithm to the real-world task of autonomous in-water ship hull inspection. We use our improvement algorithm in conjunction with redundant roadmap coverage planning algorithm to produce paths that cover complex 3D environments with unprecedented efficiency. <s> BIB006
Work addressing the optimality of the generated coverage paths, in terms such as path length and time to completion, appears in the CPP literature. Notice that it is only possible to find an optimal solution for an a priori known environment, or partially known at least, since an antagonistic example can always be found for a sensor-based approach. Hence optimal coverage methods are classified as off-line methods. Huang presented an optimal line-sweep based method for cellular decomposition algorithms in planar spaces BIB002 . This approach produces an optimal length coverage path by allowing different sweep directions in the lawnmower paths used to cover each cell. The main idea is to mini- Figure 25: Full-coverage inspection paths obtained with the method in BIB006 . mize the number of turns in the path, as each turn typically implies the added cost of the robot decelerating and accelerating again after the turn. This is achieved by allowing a different sweep direction in each cell. The number of turns is minimized by sweeping each cell in parallel to its maximal altitude axis. That is, the method intends to maximize the length of the laps in the zigzag pattern in order to minimize the number of turns. However, this approach does not take into account the cost of traveling from cell to cell. The method is validated in simulation. [ BIB003 proposed to use a genetic algorithm to achieve optimal coverage. In this proposal, workspace and obstacles are assumed to be polygonal and known beforehand. Then, the free space is divided in subregions using the trapezoidal cellular decomposition method BIB001  . Finally, a genetic algorithm is used to plan an optimal path that covers all the subregions. This proposal is tested in simulation. Mannadiar and Rekleitis proposed an algorithm based on the Boustrophedon cellular decomposition that achieves complete coverage of known spaces while minimizing the path of the robot BIB004 . The algorithm encodes the cells to be covered as edges of the Reeb graph. Then, the optimal solution to the Chinese Postman Problem is used to calculate an Euler tour, which guarantees complete coverage of the available free space while minimizing the coverage path length. [ BIB005 presented an application of the optimal Morse-based boustrophedon decomposition method BIB004 for unmanned aerial vehicles (UAVs). First, they generate an optimal exhaustive walk through the adjacency graph of the cell decomposition of the terrain. Then, they cover each cell with zigzag motions taking into account the kinematic constraints of the vehicle, as the fixed-wing UAV they use has non-holonomic constraints. Extensive experimental results in simulation validate the presented system, along with data from over 100 kilometers of coverage flights using a real fixed-wing aircraft. Cell decomposition with variable sweep direction BIB002 Off-line Polygonal Takes into account "cell height" to select the optimal sweep direction. Trapezoidal decomposition + genetic algorithm BIB003 Off-line Polygonal A genetic algorithm quickly finds a specific coverage paths among the cells. Morse decomposition + optimal adjacency graph traversal BIB004 On-line Polygonal and differentiable boundaries (nonrectilinear) Finds an optimal walk through the adjacency graph.