Coverage Path Planning Simulator for Robot Vacuums

Controls

Strategy switches between the three. The room is rebuilt and the run restarts immediately, because a coverage number only means something next to the room it was measured in.

Drag any piece of furniture with the pointer, or press 1–4 to select one and move it with the arrow keys. The run restarts as you drag. Put a table in the middle of the floor and watch the planned sweep’s distance climb while its coverage falls.

New room scatters the furniture again. Run speed trades smoothness for patience — the random strategy needs several thousand moves to finish, so start it on fast.

Theory

A path planner answers how do I get there. A coverage planner answers how do I touch all of it, and the two have almost nothing in common.

The only honest yardstick is the distance a perfect robot would need. With a floor of area A and a brush of width w, sweeping every square once and never repeating takes:

d_optimal = A / w

Everything the lab reports is a multiple of that number. A strategy at 1.2× is spending 20% of its life going over floor it has already done; one at 8× is spending seven eighths of it.

Random bounce has a closed form, and it is not encouraging. A robot with no map covers new floor in proportion to how much is still uncovered, so uncovered area decays exponentially:

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

That is the dashed curve on the plot. Read three points off it: 63% of the floor after one optimal distance, 90% after 2.3, and 99% after 4.6. The last tenth of the room costs twice what the first three quarters did — the coupon collector’s problem, wearing a brush.

Systematic coverage is linear, so it finishes at 1× plus whatever overhead the row spacing and the turns cost. In this lab that overhead is about 35%.

The measured runs land close to the theory, and where they miss they miss in the direction you would expect: a real random walk revisits nearby floor rather than teleporting, so it does slightly worse than the independent-sampling curve suggests.

Algorithm

Random bounce. Drive straight. On a bump, pick a new heading at random and check it is clear. That is the whole thing, and it needs one bit of sensing and no memory at all.

Spiral, then relocate. Turn by an angle inversely proportional to how far you have travelled since the centre, which traces an expanding spiral. On a bump, dash in a straight line for a fixed distance and start a new spiral. Excellent on open floor — a spiral has almost no overlap — and helpless in a cluttered room, where every spiral is cut short after a few turns.

Planned serpentine. Three steps, and the second is the one people skip:

1. Inflate. Grow every obstacle by the robot’s radius plus a safety margin. What is left is where the robot’s centre may go.
2. Slice. Walk down the inflated map in rows one brush width apart. Each row becomes one or more free spans.
3. Join. Visit the spans in serpentine order, and route between consecutive spans with a shortest path through the free space, so the robot drives around the sofa rather than into it.

Step 3 is where the distance overhead comes from, and it is why a cluttered room punishes a planner more than an empty one.

Source code

The random strategy is the one worth having on a real robot first, because it works with sensing you already have:

// Random-bounce coverage. Two bump switches, no map, no encoders.
const uint8_t BUMP_L = 2, BUMP_R = 3;
const uint16_t CRUISE = 170;      // PWM
unsigned long turnUntil = 0;
int turnDir = 1;

void loop() {
  bool left  = digitalRead(BUMP_L) == LOW;   // switches are active-low with pull-ups
  bool right = digitalRead(BUMP_R) == LOW;

  if (millis() < turnUntil) {                 // still executing a bounce
    drive(turnDir * CRUISE, -turnDir * CRUISE);
    return;
  }

  if (left || right) {
    // Back off first — turning while wedged against a chair leg does nothing.
    reverseFor(320);
    // A random turn between 90 and 270 degrees. The randomness is what stops the
    // robot tracing the same closed loop around the room forever.
    turnDir = right ? -1 : 1;
    turnUntil = millis() + random(420, 1250);
    return;
  }

  drive(CRUISE, CRUISE);
}

The bounce angle has to be random. A fixed reflection turns the room into a billiard table, and a billiard ball on a rectangular table traces a closed path that misses most of the surface forever.

The planned sweep needs the inflate-slice-join pass above plus odometry good enough to hold a straight row, which is a different class of robot. Prototype it here, where position is exact by construction, before deciding whether your hardware can carry it.

Assumptions and hardware differences

The lab gives the robot perfect odometry, a perfectly known map, instant turns in place, and a brush that covers a clean circle. A real machine has none of those.

Wheel slip and gyro drift bend the rows apart within about ten of them, which is why commercial robots re-localise against walls, ceiling features or a beacon. Turns take time that this lab charges no distance for. And the brush does not cover a circle — it covers a rectangle behind the robot, so reversing over floor you have already done cleans nothing.

The gap between strategies survives all of it. If a planner beats random bounce by 3× here, it beats it by perhaps 2× on real hardware; the ordering does not change.

Circuit diagram

The sensing splits cleanly into three jobs, and only the first is required.

Bump. Two microswitches on a sprung front bumper, wired active-low to interrupt-capable pins with the internal pull-ups on. This is the sensing that makes random bounce possible and it is the last thing to fail.

Cliff. Downward reflectance sensors at the front corners, read every pass of the loop. A coverage run visits everywhere, which includes the top of the stairs — the arithmetic for how far the robot travels past the edge before it can stop is worked out here.

Position. Quadrature encoders on both wheels, and a gyro if you want rows that stay parallel. Only the planned strategy needs this, and needing it is the whole reason the other two exist.

For the coverage strategies as a build, see the room coverage robot; for the reactive layer underneath all of them, the obstacle avoidance simulator covers stop thresholds and scanning.