Coverage Path Planning

The fundamental requirement that the sensor or tool footprint passes over every point in the target free space. Algorithms achieve this through exact cellular decomposition (trapezoidal or boustrophedon methods) which provably partition the area into non-overlapping cells. In contrast, randomized sampling methods offer probabilistic completeness, suitable for high-dimensional configuration spaces where exact decomposition is computationally intractable.

CPP algorithms must navigate static obstacles while minimizing uncovered gaps. Morse-based decomposition uses critical points on obstacle boundaries to slice the space, ensuring the path adapts to irregular geometries. Modern approaches integrate signed distance fields (SDFs) to maintain a safe standoff distance from obstacles, crucial for UAV inspection where aerodynamic disturbances near surfaces must be avoided.

Coverage efficiency is measured by minimizing path overlap and non-productive travel. The optimal pattern is often a simple back-and-forth lawnmower motion, but the angle of these sweep lines relative to the polygon geometry drastically changes the number of turns. Algorithms compute the optimal sweep direction by finding the minimum-altitude of the rotating calipers polygon to reduce the total path length and energy consumption.

Complex environments are broken into simpler sub-regions. Boustrophedon decomposition splits the space only when connectivity changes, merging adjacent cells to reduce unnecessary transitions. For multi-robot systems, Voronoi partitioning assigns exclusive zones to each agent based on proximity, enabling parallel coverage without inter-agent collision, a critical factor in autonomous mobile robot (AMR) fleet orchestration.

The effective coverage width of the sensor or tool dictates the lane spacing. A convex footprint (e.g., camera frustum, spray cone) is projected onto the surface, and the path is offset by this radius. For non-circular footprints, the Minkowski sum of the robot geometry and the coverage area is computed to dilate obstacles, reducing the planning problem to a point robot traversing a modified space.

Beyond geometric coverage, physical constraints like battery capacity and actuator dynamics are integrated. For UAVs, this means optimizing for minimum snap trajectories that respect motor limits. In underwater hull inspection, coverage paths must counteract hydrodynamic drag. Model Predictive Control (MPC) is often layered on top of the geometric planner to generate dynamically feasible, energy-optimal velocity profiles along the coverage waypoints.

The mathematical transformation of the physical workspace into a space where the robot is treated as a point. Every possible pose (position and orientation) maps to a single point in C-Space. Obstacles are inflated by the robot's geometry, turning complex collision checking into a simple point-in-obstacle test. For coverage planning, this abstraction is critical because it allows planners to reason about tool coverage rather than vehicle footprint, dramatically simplifying the search for complete area sweeping patterns.

The algorithmic guarantee that a planned path will not intersect with static or dynamic obstacles. Core techniques include:

• Gilbert-Johnson-Keerthi (GJK) for minimum distance between convex hulls
• Signed Distance Fields (SDF) for fast voxel-based queries
• Continuous Collision Detection (CCD) to prevent tunneling between timesteps In coverage planning, collision avoidance must operate continuously while the end-effector or sensor maintains contact with the target surface, requiring null-space optimization to satisfy both constraints simultaneously.

A receding-horizon optimal control strategy that solves a constrained optimization problem at each timestep. MPC predicts the system's future states over a finite horizon, applies only the first control input, then repeats. For coverage tasks, MPC enables dynamic feasibility—ensuring the planned sweeping pattern respects velocity, acceleration, and jerk limits of the physical platform. This is especially critical for aerial inspection drones where aggressive coverage maneuvers must remain within flight envelope constraints.

The computational problem of building a map of an unknown environment while concurrently estimating the robot's pose within it. Coverage planning in unmapped spaces depends entirely on SLAM output. Pose graph optimization and loop closure detection ensure the map is globally consistent, preventing coverage gaps caused by drift. Modern LiDAR-inertial SLAM systems provide the dense, metrically accurate maps required for precision inspection coverage on complex industrial structures.

An integrated planning paradigm that bridges high-level symbolic reasoning with low-level continuous motion planning. In coverage contexts, TAMP handles the decomposition of complex inspection goals:

• Symbolic layer: 'Inspect all weld seams on Section A'
• Motion layer: Generate collision-free coverage trajectories for each seam This hierarchical approach enables autonomous systems to reason about coverage completeness at the task level while optimizing individual sweep paths for efficiency and dynamic feasibility.

A layered grid-based data structure used extensively in ROS navigation stacks. Each layer represents different constraints:

• Static map layer: Known obstacles from SLAM
• Inflation layer: Safety buffer around obstacles
• Sensor layer: Dynamic obstacle detections For coverage planning, custom costmap layers can encode coverage history—marking cells as visited to prevent redundant sweeping—and sensor degradation zones where surface conditions reduce measurement quality, enabling adaptive path generation.