Coverage Path Planning: Sweep a Whole Floor

A different problem from getting there

A* finds one route to one goal. A coverage planner has to touch every reachable square, which changes the objective completely: there is no goal to be near, no heuristic to guide you, and success is not binary.

The measure that replaces it is distance per square metre swept. With floor area A and a tool of width w, a perfect robot sweeps each square once and never repeats:

d_optimal = A / w

A 20 m² room with a 250 mm brush needs 80 m. Every number below is a multiple of that, because a multiple is the only comparison that survives a change of room.

The law that governs sweeping without a map

A robot with no idea where it has been covers new floor in proportion to how much floor is still uncovered. That is a differential equation with one answer:

covered(d) ≈ 1 − e^(−d / d_optimal)

Read three points off it and the shape of the whole problem appears:

The last 9% costs more than the first 90%. This is the coupon collector’s problem with a brush attached, and it is the single fact that explains every robot vacuum you have ever watched.

What actually happens

Theory assumes each metre lands on floor chosen independently. A real robot drives in straight lines, so consecutive metres are correlated — it keeps re-sweeping the patch it is already standing on. Measured over five rooms in the coverage simulator:

Three things in that table are worth more than the rest of this page.

For the first half of the floor, nothing matters. All three strategies are within 20% of each other at 50%. A robot with no sensing and no memory is genuinely as good as a planner for the first half of the job — which is exactly why the cheap approach is commercially viable and why casual observation never reveals the difference.

Random does worse than its own theory. 6.76× against a predicted 4.61× at 99%, because a straight-line bounce keeps revisiting floor it just did. Treat 1 − e^(−d) as the optimistic bound, not the estimate.

The planner never finishes. It stops at 90.4% and stays there, and this is not a bug.

Why the planner leaves a tenth of the floor

A coverage planner has to keep the robot’s body clear of every wall and every table leg, so it inflates each obstacle by the robot’s radius plus a margin and plans inside what is left. Whatever falls outside is floor the robot can never drive to.

In the measured run, 130 of the 133 squares the planner missed were within two cells of a wall or a piece of furniture. Only three were open floor. The misses are not scattered — they are a ring around every obstacle in the room.

Which explains two features of every commercial machine:

• The side brush that overhangs the chassis. The brush is wider than the thing that collides, so it reaches floor the wheels can never get to.
• The wall-following pass. It is a separate behaviour, run separately, because the systematic sweep structurally cannot do it.

Random bounce reaches those edges eventually, by luck, which is the one thing it does better.

Choosing rows

For a systematic sweep the only real parameter is row spacing.

Space rows exactly one brush width apart and any heading error at all leaves an uncleaned stripe between them — and nothing later will find it, because the plan believes that floor is done. Overlap by 10–20% and the stripes close, at a cost of exactly that percentage in distance.

That overlap, plus the transit distance around furniture, is where the planner’s 1.35× comes from. It is not waste; it is the price of a plan that survives contact with a real robot.

Two more choices that matter more than they look:

• Run rows along the long axis of the room. Every turn costs time and covers no new floor, so halving the number of rows halves the turn overhead.
• Route between spans, do not drive between them. When furniture splits a row into two spans, the robot has to go around. Planning that transit as a shortest path through free space is the difference between a plan and a wish.

The sensing each strategy demands

This is the real reason all three exist.

Random bounce needs one bit. Did I hit something. Two bump switches and a random number generator is the entire robot. No encoders, no map, no localisation, and nothing to drift.

Spiralling needs to know how far it has gone since the centre of the current spiral, which is a rough odometry — good enough to grow a radius, not good enough to close a loop.

A planned sweep needs to know where it is. Straight rows, known turn angles, and a sideways step of one brush width are all odometry claims, and odometry drifts. Ten rows in, the rows are no longer parallel. This is why commercial machines that plan also carry a gyro, a ceiling camera or a beacon — the planner is cheap and the localisation it assumes is not.

So the strategy is chosen by the sensing budget, not by the algorithm’s elegance. Build the random one first: it works, it is twenty lines, and it gives you a baseline the planner has to beat.

What it costs in minutes

Take that 20 m² room, a 250 mm brush and a robot cruising at 0.25 m/s:

A battery is a distance budget. A one-hour runtime at 0.25 m/s is 900 m, which comfortably covers one room at random and does not cover three — and that, rather than any algorithmic insight, is what pushed the market toward mapping robots.

When it goes wrong

Run all three against the same room in the coverage simulator — drag the furniture while it runs and the numbers move with it. Then build the room coverage robot, which starts with the strategy that needs nothing and adds sensing only where the measurement says it pays.