A survey on coverage path planning for robotics <s> Conclusion <s> A variety of mobile robot tasks require complete coverage of an initially unknown environment, either as the entire task or as a way to generate a complete map for use during further missions. This is a problem known as sensor-based coverage, in which the robot's sensing is used to plan a path that reaches every point in the environment. A new algorithm, CC/sub R/, is presented here which works for robots with only contact sensing that operate in environments with rectilinear boundaries and obstacles. This algorithm uses a high-level rule-based feedback structure to direct coverage rather than a script in order to facilitate future extensions to a team of independent robots. The outline of a completeness proof of CC/sub R/ is also presented, which shows that it produces coverage of any of a large class of rectilinear environments. Implementation of CC/sub R/ in simulation is discussed, as well as the results of testing in a variety of world geometries and potential extensions to the algorithm. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Conclusion <s> In applications such as vacuum cleaning, painting, demining and foraging, a mobile robot must cover an unknown surface. The efficiency and completeness of coverage is improved via the construction of a map of covered regions while the robot covers the surface. Existing methods generally use grid maps, which are susceptible to odometry error and may require considerable memory and computation. This paper proposes a topological map and presents a coverage algorithm in which natural landmarks are added as nodes in a partial map. The completeness of the algorithm is argued. Simulation tests show over 99% of the surface is covered; 85% for real (Khepera) robot tests. The path length is about 10% worse than optimal in simulation tests, and about 20% worse than optimal for the real robot, which are within theoretical upper bounds for approximates solutions to traveling salesman based coverage problems. The proposed algorithm generates shorter paths and covers a wider variety of environments than topological coverage based on Morse decompositions. <s> BIB002
In this paper, we have seen that the coverage path planning problem has been addressed using many different approaches. For planar spaces, the trapezoidal decomposition guarantees complete coverage for a known polygonal environment. An improvement to the trapezoidal decomposition is the "classical" boustrophedon decomposition, which generates shorter complete coverage paths for the same class of environments. The Morse-based cellular decomposition provides complete coverage paths for environments whose obstacle boundaries are differentiable. A method to detect the critical points that determine the cell boundaries using range sensor information allows to perform Morse-based cellular decomposition coverage online. Furthermore, Morse decomposition allows generation of different coverage patterns, such as spiral patterns, that can simplify the path following to vehicles with motion constraints. However, the Morse-based cellular decomposition method cannot handle rectilinear environments, and the cyclic rectangular paths used to detect all the critical points include retracing, which makes them longer than a standard zigzag path. This limitations are overcome by the landmark-based topological coverage approach. This method uses a cellular decomposition based on natural landmarks of the environment which determine the cell boundaries. An algorithm is given to perform coverage on-line on unknown environments using this technique. For the particular case of robots with only contact sensors (i.e., with no range sensing capabilities) operating in rectilinear environments, the CC R algorithm guarantees complete on-line coverage. Grid-based methods such as the wavefront algorithm, the Spiral-STC algorithm and its derivatives, and the described neural-network-based and hexagonal decomposition approaches, provide complete coverage on a discretized representation of the target environment. However, the grid representation of the environment used is highly sensitive to localization error and incurs an exponential memory consumption. On the other hand, it is easy to create and operate with a grid map. It is worth noticing, as a unique capability among the reviewed methods, that the discussed neural network-based methods are able to handle environments with moving obstacles. Some methods aimed to cover 3-dimensional environments have been reviewed. Hert's algorithm can completely cover projectively planar 3-dimensional environments. However, details on how to detect the inlets used by the algorithm using sensor data are not provided, making it difficult to implement. Modular approaches, such as the coverage methods targeted for spraypainting tasks proposed by Atkar et al. or the simplified model of a urban environment used by Cheng et al. can achieve complete coverage of certain 3-dimensional environments. The method for coverage of bathymetric surfaces by Galceran et al. and the coverage algorithm for arable farming by Jin et al. provide coverage of 3-dimensional environments taking into account application-specific constraints. However, in confined 3-dimensional areas where a robot cannot go through the spaces between component structures, or occluded areas only visible from a reduced set of viewpoints, these modular approaches do not suffice. To overcome this limitation, Englot et al. introduced a sampling-based coverage algorithm to achieve complete sensor coverage of complex, 3-dimensional structures. The paths generated using this method are able to cover cluttered spaces where complex structures such as shafts and rudders are present. The approach is validated using triangular mesh models constructed using sensor imagery of real-world vessels. Also building upon the idea of samplingbased coverage, Papadopoulos et al. presented an algorithm that generates coverage paths for complex 3-dimensional structures suitable for vehicles with differential constraints. Furthermore, their algorithm is proven probabilistically optimal with respect to a given cost function. This approaches constitute the state of the art in coverage of complex 3-dimensional structures. We have discussed several approaches to generate optimal coverage paths in planar spaces and to reduce localization error while performing coverage. Finally, we have reviewed some multi-robot coverage methods in which time to completion is reduced by dividing the workload among the individual robot team members, besides providing increased robustness guarantees. The features of the most relevant CPP methods reviewed in this article are summarized in Table 1. For each method (rows), the table underlines (columns from left to right) its category, its approach, its main bibliographical reference, whether it can be used on-line or not, the kind of environments it can handle and some remarks. Probabilistic sampling-based algorithms have revolutionized the state of the art in path planning in the recent years, and they have proven to be extremely powerful as demonstrated in the work by Englot et al. on ship hull inspection. Therefore, exploiting these techniques opens the door to developing algorithms able to realize coverage tasks of unprecedented complexity. On the other hand, in real-world applications, a robot often does not have perfect knowledge about its location. In this situation, incorporating uncertainty in future location estimates in the planning phase can significantly improve motion performance. Although several research works have explored taking uncertainty into account in path planning problems, few attention has been given to incorporating uncertainty in coverage path planning methods. BIB002 On-line Generic planar obstacles Handles a large variety of environments (including rectilinear environments). Contact Sensorbased Coverage Rectilinear decomposition (CC R algorithm) BIB001 On-line Rectilinear Targeted for robots equipped only with contact sensors.