M8-T2 — Coverage Path Planning

Learning objectives

After this lesson, you should be able to:

• Set lane spacing from the tool width and an overlap, and compute the number of lanes, path length and turns.
• Explain the boustrophedon sweep and why its direction should follow the long side of the area.
• Describe how a cell decomposition lets a sweep handle obstacles, and what the order of cells has in common with route ordering.
• Measure a coverage run by missed area, overlap and turns, and say what causes gaps in practice.

The intuition

Think of mowing a lawn. You do not wander. You walk to one edge, mow a stripe to the opposite edge, shift over by a stripe and walk back. Each stripe is as wide as the mower, so stripes tile the lawn. This is the boustrophedon pattern (the word means “as the ox turns”, the way a plough furrows a field).

The pattern is optimal in the simplest sense: on an empty rectangle every cell is visited once, and the robot never drives without working. What it costs is turns. At each lane end the robot slows, turns and speeds up, and a cleaning robot cannot clean while it turns. So the best direction is usually along the long side of the room, which makes the lanes long and the turns few.

Furniture breaks the pattern. A bed in the middle of a lane splits it into two pieces, and a pillar leaves a lane that has to go around. The standard answer is to cut the floor into obstacle-free cells, sweep each cell with its own simple lanes, and then decide the order in which to visit the cells.

The mathematics

The tool and the lanes

w

tool width (the swath the tool treats, for example the width of the mop head)

o

overlap fraction between neighbouring lanes, for example 0.10

s

lane spacing, s = w (1 − o)

A, ℓ

width of the area measured across the lanes, and the length of a lane

n

number of lanes

The formulas ignore the curve of a turn and the extra distance for turning around at the walls. The last lane overshoots the wall by up to one spacing; real planners shift it back so the lanes end flush with the wall, which adds overlap only in the last lane.

Choosing the direction

For a rectangle the path length hardly changes with the direction, but the number of lanes does: it is proportional to the width measured across the lanes. Sweeping along the long side puts the short side across the lanes, so there are fewer lanes and fewer turns.

Obstacles: cell decomposition

A cell decomposition cuts the free space into regions that can each be covered by plain lanes. The boustrophedon cellular decomposition (Choset and Pignon, 1997) moves a line across the floor and starts a new cell whenever the line is split by an obstacle, or when two pieces join again. It makes fewer, larger cells than a trapezoidal decomposition, so there are fewer turns and fewer connections. Then:

1. Build the adjacency graph: a node per cell, an edge where two cells touch.
2. Choose an order in which to visit all cells. This is a route-ordering problem (lesson M8-T1) on the graph, with the cost of reaching the next cell.
3. Sweep each cell with boustrophedon lanes, entering and leaving near the neighbouring cells.
4. Connect the end of one cell to the start of the next with a shortest path through already-cleaned floor.

Other families exist: grid-based wavefront coverage, and spanning-tree coverage on a grid of robot-sized blocks (Gabriely and Rimon, 2001), which produces a spiral-like path with a guarantee of covering every cell once. Galceran and Carreras (2013) survey these and others.

Measuring coverage

A worked example

A ward corridor lounge, by the formulas. The floor is 12 m × 7.5 m. The mop head is w = 0.6 m, the overlap is o = 10 percent, so the lane spacing is s = 0.6 × 0.9 = 0.54 m. Scout drives at 0.5 m/s and a turn costs 4 s.

Sweeping along the long side saves 91 s, or 17 percent, without any change of algorithm. The ideal is the area divided by the tool width, 90 / 0.6 = 150 m. The 12 m sweep drives 175 m, which is 17 percent more: that is the 10 percent overlap plus the lane shifts and the last lane that overshoots the wall (14 lanes cover 14 × 0.6 − 13 × 0.06 = 7.62 m of a 7.5 m room).

Why the overlap is there. Suppose lanes were spaced at exactly 0.6 m and the robot drifted 5 cm sideways in one lane and 5 cm the other way in the next. A 10 cm strip between them would stay dry. A spacing of 0.54 m leaves 6 cm of overlap, which covers drift up to 6 cm between neighbouring lanes. If the localization error of your robot is larger, widen the overlap, not just the tolerance.

Lab M8-L2. There the floor is a grid of cells and the three stages are the lane sweep, bridging furniture with shortest paths so coverage stays complete, and the report of missed cells, revisits and turns.

Engineering implications and limitations

Plan on the real footprint

The coverage path is a path for the tool, not the robot centre. A tool that sticks out at the side reaches under a bed that the robot cannot enter; a wet mop left behind the robot leaves a trail that the next lane must not drive through. Offset the lanes from the walls by the robot’s inscribed radius (lesson M2-T2), then check that the tool, not only the body, passes the doors.

Turns are not free

A differential-drive robot can turn on the spot; a car-like robot needs a turning radius R, and if the lane spacing is smaller than 2R it cannot go to the adjacent lane directly. The usual fix is to skip lanes and come back for them on the return pass. Either way, the follower (module 5) must handle the sharp changes in heading, and the speed profile must slow for them (lesson M5-T3).

Localization and verification

Lanes only line up if the pose is good. Odometry alone drifts, so cover with a localized map, and after the run compare the swept area with the map. A coverage map, which counts how many times each cell has been inside the tool footprint, is cheap to keep during the run and tells the operator exactly where the dry stripes are. Do not trust “planned lanes completed” as proof: obstacles that appeared during the run, a lane abandoned after a recovery (module 7), or a door that was closed, all leave holes.

Dynamic environments

People and carts block lanes. Common policies are to skip the blocked stretch and revisit it at the end, to wait a limited time, or to replan the remaining cells. Keep the list of uncovered cells explicitly so that these decisions are about cells, not about the original plan.

Common misconceptions

Engineering takeaways

1. Coverage plans a path for the tool: lane spacing is s = w(1 − o), and the overlap o protects against drift.
2. Boustrophedon lanes need n = ⌈(A − w)/s⌉ + 1 lanes and 2(n − 1) turns; sweep along the long side to cut turns.
3. Obstacles are handled by cutting the floor into cells, sweeping each, and ordering the cells like route stops.
4. A coverage run is measured by missed area, overlap, turns, length and time, ideally from a coverage map kept during the run.
5. Plans are not proof: drift, blocked lanes, recoveries and wrong maps all leave gaps that only a check can find.

References and further reading

The cellular decomposition paper, the spanning-tree coverage paper and two surveys.

• H. Choset and P. Pignon, “Coverage path planning: the boustrophedon cellular decomposition”, in Field and Service Robotics, Springer, 1998 (proceedings of the 1997 conference).
• H. Choset, “Coverage for robotics – A survey of recent results”, Annals of Mathematics and Artificial Intelligence 31, 2001.
• Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot”, Annals of Mathematics and Artificial Intelligence 31, 2001.
• E. Galceran and M. Carreras, “A survey on coverage path planning for robotics”, Robotics and Autonomous Systems 61(12), 2013.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: when the map does not exist yet, and the robot has to decide where to look next: frontier exploration.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T1: Waypoint Missions and Route Ordering

  Order a set of stops with nearest-neighbour and 2-opt, and explain why this is hard in general.

• Lab
  M8-L2: Cover the Floor

  Scout must mop every free tile of the ward once: build the sweep and count the missed tiles.