galceran2013survey

A Survey on Coverage Path Planning for Robotics

Authors: Galceran, Carreras · Year: 2013 · Venue: Robotics and Autonomous Systems 61(12):1258–1276 Raw: author PDF (UdG DUGiDocs) — read live; not yet marker-converted into Docs/raw/md/ (LAN cluster down 2026-07-04).

Summary

The standard survey of coverage path planning (CPP): the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. It updates Choset’s 2001 survey with the decade’s advances, organizing methods by their underlying idea (cellular decomposition, grid, graph, 3D, optimal, uncertainty-aware, multi-robot) and closing with a summary table classifying each method by category, on/off-line status, environments handled, and remarks. This is the coverage-path-planning taxonomy our inspection chapter anchors to — the complement to view planning (scott2003view): view planning picks which views cover the surface; CPP builds the path that visits them.

Key Claims

• CPP definition: determine a path passing over all points of a target area/volume while avoiding obstacles (Abstract, Sec. 1).
• Coverage algorithms are classified along two independent axes (after Choset 2001): heuristic vs complete (does it provably guarantee full coverage of free space?) and off-line vs on-line (off-line assumes a known environment; on-line = sensor-based, no full prior map) (Sec. 1).
• CPP is related to the covering salesman problem (a TSP variant); the “lawnmower problem” of cutting all grass in a region is NP-hard, and the basic collision-free “piano mover’s problem” is PSPACE-hard. The art gallery and watchman route problems are the visibility-coverage analogues invoked by some 3D methods (Sec. 1).
• Exact cellular decomposition breaks free space into simple cells covered by back-and-forth (“mowing the lawn”/boustrophedon) motions; complete coverage reduces to an exhaustive walk of the cells’ adjacency graph. Trapezoidal → boustrophedon → Morse-based decomposition progressively handles more general (non-polygonal, differentiable-boundary) obstacles; Morse critical points can be detected on-line from range data (Reeb-graph encoding) (Secs. 2–3).
• Grid-based methods (wavefront distance transform, Spiral-STC spanning-tree coverage, neural-network shunting, hexagonal side-scan) give resolution-complete coverage but are localization-sensitive and memory-heavy; graph-based coverage handles street/road-network environments (Secs. 6–7).
• 3D coverage largely means covering a 2D surface embedded in 3D (automotive parts, buildings, sea floor, ship hulls). For confined/occluded complex structures, random-sampling-based coverage is the state of the art: Englot & Hover (2012) solve an art-gallery instance for view configurations then a TSP-variant tour; Papadopoulos et al. (2013) interleave view generation with feasibility of the connecting path and are probabilistically optimal (Sec. 8).
• Coverage under uncertainty (localization drift, active SLAM) and multi-robot coverage (workload division, mutual beaconing, robustness) are surveyed; incorporating uncertainty into CPP is flagged as a largely open problem (Secs. 10–12).

Method

A literature survey; it transcribes few equations. Two are worth carrying:

• Morse function / critical points. A slice (codimension-one manifold) is the pre-image ${\mathcal{W}}_{\lambda }=h^{-1}(\lambda )$ of a real-valued Morse function $h:\mathcal{W}\to \mathbb{R}$ swept through the workspace by increasing $\lambda$; cell boundaries are placed at critical points, where the obstacle surface normal is parallel to the sweep direction (all partials of $h$ vanish and the Hessian is nonsingular). Different $h$ yield different coverage patterns (e.g. $h=x$ → boustrophedon lanes; $h=\sqrt{x^2+y^2}$ → spiral) (Sec. 3).
• Critical-point detection gradient — for a robot at $x$ with nearest obstacle-surface point $c_0$, the distance gradient $\nabla d_i(x)=(x-c_0)/\Vert x-c_0\Vert$ is the unit outward surface normal, detected during wall-following (Sec. 3.1).

The organizing deliverable is Table 1: category × approach × reference × on/off-line × environments handled × remarks — a ready map from a coverage problem to a candidate method.

Relevance to thesis

CPP is the path-level half of our inspection mission (the view-planning half is scott2003view): once a scorer picks the mesh views that cover the target, CPP is the literature for the tour that visits them. The most directly analogous result is Englot & Hover (2012) (Sec. 8.6): complete sensor coverage of a complex 3D structure (a ship hull) by a fully-actuated, six-degree-of-freedom hovering vehicle, using a closed triangular mesh of the target — the same problem shape as a free-flying 6-DOF manipulator inspecting a satellite mesh. Their two-stage recipe (solve an art-gallery instance for a covering set of view configurations, then a TSP-variant minimum-cost closed walk) and Papadopoulos et al.’s differential-constraint-aware, asymptotically-optimal variant are candidate baselines/contrasts for our coverage tour. The two classification axes (complete vs heuristic, off-line vs on-line) give us provenance-backed language for describing our own planner. Regime caveat: nearly all surveyed platforms are wheeled/aerial/underwater vehicles with simple kinematics; none carry a redundant arm on an actuated base, so the manipulator’s coupling and singularity structure is out of scope here — CPP constrains the path, not the arm.

Connections

Topics: motion_planning · receding_horizon_control · d_optimality · coverage_path_planning (PAGE NEEDED) · next_best_view (PAGE NEEDED) · Sources: scott2003view · connolly1985determination

Key Equations / Quotes

“The coverage path planning (CPP) problem is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles.” (Abstract)

“They consider the planning problem with a fully-actuated, six degree-of-freedom hovering AUV that uses a bathymetry sonar to inspect the structures in the ship hull. The method requires a discrete model of the structure to be inspected provided in the form of a closed triangular mesh.” (Sec. 8.6, on Englot & Hover 2012)

“few attention has been given to incorporating uncertainty in coverage path planning methods. Hence, this remains as an open issue for further research.” (Sec. 12)

Open Questions

• Englot & Hover cover a ship hull with a 6-DOF hovering base but no manipulator — what changes in the art-gallery + TSP recipe when the sensor rides a redundant arm whose reachable viewpoints depend on base pose and arm configuration (coupling, singularities)?
• The survey’s own conclusion flags uncertainty-aware CPP as open — this is exactly our risk layer; does the CPP tour or the view-selection step carry the risk metric?
• “3D coverage” in the survey means covering a 2D surface embedded in 3D; for a satellite with deep occlusions and thin appendages, is the closed-mesh assumption adequate?