A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposi- <s> This paper describes a prototype robot and the necessary path planning and control for space inspection applications. The robot is the first generation of a free-flying robotic camera that will assist astronauts in constructing and maintaining the Space Station. The robot will provide remote views to astronauts inside the Space Shuttle and future Space Station, and to ground controllers. The paper describes a planar robot prototype autonomously moving about an air bearing table, and introduces a method for determining paths in three-dimensions for efficient fuel use. Finally, the paper describes the software simulation of the path planner with the future Space Station. <s> BIB001 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposi- <s> This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a geometric structure that a robot uses to plan a path between two points in an environment. If the robot knows the roadmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the environment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction procedure of the HGVG requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor-based planning algorithms. Simulations and experiments using a mobile robot with ultrasonic sensors verify this approach. <s> BIB002 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposi- <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> BIB003 </s> A survey on coverage path planning for robotics <s> Morse-based Cellular Decomposi- <s> Coverage path planning determines a path that passes a robot, a detector, or some type of effector over all points in the environment. Prior work in coverage tends to fall into one of two extremes: coverage with an effector the same size of the robot, and coverage with an effector that has infinite range. In this paper, we consider coverage in the middle of this spectrum: coverage with a detector range that goes beyond the robot, and yet is still finite in range. We achieve coverage in two steps: The first step considers vast, open spaces, where the robot can use the full range of its detector; the robot covers these spaces as if it were as big as its detector range. Here we employ previous work in using Morse cell decompositions to cover unknown spaces. A cell in this decomposition can be covered via simple back-and-forth motions, and coverage of the vast space is then reduced to ensuring that the robot visits each cell in the vast space. The second step considers the narrow or cluttered spaces where obstacles lie within detector range, and thus the detector "fills" the surrounding area. In this case, the robot can cover the cluttered space by simply following the generalized Voronoi diagram (GVD) of that space. In this paper, we introduce a hierarchical decomposition that combines the Morse decompositions and the GVDs to ensure that the robot indeed visits all vast, open, as well as narrow, cluttered, spaces. We show how to construct this decomposition online with sensor data that is accumulated while the robot enters the environment for the first time. <s> BIB004
tion Combined with the Generalized Voronoi Diagram BIB004 ] presented a sensor-based coverage approach with extended range sensors. Incorrect edge Figure 14 : A concave critical point will not be detected if the boundary's curvature is smaller than the robot's periphery and will lead to an incoherent Reeb graph. This is the case of Cp2 in this example environment, which does not get detected and produces an incorrect edge emanating from Cp3. As they point out, "prior work in coverage tends to fall into one of two extremes: coverage with an effector the same size of the robot, and coverage with an effector that has infinite range." In this work, they consider coverage in the middle of this spectrum: coverage with a detector range that goes beyond the robot, and yet is still finite in range. They term these sensors extended range sensors. In this work, coverage is achieved in two steps: the first step considers vast, open spaces, where the robot can use the full range of its detector; the robot covers these spaces as if it were as big as its detector range (see Fig. 15 , on the right). Here previous work in using Morse cell decompositions BIB003 ] is employed to cover unknown spaces. As explained above, cells in this decomposition can be covered via simple backand-forth motions, and coverage of the vast space is then reduced to ensuring that the robot visits each cell in the vast space. The second step considers the narrow or cluttered spaces where obstacles lie within detector range, and thus the detector "fills" the surrounding area. In this case, the robot can cover the narrow space by simply following the Generalized Voronoi Diagram (GVD) of that space, which are sets of points equidistant to two obstacles , [de Berg et al., 2008 ] (see Fig. 15 , on the left). The GVD can be constructed on-line using range sensor information and has been previously used for sensorbased exploration BIB002 and inspection of 3D structures BIB001 . A hierarchical decomposition that combines the Morse decompositions and the GVDs is introduced to ensure that the robot indeed visits all vast, open, as well as narrow, cluttered, spaces. In their article, it is shown how to construct this decomposition online using sensor data accumulated while the robot covers the environment. Figure 15: Combination of Morse decomposition and GVD for extended range sensor coverage. In cluttered spaces (left) the robot just follows the GVD of that space. In vast areas (right), the robot follows the pattern generated using a Morse decomposition scheme. 4 Landmark-based Topological Coverage  MacDonald, 2003, 2004;  presented an on-line topological coverage algorithm for mobile robots based on detection of natural landmarks. This work is intended for simple planar environments. As in Morse decomposition, their method also uses concepts introduced by boustrophedon decomposition. However, the topological algorithm proposed here uses different events to determine cell boundaries. Morse decomposition places cell boundaries on the critical points on the obstacles surface. However, as commented before, rectilinear environments cannot be handled by Morse decomposition, as the critical points in such environments are degenerate. On the other hand, as critical points can only be discovered on the side of the robot while performing wall following, a rectangular coverage pattern which includes retracing is needed. In comparison, the topological approach presented here uses simpler landmarks to determine an exact cellular decomposition termed "slice decomposition". Due to the use of simpler landmarks, slice decomposition can handle a larger variety of environments, including ones with polygonal, elliptical and rectilinear obstacles. Moreover, obstacles can be detected from all sides of the robot, allowing a simpler zigzag pattern without retracing to be used. As a result, the generated coverage path is shorter with this method.