A survey on coverage path planning for robotics <s> Random Sampling-based Coverage of Complex 3D Structures <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> BIB001 </s> A survey on coverage path planning for robotics <s> Random Sampling-based Coverage of Complex 3D Structures <s> This paper proposes a new inspection planning algorithm, called Random Inspection Tree Algorithm (RITA). Given a perfect model of a structure, sensor specifications, robot's dynamics, and an initial configuration of a robot, RITA computes the optimal inspection trajectory that observes all points on the structure. Many inspection planning algorithms have been proposed, most of them consist of two sequential steps. In the first step, they compute a small set of observation points such that each point on the structure is visible. In the second step, they compute the shortest trajectory to visit all observation points at least once. The robot's kinematic and dynamic constraints are taken into account only in the second step. Thus, when the robot has differential constraints and operates in cluttered environments, the observation points may be difficult or even infeasible to reach. To alleviate this difficulty, RITA computes both observation points and the trajectory to visit the observation points simultaneously. RITA uses sampling-based techniques to find admissible trajectories with decreasing cost. Simulation results for 2-D environments are promising. Furthermore, we present analysis on the probabilistic completeness and asymptotic optimality of our algorithm. <s> BIB002
In confined 3-dimensional areas where a robot cannot go through the spaces between component structures, or where occluded areas are only visible from a reduced set of viewpoints, modular approaches such as those described above are unsuitable. To handle this family of prob-lems, global path planning strategies, utilizing sampling-based planning  have been applied to find feasible, collisionfree, paths through confined areas and obtain full coverage of a 2-dimensional target structure. Their approach is based on the art gallery problem. Building upon a similar idea, BIB001 introduce an off-line, sampling-based coverage algorithm to achieve complete sensor coverage of complex, 3-dimensional structures. Their target application is autonomous ship hull inspection, in which the robot must cover the inwater part of the hull surface using a sensor such as a sonar. The sensory data collected in situ is later used to construct an accurate 3-dimensional model where anomalies in the hull surface can be searched for. They consider the planning problem with a fully-actuated, six degree-of-freedom hovering AUV that uses a bathymetry sonar to inspect the structures in the ship hull. The method requires a discrete model of the structure to be inspected provided in the form of a closed triangular mesh. The planning is performed in two steps. First, a graph of feasible paths for the robot is constructed using random sampling until the set of nodes of the graph allows complete coverage of the structure. This is equivalent to solving a variant of the art gallery problem. Then, a minimumcost closed walk along the graph which fully covers the structure is searched for in the graph. This second step involves solving a variant of the traveling salesman problem. By favoring a random sampling method, they reduce the computational burden necessary to face the high-dimensionality of the problem. It should be noted that the generated paths cover cluttered spaces where complex structures such as shafts and rudders are present. The approach is validated using sensor imagery of real vessels and with experiments conducted at sea. Furthermore, a method for smoothing and shortening the paths initially generated is provided. This procedure can be incrementally applied while computation time allows. Fig. 25 shows examples of planned inspection paths for a ship hull with and without smoothing. As discussed above, the approach by BIB001 first generates a set of view configurations that completely cover the target surface (by solving an instance of the art gallery problem) and then finds a path that connects them (by solving an instance of the traveling salesman problem). This might pose a problem for robots with differential constraints, given that a path connecting to a given view configuration might be infeasible. To tackle this problem, BIB002 presented a random sampling-based algorithm that incrementally explores the robot's configuration space while constructing an inspection path until all points on the target surface are guaranteed to be covered. In contrast to the aforementioned approaches, which first plan a set of view configurations that cover the target environment, their algorithm generates view configurations and at the same time validates the feasibility of the path connecting them. Only view configurations reached by feasible paths are incorporated in the final coverage path. Additionally, this method is probabilistically optimal with respect to a given cost function. The method is validated in simulation. Given the wide variety of structures that are able to handle, these approaches constitute the state of the art in coverage of complex 3-dimensional structures.