Coverage path planning is the problem of computing a path that makes a robot’s tool or sensor footprint pass over every reachable point of a target area while avoiding obstacles and minimizing time, distance or overlap. In robot navigation, it differs from ordinary point-to-point path planning: the goal is not to reach a destination but to sweep a whole region, as a cleaning robot does with a floor, a mower with a lawn, a tractor with a field or a drone with a survey area.
The quality of a coverage plan is judged by completeness, the share of the free area actually covered, and by efficiency, which includes path length, number of turns, overlap between passes and energy use. Because turns cost time and often cause slippage, many practical planners optimize the number and type of turns as much as raw distance.
How coverage path planning works
Most coverage planners follow three steps. First, they represent the environment, usually as a polygon map with obstacles or as an occupancy grid. Second, they decompose the free space into simpler regions that can each be covered with a regular pattern. Third, they order the regions and connect them into one continuous path, solving a routing problem similar to the traveling salesman problem.
Within each region, the classic pattern is the boustrophedon or back-and-forth sweep, named after the way an ox plows a field. The spacing between adjacent passes equals the effective tool width minus a chosen overlap, often a few percent to around 20 percent of the width, depending on localization accuracy and how costly a missed strip would be.
| Parameter | Typical range or choice | What it affects |
|---|---|---|
| Tool or sensor width | Centimeters for floor robots, meters for farm machines | Number of passes |
| Pass overlap | About 5 to 20 percent of width | Missed strips versus wasted time |
| Sweep direction | Aligned with the longest edge | Number of turns |
| Turning radius | Zero for differential drive, meters for vehicles | Headland size and turn shape |
| Localization accuracy | Centimeters with RTK GPS, decimeters indoors | Required overlap |
Main families of coverage algorithms
Coverage algorithms are commonly grouped by how they split and represent space. Exact cellular decomposition divides the area into cells whose union matches the free space exactly; the boustrophedon cellular decomposition creates cells at points where obstacles change the connectivity of a sweep line. Approximate methods use grids, and spanning tree coverage builds a tree over coarse grid cells and circles around it.
| Family | Representation | Strength | Limitation |
|---|---|---|---|
| Boustrophedon decomposition | Exact polygon cells | Efficient straight passes | Needs an accurate map |
| Grid-based coverage | Occupancy grid cells | Simple, handles any shape | Resolution limits accuracy |
| Spanning tree coverage | Coarse grid plus tree | Provably complete on the grid | Many turns |
| Morse-based decomposition | Critical points of a function | Handles curved obstacles | Complex to implement |
| Online or sensor-based | Map built during coverage | Works in unknown areas | Less efficient paths |
Offline planners compute the full path before the robot starts, using a known map. Online planners build the map and the plan at the same time, which is necessary for robots entering unknown rooms. Many consumer cleaning robots combine both: they map on the first run and then plan efficient coverage on later runs.
Coverage path planning compared with related navigation tasks
Coverage planning sits beside several neighboring navigation concepts and relies on them. A global path planner finds a route between two points and is used inside coverage to travel between regions. A local planner and obstacle avoidance follow the coverage path while reacting to unexpected objects. Localization keeps the robot aware of where it is, which directly determines whether the planned passes are actually covered.
| Function | Goal | Relation to coverage |
|---|---|---|
| Path planning | Reach one goal pose | Connects coverage regions |
| Waypoint navigation | Visit listed points in order | Executes the coverage path |
| Obstacle avoidance | Prevent collisions | Handles unmapped obstacles |
| Localization | Estimate current pose | Determines real coverage accuracy |
| Costmap | Encode traversal costs | Marks no-go and preferred zones |
Practical design choices
In practice, the sweep direction is chosen to minimize the number of turns, which usually means sweeping parallel to the longest edge of each region. Vehicles with a large turning radius need headlands, extra strips around the boundary used for turning, which are themselves covered at the end. Agricultural planners also consider slope, soil compaction and the position of the field entrance.
- Match overlap to localization error: poorer positioning requires wider overlap.
- Cover edges separately with a perimeter pass when the tool cannot reach corners.
- Plan for interruptions such as battery recharging, resuming from the last covered strip.
- Record actual coverage from the pose history, not only the planned path.
- Exclude no-go zones explicitly in the map rather than relying on sensors alone.
Limitations and failure modes
Coverage plans are only as good as the map and the localization. Wheel odometry drift on slippery floors or GNSS errors near buildings and trees cause gaps and overlaps that the plan never intended. Dynamic obstacles such as people, pets or parked vehicles force detours, after which the robot must return to uncovered areas rather than continue blindly.
Optimal coverage is computationally hard in general, so planners rely on heuristics and approximations. A plan that is shortest in distance may still be slower in reality if it contains many sharp turns or poor transitions between regions.
The idea in brief
Coverage path planning answers a simple question: how should a robot move so that it covers every part of an area? Think of mowing a lawn by hand. Most people walk in straight, slightly overlapping lines and turn at the edges.
A robot does the same thing, but it plans the lines with a map. It works around obstacles such as trees or furniture. The aim is to miss nothing while wasting as little time as possible on turns and repeated strips.
A practical scenario
A farm operator uses an autonomous tractor with a six-meter sprayer boom and RTK GPS positioning accurate to a few centimeters. The field is an irregular polygon of about 40 hectares with a pond and a power line pole inside.
The coverage planner splits the field into four cells around the obstacles, chooses a sweep direction parallel to the longest boundary in each cell and sets the overlap at about five percent of the boom width, since positioning is precise. Headland passes along the borders give the tractor room to turn. Compared with manual driving, the plan reduced overlapping spray strips, which lowered chemical use, and the recorded pose history confirmed that no strip was missed.