How do robot vacuums know where to go?
How a robot vacuum finds its way round a room: bump and go, wall following and spirals, then knowing where it is, mapping the room and planning lanes. Watch four methods clean the same mat on a small robot and see how much floor each covers in 80 seconds.
Many robot vacuums do not know where they are going at all. The simplest ones drive in a straight line until they bump into something, turn a random amount and set off again, and add a spiral for a dirty patch and a run along the walls for the edges. Over a long clean those random paths reach most of the floor, but they cross some places many times and can miss others. Smarter robot vacuums keep track of where they are, build a map of the room as they go, and plan back and forth lanes that cover each part of the floor once. On this page a small robot cleans the same 1.5 metre mat with four boxes on it in four different ways, and each demo below is a real program you can change and run.
In the overhead view of each demo, light blue squares are floor the robot has cleaned and the blue line is where it has been. To score each method, the program cuts the mat into 10 cm squares, 213 of them outside the boxes, and counts a square as cleaned once the middle of the robot has been in it. The robot is 7 cm across, so this is a generous score, and every demo uses the same one. The chart shows % covered, the share of the 213 floor squares cleaned so far, and % of edges, the same for the 84 floor squares next to a wall or a box. Every demo cleans for 80 seconds.
Two kinds of robot vacuum
bump and go: map and plan:
drive forward work out where you are
if you bump into something: mark the map: cleaned here,
back off blocked there
turn a random amount drive to the next square in
go again the plan not yet cleaned
The first kind needs almost no sensors and almost no computing. It is how the first home robot vacuums worked, and it is still how many cheaper ones work. The second kind needs to know where it is, which is the hard part, and a map to plan on. The rest of this page builds up from the first kind to the second.
What a robot vacuum can sense
- A bump sensor. The front of the robot is a sprung bumper. When it hits something it moves back a little and presses a switch, so the robot knows it has touched something and roughly which side.
- Cliff sensors. Infrared sensors under the front edge point down at the floor. If the floor suddenly is not there, at the top of a stair, the robot stops and backs away.
- A wall sensor. A sensor on the side measures how far away the wall is, so the robot can run along it without touching it.
- Wheel odometry. Sensors on the wheels count how far each wheel has turned, and a gyro measures how fast the robot is turning. Adding these up gives an estimate of where the robot is.
- Lidar or cameras. Robots that map a room carry a range sensor: often a lidar, a laser that spins on top and measures the distance to everything round the robot, or a camera that picks out features of the room.
The robot on this page is not a vacuum, and it has no wheels: vibration motors shake its feet, and it can drive forwards, sideways and turn on the spot. It has its own versions of some of these. bumped() is true for a moment after its accelerometer feels the jolt of a collision. velocity() says how fast it is actually moving, so a robot that is told to drive and is not moving has stalled against something. odometry() is where it thinks it is, from an optical flow sensor that watches the mat slide past underneath and a gyro. In the simulator, position() is exact, as if a camera over the mat were watching.
Bump and go
The robot drives forward at full speed. When it bumps into something, or stalls, it backs off 3 cm and turns right by a random angle between 100 and 260 degrees, then drives forward again. That is the whole method.
The program
from bugbot import *
import random
connect()
# change these and press Run
SEED = 1 # a different seed, a different run
random.seed(SEED)
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
# edge squares: floor squares next to a wall or a box
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
cleaned, trail = set(), []
next_draw = 0
def sweep():
# mark the square the robot is on, and plot the scores
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
trail.append((x, y))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
if clock() >= next_draw: # redraw once a second
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("path", trail, "blue", "line")
next_draw = clock() + 1
was_hit, since = False, 0
def hit_something():
# a new bump, or told to drive and not moving (a stall)
global was_hit, since
b = bumped()
new = b and not was_hit
was_hit = b
stalled = clock() - since > 0.6 and velocity()[1] < 3
if new or stalled:
backward(60, distance=3) # back off a little
since = clock()
return True
return False
bumps = 0
while clock() < 80:
if hit_something():
bumps += 1
# turn a random amount, then go again
turn_right(100, angle=random.randint(100, 260))
since = clock()
forward(100)
wait(0.1)
sweep()
stop()
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
The robot bumps 12 times in 80 seconds and cleans 25 % of the floor. The blue line shows why it does not do better. It crosses the middle of the room up and down more than once, cleaning the same squares again, and it never gets further left than 67 cm across the mat, so the two boxes on the left side of the room are never reached. Much of its time goes on backing off and turning rather than cleaning: the chart climbs in steps, with flat parts where the robot is turning or driving over squares it has already cleaned.
Each run is different, because the turns are random. Change SEED and run it again. Over seeds 1 to 20, the robot cleaned between 15 % and 36 % of the floor in 80 s, 25.9 % on average, and 20.8 % of the edges on average.
Random bouncing works better than it sounds, given time. Each new straight line is likely to cross some floor it has not been on, so on a long clean in an ordinary room it reaches most places in the end. The cost is time and battery: the longer it runs, the more of what it drives over is already clean.
Edges and spirals
Two more simple moves fill in what bouncing misses.
Edge following runs along the walls and round furniture, where a random path rarely goes. A robot with a wall sensor keeps a steady distance from the wall. This robot follows an edge by touch: it curves gently to the right, towards the wall, and each time it bumps it turns 45 degrees left, away from it. So it runs round the room with the wall on its right, touching it every few centimetres.
A spiral cleans one patch thoroughly: the robot drives round in circles that grow by one lane width each time round. Robot vacuums use it for a spot of dirt, or to start a clean. Here the radius grows by 10 cm a turn, and the spiral stops at the first bump.
This demo starts with a spiral, then follows the edges for the rest of the 80 seconds.
The program
from bugbot import *
import math, random
connect()
# change these and press Run
SEED = 1
EDGE_TIME = 80 # seconds of edge following at a time
BOUNCE_TIME = 15 # then this many seconds of bouncing
random.seed(SEED)
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
# edge squares: floor squares next to a wall or a box
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
cleaned, trail = set(), []
next_draw = 0
def sweep():
# mark the square the robot is on, and plot the scores
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
trail.append((x, y))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
if clock() >= next_draw: # redraw once a second
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("path", trail, "blue", "line")
next_draw = clock() + 1
was_hit, since = False, 0
def hit_something():
# a new bump, or told to drive and not moving (a stall)
global was_hit, since
b = bumped()
new = b and not was_hit
was_hit = b
stalled = clock() - since > 0.6 and velocity()[1] < 3
if new or stalled:
backward(60, distance=3) # back off a little
since = clock()
return True
return False
mode, until = "spiral", 80
turned = 0 # degrees turned in the spiral
bumps = 0
while clock() < 80:
hit = hit_something()
if hit:
bumps += 1
if mode == "spiral":
if hit: # the spiral ends at the first bump
mode, until = "edge", clock() + EDGE_TIME
else:
# the radius grows by 10 cm each time round
r = 8 + 10 * turned / 360
rate = min(120, math.degrees(20 / r)) # deg/s
drive(100, 0, rate / 1.2)
turned += rate * 0.1
elif mode == "edge":
if hit:
turn_left(100, angle=45) # away from the wall
since = clock()
drive(100, 0, 20) # curve right, back to it
if clock() > until:
mode, until = "bounce", clock() + BOUNCE_TIME
else:
if hit:
turn_right(100, angle=random.randint(100, 260))
since = clock()
forward(100)
if clock() > until:
mode, until = "edge", clock() + EDGE_TIME
wait(0.1)
sweep()
stop()
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
The spiral cleans 10.8 % of the floor in the first 14 seconds, until it meets the corner of a box. Edge following then spends about 9 seconds bumping round that corner, and another 8 at the top wall, turning away and curving back into it. From 39 seconds it settles along the walls, and runs anticlockwise along the top, down the left side and along the bottom. In that time the % of edges line climbs from 7 % to 37 %, higher than any of the 20 bump and go runs. Apart from the spiral, it hardly goes near the middle of the room.
Simple robot vacuums switch between these moves on timers or when they bump a certain number of times. Try it: set EDGE_TIME = 20 and the robot follows edges for 20 seconds, bounces for 15, and repeats. On this small mat mixing did not help in 80 seconds: over seeds 1 to 20 it averaged 25.3 % of the floor and 22.8 % of the edges, about the same as bump and go.
Knowing where you are
To clean in tidy lanes, and to know which parts of the floor are done, a robot has to know where it is. With no view of the room from outside, it works that out by adding up its own movements, which is called dead reckoning or odometry. A wheeled robot vacuum counts how far each wheel has turned and reads the gyro for how much it has turned. This robot reads its optical flow sensor and its gyro, and odometry() adds them up.
Every measurement is a little wrong, and odometry adds every error in, so the estimate drifts: the further the robot goes, the further out it is. A wheel that slips on a rug, or a gyro that reads a tiny turn when there is none, both show up as a position that is wrong and getting worse. The dead reckoning guide shows how the drift grows and how to calibrate some of it away.
Robot vacuums that map a room correct the drift with their lidar or camera. They compare what the sensor sees now with the map they have built so far, and move their estimate to where the two agree. Doing both at once, building a map and finding yourself on it, is called SLAM: simultaneous localisation and mapping. A particle filter is one of the standard ways to find a robot on a map.
A map of the room
The map a robot vacuum keeps is often an occupancy grid: the floor cut into small squares, each marked free, blocked or not yet known. A lidar fills it in from a distance, one laser beam at a time. The occupancy grid mapping guide builds one with this robot's depth sensor.
The demos below keep a much simpler map, made by touch, in the same 10 cm squares as the score. It starts empty. When the robot bumps into something, it marks the square it was heading for as blocked. It also keeps a set of the squares it thinks it has been on. The boxes typed into the program are only used for the score, and the robot never sees them.
Planning a sweep
With a map and a position, the robot can plan. The plan here is the pattern you see on a mown lawn: up the first column of squares, across one, down the next, and so on across the mat. It is called a boustrophedon path, from the Greek for "as the ox turns" when ploughing.
The robot takes the next square in the plan that it has not been on and is not blocked, and finds a route there on its map with a breadth-first search, which goes round anything it has marked as blocked. It drives to each square of the route in turn, always facing up the mat and sliding sideways when it needs to. When it bumps into a box, the square goes on the map and it finds a new route. In this demo the robot knows exactly where it is, from position(), which stands in for a mapping robot that keeps its position right with a lidar or camera.
The red squares are the squares its map says are blocked. The chart has a third line, % it thinks: the score worked out from where the robot thinks it has been.
The program
from bugbot import *
import math
from collections import deque
connect()
# change these and press Run
ODOMETRY = False # True: the robot steers by odometry() alone
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
# the robot's own map: squares it has found blocked, and
# squares it believes it has been on. Both start empty.
blocked, been = set(), set()
def route(a, b):
# breadth-first search on the map, from square a to square b
came = {a: None}
todo = deque([a])
while todo:
c = todo.popleft()
if c == b:
break
i, j = c
for n in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= n[0] < N and 0 <= n[1] < N and \
n not in blocked and n not in came:
came[n] = c
todo.append(n)
if b not in came:
return []
path = []
while b is not None:
path.append(b)
b = came[b]
return path[::-1][1:]
# the plan: up the first column of squares, down the next...
lanes = []
for i in range(N):
column = [(i, j) for j in range(N)]
lanes += column[::-1] if i % 2 else column
cleaned, trail, belief = set(), [], []
next_draw = 0
def sweep(bx, by):
# score from the true position, and from the robot's belief
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
trail.append((x, y))
belief.append((bx, by))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
plot("% it thinks", len(been & FLOOR) * 100 / len(FLOOR))
if clock() >= next_draw: # redraw once a second
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("blocked", [(i * CELL + 5, j * CELL + 5)
for i, j in blocked], "red", "squares", 5)
draw("belief", belief, "red", "line")
draw("path", trail, "blue", "line")
next_draw = clock() + 1
def where():
# where the robot thinks it is, and which way it faces
if ODOMETRY:
x, y, h = odometry()
else:
(x, y), h = position(), heading()
return 75 + x, 75 + y, h
def push(p):
# under 15 % the robot does not move at all
if abs(p) < 4:
return 0
return math.copysign(max(17, min(100, abs(p))), p)
bumps, k = 0, 0
path, was_hit = [], False
while clock() < 80 and k < len(lanes):
x, y, h = where()
been.add((int(x // CELL), int(y // CELL)))
if lanes[k] in been or lanes[k] in blocked:
k += 1 # been there, or cannot go there
path = []
continue
if not path:
path = route((int(x // CELL), int(y // CELL)), lanes[k])
if not path: # no way there on the map
k += 1
continue
tx, ty = path[0][0] * CELL + 5, path[0][1] * CELL + 5
dx, dy = tx - x, ty - y
d = math.hypot(dx, dy)
if d < 4:
path.pop(0) # reached this square: on to the next
continue
hit = bumped()
if hit and not was_hit:
# something is in the way: mark that square on the map
bumps += 1
was_hit = True
blocked.add(path[0])
path = []
drive(push(-dy / d * 60), push(-dx / d * 80), 0)
wait(0.3) # back away from it
continue
was_hit = hit
# drive towards the square at 20 cm/s, facing up the mat
vx, vy = 20 * dx / d, 20 * dy / d
turn = (0 - h + 180) % 360 - 180
drive(push(vy * 5), push(vx * 100 / 15), push(turn * 2))
wait(0.1)
sweep(x, y)
stop()
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
print("it thinks:", round(len(been & FLOOR) * 100 / len(FLOOR)), "%")
The robot drives from the middle of the mat to the bottom left corner and starts its lanes. It cleans about 6.5 % of the floor every 10 seconds for the first 50 seconds, then more slowly as it works round the box at the top, and ends on 42 %, with 43 % of the edges. Its 12 bumps are all against the two boxes on the left, and each one puts a red square on its map; after that it goes round them. Most of what it drives over is new floor, so the chart climbs as a straight line with few flat parts. The % it thinks line lies on top of % covered, because the robot knows where it is.
The plan does not finish: at up to 20 cm/s, every lane across this mat is more driving than fits in 80 seconds. It gets further than bump and go in the same time mostly because it never stops to back off and turn a random amount. Per metre driven, the two were close in these short runs, about 7 new squares a metre each. The difference shows on a longer clean, at the end of the page: the lanes keep reaching new floor until they finish, while a random path finds less and less of it.
Many mapping robots also split the house into rooms, clean each room in lanes, and run along the edges of each one. The route from one place to another is a pathfinding problem. A* is the usual way to solve it on a grid: it finds a route as short as the breadth-first search here, usually after looking at fewer squares.
When the robot is wrong about where it is
The same program with ODOMETRY = True. Now the robot works out where it is from odometry() alone, with no camera. The red line is where it thinks it has been, and the blue line is where it went.
The program
from bugbot import *
import math
from collections import deque
connect()
# change these and press Run
ODOMETRY = True # True: the robot steers by odometry() alone
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
# the robot's own map: squares it has found blocked, and
# squares it believes it has been on. Both start empty.
blocked, been = set(), set()
def route(a, b):
# breadth-first search on the map, from square a to square b
came = {a: None}
todo = deque([a])
while todo:
c = todo.popleft()
if c == b:
break
i, j = c
for n in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= n[0] < N and 0 <= n[1] < N and \
n not in blocked and n not in came:
came[n] = c
todo.append(n)
if b not in came:
return []
path = []
while b is not None:
path.append(b)
b = came[b]
return path[::-1][1:]
# the plan: up the first column of squares, down the next...
lanes = []
for i in range(N):
column = [(i, j) for j in range(N)]
lanes += column[::-1] if i % 2 else column
cleaned, trail, belief = set(), [], []
next_draw = 0
def sweep(bx, by):
# score from the true position, and from the robot's belief
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
trail.append((x, y))
belief.append((bx, by))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
plot("% it thinks", len(been & FLOOR) * 100 / len(FLOOR))
if clock() >= next_draw: # redraw once a second
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("blocked", [(i * CELL + 5, j * CELL + 5)
for i, j in blocked], "red", "squares", 5)
draw("belief", belief, "red", "line")
draw("path", trail, "blue", "line")
next_draw = clock() + 1
def where():
# where the robot thinks it is, and which way it faces
if ODOMETRY:
x, y, h = odometry()
else:
(x, y), h = position(), heading()
return 75 + x, 75 + y, h
def push(p):
# under 15 % the robot does not move at all
if abs(p) < 4:
return 0
return math.copysign(max(17, min(100, abs(p))), p)
bumps, k = 0, 0
path, was_hit = [], False
while clock() < 80 and k < len(lanes):
x, y, h = where()
been.add((int(x // CELL), int(y // CELL)))
if lanes[k] in been or lanes[k] in blocked:
k += 1 # been there, or cannot go there
path = []
continue
if not path:
path = route((int(x // CELL), int(y // CELL)), lanes[k])
if not path: # no way there on the map
k += 1
continue
tx, ty = path[0][0] * CELL + 5, path[0][1] * CELL + 5
dx, dy = tx - x, ty - y
d = math.hypot(dx, dy)
if d < 4:
path.pop(0) # reached this square: on to the next
continue
hit = bumped()
if hit and not was_hit:
# something is in the way: mark that square on the map
bumps += 1
was_hit = True
blocked.add(path[0])
path = []
drive(push(-dy / d * 60), push(-dx / d * 80), 0)
wait(0.3) # back away from it
continue
was_hit = hit
# drive towards the square at 20 cm/s, facing up the mat
vx, vy = 20 * dx / d, 20 * dy / d
turn = (0 - h + 180) % 360 - 180
drive(push(vy * 5), push(vx * 100 / 15), push(turn * 2))
wait(0.1)
sweep(x, y)
stop()
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
print("it thinks:", round(len(been & FLOOR) * 100 / len(FLOOR)), "%")
The red lanes are straight, because the robot steers them straight by its own estimate. The blue lanes lean. The robot's gyro reads a small turn that is not there, so its idea of which way is up the mat drifts: 7 degrees out after 40 seconds and 15 degrees after 80. Its position estimate is 10 cm out at 40 seconds and 15 cm out at 74 seconds.
The score hardly changes in 80 seconds, 41 % against 42 %, because a lane that leans still crosses new floor. What goes wrong is the map. Of the squares the robot has on its list as done, 11 it never touched, and it will not go back for them. At 74 seconds it bumps into the bottom edge of the mat 15 cm to the left of where it thinks it is, and marks a square of clear floor as blocked. Left to run until it believes it has finished, this robot stops after 161 seconds with 82 % of the floor cleaned, against 97 % for the same plan with its position kept right (the ten minute demos below show both). A robot that cleaned a whole house like this would leave strips it believed were clean, and its map would stop matching the rooms. That is why mapping robot vacuums keep checking their position against the room with a lidar or camera.
The four side by side
| Method | Floor cleaned in 80 s | Edges cleaned in 80 s | Bumps in 80 s | What it needs |
|---|---|---|---|---|
| Bump and go | 25 % | 21 % | 12 | a bump sensor |
| A spiral, then the edges | 26 % | 37 % | 22 | a bump sensor; a wall sensor helps |
| Planned lanes with a map | 42 % | 43 % | 12 | a map, and its position kept right |
| Planned lanes on odometry | 41 % | 42 % | 12 | a map and odometry |
Bump and go is the cheapest. Edge following reaches the edges that bouncing misses. Planning covers the most floor in a set time, and only works as well as the robot's idea of where it is. But 80 seconds is a short clean, and the next two demos run for longer.
A longer clean
The same room with ten minutes on the clock. This is the bump and go program from the top of the page, left to run for 590 seconds, just under ten minutes. To keep the picture light it draws its line one point a second and redraws every 5 seconds.
The program
from bugbot import *
import random
connect()
# change these and press Run
SEED = 1 # a different seed, a different run
random.seed(SEED)
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
# edge squares: floor squares next to a wall or a box
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
cleaned, trail = set(), []
next_draw = 0
def sweep():
# mark the square the robot is on, and plot the scores
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
if len(trail) < clock(): # one point a second for the line
trail.append((x, y))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
if clock() >= next_draw: # redraw every 5 seconds
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("path", trail, "blue", "line")
next_draw = clock() + 5
was_hit, since = False, 0
def hit_something():
# a new bump, or told to drive and not moving (a stall)
global was_hit, since
b = bumped()
new = b and not was_hit
was_hit = b
stalled = clock() - since > 0.6 and velocity()[1] < 3
if new or stalled:
backward(60, distance=3) # back off a little
since = clock()
return True
return False
bumps = 0
while clock() < 590: # just under ten minutes
if hit_something():
bumps += 1
# turn a random amount, then go again
turn_right(100, angle=random.randint(100, 260))
since = clock()
forward(100)
wait(0.1)
sweep()
stop()
next_draw = 0
sweep() # draw the final picture
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
The first 80 seconds are the same as before, 25 %. Then the line climbs in bursts with long flat stretches: from 70 to 220 seconds it gains less than 4 %, while the robot crosses floor it has already cleaned. It ends on 79 % of the floor after 91 bumps. Over seeds 1 to 5 it finished between 79 % and 88 %, and at 3 minutes it was on between 29 % and 57 %.
This is the planned lanes program, left to run until it has been to every square in its plan it can reach. It draws two points a second.
The program
from bugbot import *
import math
from collections import deque
connect()
# change these and press Run
ODOMETRY = False # True: the robot steers by odometry() alone
# the floor, cut into 10 cm squares. The boxes are typed in
# only to know which squares are floor; the robot never sees this.
CELL, N = 10, 15
BOXES = [(22.5, 30, 18, 18), (105, 37.5, 18, 18),
(37.5, 105, 18, 18), (97.5, 97.5, 18, 18)]
def in_box(x, y):
return any(bx < x < bx + w and by < y < by + h
for bx, by, w, h in BOXES)
FLOOR = {(i, j) for i in range(N) for j in range(N)
if not in_box(i * CELL + 5, j * CELL + 5)}
EDGES = {(i, j) for i, j in FLOOR
if any(n not in FLOOR for n in
((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)))}
# the robot's own map: squares it has found blocked, and
# squares it believes it has been on. Both start empty.
blocked, been = set(), set()
def route(a, b):
# breadth-first search on the map, from square a to square b
came = {a: None}
todo = deque([a])
while todo:
c = todo.popleft()
if c == b:
break
i, j = c
for n in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= n[0] < N and 0 <= n[1] < N and \
n not in blocked and n not in came:
came[n] = c
todo.append(n)
if b not in came:
return []
path = []
while b is not None:
path.append(b)
b = came[b]
return path[::-1][1:]
# the plan: up the first column of squares, down the next...
lanes = []
for i in range(N):
column = [(i, j) for j in range(N)]
lanes += column[::-1] if i % 2 else column
cleaned, trail, belief = set(), [], []
next_draw = 0
def sweep(bx, by):
# score from the true position, and from the robot's belief
global next_draw
x, y = position()
x, y = 75 + x, 75 + y # the robot starts at (75, 75)
cleaned.add((int(x // CELL), int(y // CELL)))
if len(trail) < 2 * clock(): # two points a second for the lines
trail.append((x, y))
belief.append((bx, by))
plot("% covered", len(cleaned & FLOOR) * 100 / len(FLOOR))
plot("% of edges", len(cleaned & EDGES) * 100 / len(EDGES))
plot("% it thinks", len(been & FLOOR) * 100 / len(FLOOR))
if clock() >= next_draw: # redraw every 5 seconds
draw("cleaned", [(i * CELL + 5, j * CELL + 5)
for i, j in cleaned & FLOOR], "#a8d8f0", "squares", CELL)
draw("blocked", [(i * CELL + 5, j * CELL + 5)
for i, j in blocked], "red", "squares", 5)
draw("belief", belief, "red", "line")
draw("path", trail, "blue", "line")
next_draw = clock() + 5
def where():
# where the robot thinks it is, and which way it faces
if ODOMETRY:
x, y, h = odometry()
else:
(x, y), h = position(), heading()
return 75 + x, 75 + y, h
def push(p):
# under 15 % the robot does not move at all
if abs(p) < 4:
return 0
return math.copysign(max(17, min(100, abs(p))), p)
bumps, k = 0, 0
path, was_hit = [], False
while clock() < 590 and k < len(lanes):
x, y, h = where()
been.add((int(x // CELL), int(y // CELL)))
if lanes[k] in been or lanes[k] in blocked:
k += 1 # been there, or cannot go there
path = []
continue
if not path:
path = route((int(x // CELL), int(y // CELL)), lanes[k])
if not path: # no way there on the map
k += 1
continue
tx, ty = path[0][0] * CELL + 5, path[0][1] * CELL + 5
dx, dy = tx - x, ty - y
d = math.hypot(dx, dy)
if d < 4:
path.pop(0) # reached this square: on to the next
continue
hit = bumped()
if hit and not was_hit:
# something is in the way: mark that square on the map
bumps += 1
was_hit = True
blocked.add(path[0])
path = []
drive(push(-dy / d * 60), push(-dx / d * 80), 0)
wait(0.3) # back away from it
continue
was_hit = hit
# drive towards the square at 20 cm/s, facing up the mat
vx, vy = 20 * dx / d, 20 * dy / d
turn = (0 - h + 180) % 360 - 180
drive(push(vy * 5), push(vx * 100 / 15), push(turn * 2))
wait(0.1)
sweep(x, y)
stop()
next_draw = 0
sweep(*where()[:2]) # draw the final picture
print("finished after", round(clock()), "s")
print("bumps:", bumps)
print("covered:", round(len(cleaned & FLOOR) * 100 / len(FLOOR)), "%")
print("edges:", round(len(cleaned & EDGES) * 100 / len(EDGES)), "%")
print("it thinks:", round(len(been & FLOOR) * 100 / len(FLOOR)), "%")
It finishes after 182 seconds, about 3 minutes, with 97 % of the floor cleaned, more than any of the five bump and go runs managed in almost ten minutes. The 3 % it misses are squares against the boxes that it marked as blocked after bumping into them, so it never went into them.
Now set ODOMETRY = True. The robot steers by its own estimate again, and stops after 161 seconds believing it has finished. It thinks it has cleaned 83 % of the floor; it has cleaned 82 %, and the two are not the same squares. Its map has 38 blocked squares, and 17 of them have their middle 10 cm or more from any box or wall. 23 squares it has on its list as done it never touched. The plan was the same, and the difference is only in how well the robot knows where it is.
| Method | Floor cleaned | Time |
|---|---|---|
| Bump and go | 79 % to 88 % (seeds 1 to 5) | 590 s, still going |
| Planned lanes with a map | 97 % | finished after 182 s |
| Planned lanes on odometry | 82 % | stopped after 161 s, believing it had finished |
Questions
How does a robot vacuum know where to go?
It depends on the robot. Simple ones do not know: they drive until they bump into something, turn and go again, with spirals and runs along the walls mixed in, and cover the floor by chance over a long clean. Mapping ones keep track of where they are by adding up their wheel movements and checking against a lidar or camera, build a map of the room, and plan lanes across it.
Do robot vacuums just move randomly?
The simpler ones mostly do. Their turns after each bump are random, so each run takes a different path. On this page, bump and go cleaned between 15 % and 36 % of a small room in 80 seconds depending on the random turns. Robots that build a map drive in planned lanes instead.
How does a robot vacuum map a room?
It measures the distance to walls and furniture with a lidar or a camera as it moves, and marks what it sees on a grid of small squares: free, blocked or unknown. At the same time it works out where it is on that grid by matching what it sees now with what is already on the map. This is called SLAM, simultaneous localisation and mapping.
What is SLAM in a robot vacuum?
Simultaneous localisation and mapping: building a map of the room while working out where you are on that map. Each needs the other, since the map is drawn from where the robot thinks it is, and the robot finds itself by comparing its sensors with the map. Robot vacuums with a lidar or a camera do this so that their position does not drift as it would with wheel odometry alone.
How does a robot vacuum avoid falling down stairs?
With cliff sensors: infrared sensors under the front edge that point down at the floor. When the floor is not where it should be, the robot stops and backs away. They can be fooled by very dark floors and rugs, which reflect little infrared light and can look like a drop.
Why does my robot vacuum bump into things?
A bump and go robot uses bumps as its main sensor, so it touches almost everything. Robots with a lidar or camera see most things before they reach them, but low things, thin chair legs, glass and mirrors can be missed by the range sensor, so they still have a bumper as a backup. The demos on this page find every box by bumping into it.
Why does my robot vacuum miss spots?
A robot that moves at random may not reach a spot at all in the time it runs: in the first demo the robot never reached the left side of the room in 80 seconds. A robot that plans lanes misses spots when it is wrong about where it is, because it marks floor as done that it never touched. In the last demo that was 11 squares out of 213 after 80 seconds.
What is the boustrophedon or lawnmower pattern?
Back and forth lanes: up one lane, across by one lane width, down the next, and so on, like mowing a lawn. The name is Greek for "as the ox turns", from ploughing a field. A robot uses it to cover an area once without crossing its own path. Obstacles break the lanes up, so a planner splits the room into pieces and covers each piece in lanes.
Is a mapping robot vacuum better than a random one?
On the same floor in the same time, a mapping robot that knows where it is covers more. On this page it cleaned 42 % of a small room in 80 seconds against 25 % for bump and go, and finished 97 % of the room in about 3 minutes, when bump and go had cleaned 79 % to 88 % after almost 10. A random robot gets most of the way on a long enough clean and needs far fewer sensors. A mapping robot can also usually be sent to clean one room.
How does a robot vacuum know where it is?
It adds up its own movements from wheel sensors and a gyro, which is called odometry or dead reckoning. That estimate drifts, so robots that map correct it by matching what their lidar or camera sees against the map. On this page, the robot's odometry was 15 degrees out in its heading after 80 seconds with nothing to correct it.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- 2.1 Where am I? Sensing, Robot club
- 2.2 The distance sensor Sensing, Robot club
- 2.3 The depth grid Sensing, Robot club
- 6.6 Bumps and stalls Seeing more, Robot club
- U3.2 Write your own odometry Odometry and drift, University
- U8.1 A map of cells Mapping, University
- U8.4 Building a grid Mapping, University
- U8.6 Frontiers Mapping, University