Task Description:

Sensor-based coverage uses sensor information to determine a path that passes a detector over all points in an unknown space. Our prior work in coverage prescribed a path for a circular robot of radius r to pass over all points in unknown spaces; in this case we set the detector range D to be equal to the robot's radius, r. Our prior work in Voronoi diagrams prescribed a path for a circular robot with infinite detector range delta= infinity to pass its detector over all points in an unknown bounded space. This work combines these results to consider ``efficient'' coverage with a finite-range detector with r < D < infinity. We define a new hierarchical decomposition with two types of cells: VAST and NARROW. In the VAST-cells, we treat the circular detector like a robot and re-use our critical point based coverage algorithm. In the NARROW-cells, since the obstacles are within the detector range, we effectively have an infinite-range detector, so the robot simply follows the Voronoi diagram. This work proves that this approach ensures complete coverage with extended-range detectors, which includes a switching procedure from VAST to NARROW-cells.

Figure 1: Depiction of the stages of the incremental construction of the hierarchical decomposition while the robot is covering the space. In the graph, gray ellipses depict the VAST-cells that contain VAST-subcells represented as solid edges. Each VAST-subcell has two associated critical points represented as black dots. NARROW-cell is represented by the white ellipse and it contains the NARROW-subcells depicted as dashed edges. Hollow dots correspond to cusp points and gray dots represent the meet points. Double arrows show the links between the NARROW-cells and their neighboring VAST-cells.

Exact Cellular Decomposition
Constrained Controlled Coverage
Auto-Body Painting