Coverage Path Planning
Some robots do not need to get somewhere, they need to go everywhere: lawn mowers, floor cleaners, crop sprayers, and inspection drones. Coverage planning finds a path that passes over every part of an area. The simplest systematic method sweeps back and forth in rows, like mowing a lawn.
Boustrophedon sweeping
The word means "as the ox turns", like plowing. Split the area into cells that each have no obstacle inside, then sweep each cell in parallel rows spaced one tool width \(w\) apart. The path length is roughly
A random bouncer drives straight until it hits something, then turns a random amount. Its coverage keeps growing, but more and more slowly, because it keeps crossing places it has already cleaned.
What to notice
Systematic sweeping reaches nearly full coverage in about the time it takes to drive \(A/w\), then stops. Random bouncing covers the easy middle quickly, then spends a long time finding the last corners, and its coverage curve flattens out. Early robot vacuums used random bouncing, which needs no map. Modern ones map the room first and then sweep it in rows.