A survey on coverage path planning for robotics <s> 3-dimensional Coverage <s> Field operations should be done in a manner that minimizes time and travels over the field surface and is coordinated with topographic land features. Automated path planning can help to find the best coverage path so that the field operation costs can be minimized. Intelligent algorithms are desired for both two-dimensional (2D) and three-dimensional (3D) terrain field coverage path planning. The algorithm of generating an optimized full coverage pattern for a given 2D planar field by using boustrophedon paths has been investigated and reported before. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations. This work addressed four critical tasks: terrain modeling and representation, coverage cost analysis, terrain decomposition, and the development of optimized path searching algorithm. The developed algorithms and methods have been successfully implemented and tested using 3D terrain maps of farm fields with various topographic features. Each field was decomposed into subregions based on its terrain features. A recommended “seed curve” based on a customized cost function was searched for each subregion, and parallel coverage paths were generated by offsetting the found “seed curve” toward its two sides until the whole region was completely covered. Compared with the 2D planning results, the experimental results of 3D coverage path planning showed its superiority in reducing both headland turning cost and soil erosion cost. On the tested fields, on average the 3D planning algorithm saved 10.3% on headland turning cost, 24.7% on soil erosion cost, 81.2% on skipped area cost, and 22.0% on the weighted sum of these costs, where their corresponding weights were 1, 1, and 0.5, respectively. © 2011 Wiley Periodicals, Inc. © 2011 Wiley Periodicals, Inc. <s> BIB001 </s> A survey on coverage path planning for robotics <s> 3-dimensional 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> BIB002 </s> A survey on coverage path planning for robotics <s> 3-dimensional Coverage <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> BIB003
Planar terrain covering algorithm applied at successive depths  On-line Projectively planar (2.5D) Theoretically proven, however no details on how to detect the inlets used by the algorithm are provided. 3D cellular decomposition On-line Closed, orientable surfaces embedded in R 3 Theoretically proven. Demonstrated in simulation for simple 3D surfaces (polyhedra). Hierarchical segmentation of pseudo-extruded surfaces  Off-line Car-like parts (pseudo-extruded surfaces) Specifically targeted for coverage of automotive parts. Generates paths which optimize paint deposition uniformity. Coverage path generation on simplified 3D surfaces  On-line Urban environments simplified as hemispheres and cylinders Suitable for covering urban structures with sufficient clearance between them. Coverage of Bathymetric Surfaces Off-line Bathymetric (elevation) maps Provides fair imaging angles on rugged terrain. Coverage for Arable Farming BIB001 Off-line Elevation maps Minimizes application-specific costs. Random sampling-based BIB002 Off-line Complex 3D structures Allows for coverage of complex 3-dimensional structures such as a ship propeller. Random sampling-based with differential constraints BIB003 Off-line Complex 3D structures Can handle differential constraints and probabilistically guarantees optimality.