Glossary

Fictionlab > Glossary > Coverage path planning

Coverage path planning

Coverage Path Planning – definition

Coverage Path Planning (CPP) is the process of computing a mobile robot trajectory that covers a defined area while satisfying constraints on robot motion, sensor footprint, obstacle clearance, and mission completion. In unmanned ground vehicle (UGV) applications, the objective is not simply to reach one target pose. The robot must traverse the free space so that a sensor, tool, or inspection payload observes or processes the required surface.

CPP is used for autonomous mapping, visual inspection, agricultural surveying, floor or terrain scanning, and repeated data collection. A plan usually consists of parallel lanes, connecting turns, and recovery behaviour for blocked or unreachable regions. The term is also called complete coverage path planning when the algorithm aims to cover all reachable free cells or all reachable workspace within a specified tolerance.

For a differential-drive UGV such as Leo Rover, coverage planning must account for non-holonomic motion. The robot cannot move laterally, and lane transitions require feasible turns. Leo Rover provides a four-wheel differential drive base and native ROS 2 support on Raspberry Pi-based compute hardware, but it requires an integrated navigation stack, localisation method, map, and sensor configuration before it can execute autonomous coverage missions. Raph Rover follows the same UGV planning principles but can carry larger sensor or compute payloads where the mission requires them.

Coverage planning inputs for mobile robots

A coverage planner operates on a representation of the workspace and a model of the robot’s effective working width. In ROS 2, the workspace is commonly represented as an occupancy grid, costmap, polygon, point cloud-derived map, or georeferenced boundary. The selected representation affects the achievable accuracy and computational cost.

Input Typical ROS 2 representation Role in CPP
Robot pose geometry_msgs/msg/PoseStamped, TF2 transform Initial pose, progress tracking, route execution
Map nav_msgs/msg/OccupancyGrid Free-space and obstacle definition
Costmap Nav2 global and local costmaps Inflation, obstacle clearance, traversability constraints
Coverage boundary Polygon or mission-specific waypoint file Area that must be processed
Tool footprint Planner parameter Lane spacing and overlap calculation

The nominal lane spacing is determined by the effective footprint rather than the physical width of the UGV. If a sensor or tool has usable width w and the required overlap is o, where 0 ≤ o < 1, a common first approximation is:

lane_spacing = w × (1 - o)

This formula does not compensate for pose error, wheel slip, terrain-induced heading error, or sensor occlusion. Practical missions therefore use a safety margin and validate coverage from recorded sensor data or a coverage grid.

How Coverage Path Planning works in ROS 2

ROS 2 does not define one mandatory CPP interface or a standard coverage planner. A typical implementation combines a mission-level coverage node with Navigation2 (Nav2). The coverage node generates ordered lane endpoints or intermediate poses. Nav2 then plans collision-free motion and controls the UGV between these poses.

Coordinate frames should follow REP 105, which defines conventional mobile-platform frames including map, odom, and base_link. The coverage plan is normally generated in the map frame. The local controller operates with continuously updated transforms and obstacle data.

coverage_planner:
  ros__parameters:
    frame_id: map
    lane_spacing_m: 0.40
    headland_width_m: 0.60
    obstacle_clearance_m: 0.20
    route_pattern: boustrophedon
    allow_reverse: false

The parameter values above are examples, not universal Leo Rover or Raph Rover specifications. Lane spacing must be derived from the mission payload and validated against localisation accuracy, sensor field of view, and available turning space.

Algorithms and route patterns

CPP algorithms differ mainly in how they decompose the workspace and how they minimise unproductive travel between coverage lanes. The best choice depends on map complexity, obstacle density, vehicle kinematics, and whether the mission is global or online.

  • Boustrophedon pattern – Alternating parallel lanes, often called a lawnmower pattern. It is efficient in open, approximately rectangular areas.
  • Boustrophedon cellular decomposition – Divides free space into cells when obstacle topology changes. Each cell can be covered with a local lane pattern.
  • Spanning-tree coverage – Covers grid cells by traversing a graph or spanning tree. It is useful where the map is naturally discretised.
  • Wavefront coverage – Uses distance propagation over a grid to derive routes. Its resolution is bounded by the grid-cell resolution.
  • Frontier-based exploration – Selects boundaries between known and unknown space. It supports map-building missions but does not by itself guarantee complete coverage of an already known area.

For a Leo Rover operating indoors with a 2D LiDAR or depth-camera obstacle layer, a lane-based planner with Nav2 obstacle avoidance is often appropriate. For outdoor Raph Rover missions, GNSS/RTK may provide a global reference, while LiDAR, cameras, wheel odometry, and IMU data support local obstacle detection and pose continuity where satellite positioning degrades.

Key metrics and failure conditions

Coverage quality must be measured separately from navigation success. A robot can report that all waypoints were reached while leaving unobserved strips because of inaccurate localisation, route deviations, or a sensor footprint that was modelled incorrectly.

  • Coverage ratio: covered area divided by required reachable area.
  • Overlap: repeated coverage between adjacent swaths, expressed as a percentage or width.
  • Path length: total travelled distance, including turns and transit segments.
  • Completion time: elapsed time from mission start to coverage completion.
  • Missed-area rate: required area not observed or processed to the specified criterion.
  • Clearance: minimum robot-to-obstacle distance maintained according to collision checking, robot-footprint modelling, and costmap configuration.

Common failures include stale obstacle maps, inaccurate TF transforms, incorrect robot footprint parameters, insufficient headland for turns, and localisation drift. The Nav2 costmap and controller can avoid obstacles, but dynamic avoidance can create uncovered gaps. A production workflow should record the robot trajectory, localisation covariance where available, sensor data, and the coverage-state map for post-mission verification.

Normative references and technical sources

The following sources define the ROS interfaces and coordinate conventions commonly used when implementing CPP for UGVs. They do not prescribe one universal coverage algorithm.

See also