Coverage Path Planning

Planning a path that sweeps a robot, or its tool, across every reachable part of an area.

Ordinary path planning only cares about getting from A to B; coverage path planning requires a robot's working footprint (a suction nozzle, a cutting blade, a spray nozzle) to sweep every obstacle-free part of a target area, while minimizing repeated coverage, turns, and total time. Three classic families of methods exist: cell decomposition, most commonly the boustrophedon (‘ox-turning,’ i.e. back-and-forth like plowing a field) decomposition proposed by Choset and Pignon in 1998, which cuts the region into cells around obstacles and sweeps back and forth within each like plowing; grid-based methods, which divide the map into cells visited one by one; and spiral patterns, among others. Methods are further split into offline and online depending on whether the map is known in advance. Galceran and Carreras's 2013 survey in Robotics and Autonomous Systems gives a systematic overview. Typical applications include robot vacuums, lawn-mowing robots, agricultural machinery, spraying drones, and arm-based spray-painting or sanding of curved surfaces.

ExampleThe open-source library Fields2Cover, aimed at farm machinery, splits planning into headland generation, swath generation, swath-sequence ordering, and final path generation; Nav2's opennav_coverage, built on it, supports boustrophedon, serpentine, and spiral swath orderings, letting ROS 2 robots run full-coverage tasks directly.

Also called

CPP, Complete Coverage Path Planning

Related

Path Planning · Global Planning and Local Planning · Occupancy Grid Map · Robot Vacuum Cleaner · ROS 2 Navigation Stack (Nav2) · Multi-Agent Path Finding

Sources

Mier et al., Fields2Cover: An Open-Source Coverage Path Planning Library for Unmanned Agricultural Vehicles (arXiv:2210.07838)
open-navigation/opennav_coverage（Nav2 全覆盖任务服务器） (Chinese)
Choset & Pignon: Coverage Path Planning: The Boustrophedon Cellular Decomposition (1998)