A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <s> Abstract This paper describes preliminary work on an algorithm for planning collision-free motions for a robot manipulator in the presence of obstacles. The physical obstacles lead to forbidden regions in the robots configuration space, and for collision-free motion we need paths through configuration space which avoid these regions. Our method is to construct a certain one-dimensional subset or “roadmap” of the space of allowable configurations. If S denotes the set of allowable configurations, the roadmap has the property that any connected component of S contains a single connected component of the roadmap. It is also possible, starting from an arbitrary point p ∈ S to rapidly construct a path from p to a point on the roadmap. Thus given any two points in S we can rapidly determine whether they lie in the same connected component of S, and if they do, we can return a candidate path between them. We do not give a complete description of the algorithm here, but we define the roadmap geometrically, and verify that it has the necessary connectivity. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <s> A robot planning algorithm that constructs a global skeleton of free-space by incremental local methods is described. The curves of the skeleton are the loci of maxima of an artificial potential field that is directly proportional to the distance of the robot from obstacles. The method has the advantage of fast convergence of local methods in uncluttered environments, but it also has a deterministic and efficient method of escaping local extremal points of the potential function. The authors present a general algorithm, for configuration spaces of any dimension, and describe instantiations of the algorithm for robots with two and three degrees of freedom. > <s> BIB002 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <s> Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include de-mining, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Essentially, the boustrophedon decomposition is a generalization of the trapezoidal decomposition that could allow for non-polygonalobstacles, but also has the side effect of having more “efficient” coverage paths than the trapezoidal decomposition. Each cell in the boustrophedon decomposition is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and experiments on a mobile robot validate this approach. <s> BIB003 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <s> Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algo... <s> BIB004 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <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> BIB005 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposition <s> Coverage path planning is the problem of moving an effector (e.g. a robot, a sensor) over all points in a given region. In marine robotics, a number of applications require to cover a region on the seafloor while navigating above it at a constant depth. This is the case of Autonomous Surface Vehicles, that always navigate at the water surface level, but also of several Autonomous Underwater Vehicle tasks as well. Most existing coverage algorithms sweep the free space in the target region using lawnmower-like back-and-forth motions, and the inter-lap spacing between these back-and-forth laps is determined by the robot's sensor coverage range. However, while covering the seafloor surface by navigating above it at a constant depth, the sensor's field of view varies depending on the seafloor height. Therefore, to ensure full coverage one would need to use the inter-lap spacing determined by the shallowest point on the target surface, resulting in undesired coverage overlapping among the back-and-forth laps. In this work, we propose a novel method to generate a coverage path that completely covers a surface of interest on the seafloor by navigating in a constant-depth plane above it. The proposed method uses environment information to minimize the coverage overlapping by segmenting the target surface in regions of similar depth features and addressing them as individual coverage path planning problems. A cell decomposition coverage method is applied to each region. The surface gradient is used to determine the best sweep orientation in each cell, and the inter-lap spacing in the lawnmower-like paths used to cover each cell is maximized on a lap-by-lap basis, hence obtaining a shorter, more efficient coverage path. The proposal is validated in simulation experiments conducted with a real-world bathymetric dataset that show a significant increase on path efficiency in comparison with a standard boustrophedon coverage path. <s> BIB006
Later, BIB004 generalized the boustrophedon decomposition by proposing a novel cellular decomposition approach based on critical points of Morse functions [Milnor, 1963] . In fact, they show that the boustrophedon decomposition is a particular case of Morse decomposition. With respect to the original boustrophedon decomposition, the Morse-based decomposition has the advantage of handling also non-polygonal obstacles. By choosing different Morse functions, different cell shapes are obtained, e.g. circular or spiked cells. Theoretically, Morse-decompositions can be applied to any n-dimensional space. Moreover, they presented a method to perform coverage of planar spaces by detecting the critical points using sensory range information, and a motion-template-based algorithm that ensures to encounter all the critical points in the target area. Therefore, this method allows complete coverage on-line Choset, 2001, 2002a] . The Morse decomposition is based on a roadmap method for start-to-goal path planning proposed by Canny BIB001 BIB002 . Critical points of a Morse function restricted to the obstacle boundaries are used to determine the cell decomposition. Recall that, given a real-valued func- A critical point is a value p ∈ R m where either the function is not differentiable or all its partial derivatives are 0, i.e., ∂h ∂x 1 (p) = ... = ∂h ∂xm (p) = 0, and its Hessian ( ) is non-singular. For instance, in the case of a single variable function, a critical point corresponds either to a local maximum, a local minimum or an inflection. A Morse function is one whose critical points are nondegenerate [Milnor, 1963] . Practically speaking, this means that critical points are isolated from one another. To determine the cell decomposition, a slice is swept through the target space. Formally, the slice is a codimension one manifold defined in terms of the preimage of a real-valued Morse function, h : W → R, where W is the robot's workspace, i.e., the space to be covered. For instance, in the plane (W = R 2 ), choosing h(x, y) = x will make the slice be effectively a vertical line. Changes on the connectivity of the slice occur at critical points of the Morse function restricted to the obstacle boundaries. To put it more simply, at a critical point the sweep line encounters an obstacle whose surface normal is perpendicular to the sweep line, as shown in Fig. 4 . Morse theory guarantees that, between critical points, the connectivity of the slice remains unchanged. Thus, as no obstacles lay between critical points, the space between them can be covered easily by simple motions, and critical points can be used to determine the cell boundaries. Choosing different Morse functions produces different slice shapes and hence different cell decomposition patterns. For simplicity, we will describe the Morse-based boustrophedon decomposition BIB003 , which happens in the plane. Later, we will give examples of different decomposition patterns obtained using different Morse functions. In the boustrophedon decomposition, a vertical slice, defined in terms of the Morse function h(x, y) = x, is swept from left to right in the workspace, i.e., along the abscissae axis. Thus, the vertical slice is determined by the preimage of this Morse function, W λ = h −1 (λ). The slice is parametrized by λ ∈ R, which fixes its location in the target space. Increasing the value of the slice parameter, λ, sweeps the slice from left to right through the workspace. As the slice sweeps the space it intersects (or stops intersecting) obstacles, which divide it into smaller pieces as the slice first encounters an obstacle, that is, the connectivity of the slice in the free space increases. Also, immediately after the slice leaves an obstacle, smaller slice pieces are merged into larger pieces (the connectivity of the slice in the free space decreases). The points where these connectivity changes occur are the critical points. (Recall that critical points are always located on the obstacle boundaries.) Thus, at critical points, the slice is used to determine the cells in the decomposition. Notice that within a cell, the slice connectivity remains constant. Fig. 5(a) shows how, at the critical point, the connectivity of the slice changes from one to two, and hence the old cell is closed and two new cells are created. In Fig. 5(b) , at the critical point, the connectivity of the slice changes from two to one, and hence two old cells are closed and a new cell is created. Once the cell decomposition is constructed, an exhaustive walk through its associated adjacency graph is determined by the planner. Then, it generates the explicit coverage path in each cell. The coverage pattern within each cell has three parts: motion along a slice, motion orthogonal to the slice, and motion along the cell boundary, as shown in Fig. 6 . First, the robot laps along the current slice, W λ . Then the robot steps outward of the slice by going orthogonally to it by an interlap distance, typically by a distance of one robot sensor range; λ is also increased by this distance to form a new slice. If the robot encounters an obstacle (i.e., the cell boundary) while moving along the slice, the planner directs the robot to follow the obstacle boundary until it has moved an interlap distance and then a new lap along a new slice is started. The process repeats until the cell is completely covered. A key point of Morse decompositions is that, by choosing different Morse functions to define the slice that is swept through the space, different decomposition and coverage path patterns can be generated, like the spiral pattern BIB004 . Figure 8 shows a spiral pattern obtained using the morse function h(x, y) = x 2 + y 2 . Allowing different coverage patterns is useful for vehicles with kinematic constraints. For instance, a spiral path can be easily followed by an underactuated car-like vehicle unable to make hard turns BIB005 . A limitation of the Morse decomposition method is that it cannot handle rectilinear environments. This is because it is not possible to determine critical points in those environments which correspond to a change in the topology of the space (the critical points are said to be degenerate in this case [Milnor, 1963] ). [ BIB006 ] presented a CPP method based on Morse decomposition to minimize redundant coverage for autonomous under-water vehicles and autonomous surface vehicles imaging the ocean floor. To this aim, this method determines a sweep direction on each cell of the decomposition and adjusts the inter-lap spacing of the boustrophedon paths on a lap by lap basis according to the ocean depth. The efficacy of the method is demonstrated in simulation using a real-world dataset.