A survey on coverage path planning for robotics <s> Introduction <s> A small and lightweight cleaning robot powered from the AC power supply is produced for testing purposes. The robot provides a cable-length control function which prevents tangling of the cables during traveling, an ultrasonic sensor function which detects obstacles and dodges them, and a distance measuring function which makes it possible to run parallel to the wall. In a simple room with few obstacles, the robot can travel even if it does not incorporate information but in areas with complicated placement of obstacles, it is necessary to teach the robot the obstacle positions and the room size in advance. > <s> BIB001 </s> A survey on coverage path planning for robotics <s> Introduction <s> The article presents a new topic in path planning for mobile robots, region filling. which involves a sweeping operation to fill a whole region with random obstacle avoidance. The approaches for global strip filling and local path searching driven by sensory data procedures are developed. A computer graphic simulation is used to verify the filling strategy available. The research was developed from the program for the design of a robot lawn mower. However, the solution appears generic. The significance is that a problem of wide application and generic solutions for general autonomous mobile robots have been developed. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Introduction <s> In this paper we present an O(n4, log logn) algorithm to find a shortest watchman route in a simple polygon through a point,s, in its boundary. A watchman route is a route such that each point in the interior of the polygon is visible from at least one point along the route. <s> BIB003 </s> A survey on coverage path planning for robotics <s> Introduction <s> In two previous papers we explored some of the systems aspects of applying large numbers of inexpensive robots to real world applications. The concept of coverage can help the user of such a system visualize its overall function and performance in mission-relevant terms, and thereby support necessary system command control functions. An important class of coverage applications are those that involve a search, in which a number of searching elements move about within a prescribed search area in order to find one or more target objects, which may be stationary or mobile. A simple analytical framework was employed in the previous work to demonstrate that the design of a cost-effective many-robot search system can depend sensitively on the interplay of sensor cost and performance levels with mission-specific functional and performance requirements. In the current paper we extend these results: we consider additional measures of effectiveness for area search systems to provide a broader basis for a tradeoff of coordinated versus random search models, and we explore how to deliberately achieve effectively randomized search strategies that provide uniform search coverage over a specified area. <s> BIB004 </s> A survey on coverage path planning for robotics <s> Introduction <s> Window cleaning is a two-stage process; application of cleaning fluid, which is usually achieved by using a wetted applicator and removal of cleaning fluid by a squeegee blade without spillage on to other areas of the facade or previously cleaned areas of glass. This is particularly difficult for example if the window is located on the roof of a building and cleaning is performed from inside by the human window cleaner. Simulation studies were conducted to demonstrate the feasibility of a robot system to act and mimic the human operator; an end effector had to be designed to accommodate different tools such as applicator and squeegee; the pay load for tool handling, sensory feedback requirements; force and compliance control; and finally the cost of the overall system had to be feasible. As a result of the studies it was conceived that the end effector should contain a combined datuming/cleaning head. This arrangement would allow automatic datuming and location of the window pane relative to the robot using a specially designed and constructed compliant head. One advantage of a combined head being the elimination of tool changes between the datuming and wiping operation. A dedicated XYZR robot system was designed which makes use of an Industrial IBM PC connected to a DELTA-7AV systems PMAC card to drive the robot and to: coordinate its actions with those of the OCS roof mounted gantry delivery carrier system. <s> BIB005 </s> A survey on coverage path planning for robotics <s> Introduction <s> Abstract We introduce a geometric version of the Covering Salesman Problem: Each of the n salesman's clients specifies a neighborhood in which they are willing to meet the salesman. Identifying a tour of minimum length that visits all neighboirhoods is an NP-hard problem, since it is a generalization of the Traveling Salesman Problem. We present simple heuristic procedures for constructing tours, for a variety of neighborhood types, whose length is guaranteed to be within a constant factor of the length of an optimal tour. The neighborhoods we consider include parallel unit segments, translates of a polygonal region, and circles. <s> BIB006 </s> A survey on coverage path planning for robotics <s> Introduction <s> We study the problem of finding shortest tours/paths for “lawn mowing” and “milling” problems: Given a region in the plane, and given the shape of a “cutter” (typically, a circle or a square), find a shortest tour/path for the cutter such that every point within the region is covered by the cutter at some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. ::: ::: Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3+e)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 65-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 115-approximation algorithm for milling simple rectilinear polygons. <s> BIB007 </s> A survey on coverage path planning for robotics <s> Introduction <s> Demining and unexploded ordnance (UXO) clearance are extremely tedious and dangerous tasks. The use of robots bypasses the hazards and potentially increases the efficiency of both tasks. A first cr... <s> BIB008 </s> A survey on coverage path planning for robotics <s> Introduction <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> BIB009 </s> A survey on coverage path planning for robotics <s> Introduction <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> BIB010 </s> A survey on coverage path planning for robotics <s> Introduction <s> This work introduces a method and apparatus for measuring real mobile robot cleaning performances based on a dedicated vision system. The measurement method can be applied to any kind of floor cleaning mobile robot but in this work it has been applied to a proprietary design. The paper presents the analysis of the first results obtained and ends with the main conclusions. <s> BIB011 </s> A survey on coverage path planning for robotics <s> Introduction <s> A coverage algorithm is an algorithm that deploys a strategy as to how to cover all points in terms of a given area using some set of sensors. In the past decades a lot of research has gone into development of coverage algorithms. Initially, the focus was coverage of structured and semi-structured indoor areas, but with time and development of better sensors and introduction of GPS, the focus has turned to outdoor coverage. Due to the unstructured nature of an outdoor environment, covering an outdoor area with all its obstacles and simultaneously performing reliable localization is a difficult task. In this paper, two path planning algorithms suitable for solving outdoor coverage tasks are introduced. The algorithms take into account the kinematic constraints of an under-actuated car-like vehicle, minimize trajectory curvatures, and dynamically avoid detected obstacles in the vicinity, all in real-time. We demonstrate the performance of the coverage algorithm in the field by achieving 95% coverage using an autonomous tractor mower without the aid of any absolute localization system or constraints on the physical boundaries of the area. <s> BIB012 </s> A survey on coverage path planning for robotics <s> Introduction <s> The watchman route problem (WRP) was first introduced in 1988 and is defined as follows: How to calculate a shortest route completely contained inside a simple polygon such that any point inside this polygon is visible from at least one point on the route? So far the best known result for the WRP is an O(n3log n) runtime algorithm (with inherent numerical problems of its implementation). This paper gives an κ(Ɛ) × O(kn) approximate algorithm for WRP by using a rubberband algorithm, where n is the number of vertices of the simple polygon, k the number of essential cuts, Ɛ the chosen accuracy constant for the minimization of the calculated route, and κ(Ɛ) equals the length of the initial route minus the length of the calculated route, divided by Ɛ. <s> BIB013 </s> A survey on coverage path planning for robotics <s> Introduction <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> BIB014
Coverage Path Planning (CPP) is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. This task is integral to many robotic applications, such as vacuum cleaning robots BIB001 , painter robots BIB010 , autonomous underwater vehicles creating image mosaics  , demining robots BIB004  BIB008 ], lawn mowers BIB002 BIB012 , automated harvesters Stentz, 1996, 1997] window cleaners BIB005 and inspection of complex underwater structures BIB014 , just to name a few. In one of the earliest works on CPP found in the literature, BIB002 defined the requirements a robot must meet to perform a coverage operation. Albeit the target application in the aforementioned paper is a mobile robot moving in a flat 2-dimensional environment, the same criteria are applicable to other coverage scenarios. The requirements are as follows: 1. Robot must move through all the points in the target area covering it completely. 2. Robot must fill the region without overlapping paths. 3. Continuous and sequential operation without any repetition of paths is required. 4. Robot must avoid all obstacles. 5. Simple motion trajectories (e.g., straight lines or circles) should be used (for simplicity in control). 6. An "optimal" path is desired under available conditions. However, it is not always possible to satisfy all these criteria in complex environments. Therefore, sometimes a priority consideration is required. The CPP problem is related to the covering salesman problem, a variant of the well-known traveling salesman problem where, instead of visiting each city, an agent must visit a neighborhood of each city BIB006 . However, in CPP, the agent must pass over all points in the target area in contrast to visiting all the neighborhoods. Since the traveling salesman problem is NP-hard, the computational time required to solve the problem increases drastically when the dimension of the problem increases. Actually, finding a path to cut all the grass of a given region covered by grass, which is known as the "lawnmower problem", is proven to be NP-hard BIB007 . Notice that the lawnmower problem does not account for obstacles. In fact, even the basic path planning problem, known as the "piano mover's problem", of finding a collision-free path from a start configuration to a goal configuration is shown to be PSPACE-hard, which implies NPhard   . Two additional, similar problems related to CPP are the art gallery problem and the watchman route problem. The art gallery problem calls for the minimum number of guards needed to station in a polygonal gallery so that each point in the gallery is visible to at least one guard [Shermer, 1992] . The watchman route problem calls for the shortest route from a given point back to itself so that each point in a given space is visible from at least one point along the route BIB013 . Simple cases of the watchman route problem such as covering the interior of simple polygons can be achieved in polynomial time BIB003 . But, in general, both the art gallery problem and the watchman route problem are NP-hard [Shermer, 1992; BIB013 . Some coverage algorithms we discuss in Subsec. 8.6 approach CPP as the art gallery problem and the watchman route problem. Coverage algorithms can be classified as heuristic or complete depending on whether or not they provably guarantee complete coverage of the free space. Independently, they can be classified as either off-line or on-line. This classification was originally proposed by Choset in his survey BIB009 . Off-line algorithms rely only on stationary information, and the environment is assumed to be known in advance. However, assuming full prior knowledge of the environment might be unrealistic in many scenarios. On the other hand, on-line algorithms do not assume full prior knowledge of the environment to be covered and utilize real-time sensor measurements to sweep the target space. Thus, these later algorithms are also called sensor-based coverage algorithms. In certain scenarios, a valid approach to solve the problem is to randomize. This is an approach that some floor-cleaning robots rely on: if the floor is swept randomly for long enough, it should become cleaned. Examples of commercial floorcleaning robots based fully or partially on this strategy are the RC3000 by Karcher, Trilobite by Electrolux and Roomba by iRobot BIB011 . There are advantages to this approach, the main one being that no complex sensors for localization nor expensive computational resources are needed. However, for covering vast areas, and especially for underwater or aerial robotics operations which deal intrinsically with a 3-dimensional space, it is difficult to think that a randomized "algorithm" could be usable, as the cost of operating the vehicle (energy and time) would be unaffordable. A considerable body of research addressing the CPP problem can be found in the literature. BIB009 presented a survey on coverage path planning methods. However, no updated surveys on CPP reflecting recent advances in the field have been presented in the past ten years. In this paper, we present a review of the most successful CPP methods, focusing in the achievements made in the past decade. Furthermore, we discuss reported field applications of the described CPP methods. This work aims to become a starting point for researchers who are initiating their endeavors in CPP. Likewise, this work aims to present a good review of the recent breakthroughs in the field, providing links to the most interesting and suc-cessful works. Since most CPP algorithms decompose the target space in sub-regions (called cells) to achieve coverage, BIB009 classified coverage algorithms according to the type of decomposition used. Hence, his taxonomy comprises heuristic and randomized approaches (which typically do not use a representation of the environment and therefore neither use a decomposition), and approximate, semi-approximate and exact cellular decompositions. However, we argue that qualitatively different approaches can be distinguished among these categories. Thus, the sections in this article do not bear a one-to-one correspondence with Choset's taxonomy, but rather reflect the common underlying ideas used in the discussed approaches. Nonetheless, Choset's taxonomy is commonly used throughout the literature, and hence we provide the corresponding Choset's classification for the methods reviewed. Resulting from these considerations, the remainder of this article is organized as follows. Sec. 2 reviews classical cellular decomposition algorithms which set the fundamentals of the cellular decomposition approach. Sec. 3 discusses the cellular decomposition based on critical points of Morse functions, which can deal with a more general class of obstacles. Sec. 4 presents a coverage approach based on detection of natural landmarks. A coverage algorithm for robots equipped with only contact sensors operating in rectilinear environments is discussed in Sec. 5. Methods based on a grid representation of the space are reviewed in Sec. 6. Work addressing the coverage problem in environments that can be represented as a graph, such as a street or road network, is briefly reviewed in Sec. 7. In Sec. 8 several methods for covering 3-dimensional environments are presented. Sec. 9 reviews some methods for achieving optimal coverage, and Sec. 10 focuses on methods that intend to reduce the accumulation of localization error while performing coverage. In Sec. 11 several multi-robot CPP methods are reviewed. Finally, concluding remarks including a summary table and directions for further research are given in Sec. 12.