Sensor-based coverage with extended range detectors

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.