A survey on coverage path planning for robotics <s> 3D Coverage <s> This paper surveys recent results in coverage path planning, a new path planning approach that determines a path for a robot to pass over all points in its free space. Unlike conventional point-to-point path planning, coverage path planning enables applications such as robotic de-mining, snow removal, lawn mowing, car-body painting, machine milling, etc. This paper will focus on coverage path planning algorithms for mobile robots constrained to operate in the plane. These algorithms can be classified as either heuristic or complete. It is our conjecture that most complete algorithms use an exact cellular decomposition, either explicitly or implicitly, to achieve coverage. Therefore, this paper organizes the coverage algorithms into four categories: heuristic, approximate, partial-approximate and exact cellular decompositions. The final section describes some provably complete multi-robot coverage algorithms. <s> BIB001 </s> A survey on coverage path planning for robotics <s> 3D Coverage <s> In spray painting applications, it is essential to generate a spray gun trajectory such that the entire surface is completely covered and receives an acceptably uniform layer of paint deposition; we call this the “uniform coverage” problem. The uniform coverage problem is challenging because the atomizer emits a non-trivial paint distribution, thus making the relationships between the spray gun trajectory and the deposition uniformity complex. To understand the key issues involved in uniform coverage, we consider surface patches that are geodesically convex and topologically simple as representative of subsets of realistic automotive surfaces. In addition to ensuring uniform paint deposition on the surface, our goal is to also minimize the associated process cycle time and paint waste. Based on the relationships between the spray gun trajectory and the output characteristics (i.e., uniformity, cycle time and paint waste), our approach decomposes the coverage trajectory generation problem into three subpro... <s> BIB002
Most coverage path planning methods, and in particular the methods reviewed so far in this article, assume that the environment can be modeled as a simple planar surface. This assumption is valid for floor cleaning, land mine detection, lawn mowing, etc. However, some surfaces in nature are 3-dimensional, and 3-dimensional coverage path planning is required instead to cover these surfaces. This is the case of an autonomous underwater vehicle covering the seabed  or a robot spray-painting vehicle parts BIB002 , for instance. Next, we review several 3-dimensional coverage methods. It is worth noticing that, except the algorithm discussed in Subsec. 8.1, the methods discussed below actually focus on coverage of a surface of lower dimension than the robot's workspace. Indeed, in 3-dimensional coverage, covering 2-dimensional sur-faces embedded in 3-dimensional space such as the boundaries of automotive parts, the boundaries of buildings, the ocean floor, rugged agricultural fields or the boundaries of the in-water part of a ship hull are the main focus. This contrasts with the standard CPP problem, in which all the free space must be covered. 8.1 3D Coverage using a Planar Coverage Algorithm in Successive Horizontal Planes  presented a 3D coverage algorithm that is based on a planar 2-dimensional terrain-covering algorithm  . Their target application is an autonomous underwater vehicle imaging the sea bottom. Their solution applies to a 3D projectively planar environment by applying the planar terrain-covering algorithm in the successive horizontal planes laying at different depths. The restriction to projectively planar environments means that elements such as caves are not handled by this method. Their 2D terrain-covering algorithm uses a partial discretization of the space in where the space is divided in vertical slices of the same width, but where the top and bottom of each slice can have any shape. This discretization is classified as a semi-approximate cellular decomposition according to Choset's taxonomy BIB001 . A robot following this algorithm may start at an arbitrary point in the environment and will zigzag along parallel straight lines (grid lines) to cover the given area. Portions of the area that either would not be covered or would be covered twice using the zigzag procedure are detected by the robot and covered using the same procedure; that is, the procedure is applied recursively. These smaller areas, called inlets, are covered as soon as they are detected and inlets within inlets are treated in the same way. Hence, the inlets are covered in a depthfirst order. By requiring the robot to remember the points at which it enters and exits every inlet it covers (which define the inlet doorways), the algorithm assures that each inlet is covered only once. When entering or exiting a certain type of inlet, the robot may cover the same area more than once, or miss some area at the inlet. Those inlets are called diversion inlets, and special procedures are necessary for covering them effectively. The robot enters a diversion inlet by moving along its boundary. After covering a given diversion inlet, the robot exits it by resuming its path as if the diversion inlet did not exist. When the area to be covered is not simply connected and contains islands as well as inlets, the same basic procedures are used, but with minor modifications to ensure that the area surrounding every island is covered. The robot is able to convert the part of the area around each island that would normally not be covered into an artificial inlet by remembering certain points along its path. Artificial inlets are covered in the same way that real diversion inlets are. Fig. 23 illustrates this procedure. It is worth noticing, however, that details on how to detect the inlets used by the algorithm using sensor information are not provided. The work of  was extended later in ] to cover only areas that are close to the seabottom surface. In this later work, it is assumed that the regions of interest in underwater environments are the ones close to the sea bottom. Therefore, aiming to make the robot navigate only in areas close to the surface, artificial obstacles (artificial islands) are introduced in the robot's map of the environment. This way, the volume of water at a certain distance from the seafloor surface is discarded and a more efficient exploration of the seabottom is achieved. A theoretical proof of correctness of the algorithm is given in  and the extension proposed in ] is validated in simulation.