A robot you can't break
Real robots are wonderful, but they cost money, their batteries run flat, and a robot with a bug in its program can drive off the edge of a table or push over a cup of tea. So professional roboticists almost always try their ideas in a simulation first: a program that pretends to be the robot and its world. Only when the simulated robot behaves do they load the program onto the real one.
In this lesson you will build exactly that: a simulated robot that lives in a world made of squares. You will teach it to move, turn and feel for walls; then to escape a maze using one simple rule; then to head for a goal and steer round an obstacle in its way. Along the way your robot will get stuck and go round in circles, which is the best way to learn how to debug.
You will need some Python: variables, if, loops, functions and lists. If any of those are new, Lumenary CS's first programs and the lessons after it teach them from the beginning.
A world made of squares
Picture a robot on a floor of square tiles, like a chessboard. Some squares are walls; the rest are open floor. We describe each square by its row (counting down from the top, starting at 0) and its column (counting across from the left, starting at 0). We draw the world with text: # for a wall and . for floor.
The robot always stands on one square and faces one of four directions, which we call by compass letters: N (up the screen), E (right), S (down) and W (left). It can do only four things:
- move forward one square, unless a wall is in the way;
- turn left or turn right by a quarter turn, staying on the same square;
- sense whether there is a wall on the next square ahead (later, also to its right or left), like a bump switch or a short-range distance sensor from How robots sense the world.
Definition— grid world and state
A grid world is a simplified world made of squares, each either open or blocked. The robot's state is everything we need to know about it at one moment: here, its row, its column and the direction it is facing.
A grid world leaves out almost everything about a real robot: wheels slip, sensors are noisy, and real turns are never exactly 90 degrees. That is fine. A simple model lets us think clearly about the logic of a robot program, and the same logic carries over to real robots later.
Building the robot in Python
Here is the whole robot in about sixty lines. The world is a list of strings; the robot is a dictionary holding its state. Press Run, then read the explanation below.
# A robot in a grid world. "#" is a wall and "." is open floor.
WORLD = [
"########",
"#......#",
"#.###..#",
"#......#",
"########",
]
HEADINGS = ["N", "E", "S", "W"] # in clockwise order
STEP = {"N": (-1, 0), "E": (0, 1), "S": (1, 0), "W": (0, -1)}
ARROW = {"N": "^", "E": ">", "S": "v", "W": "<"}
robot = {"row": 1, "col": 1, "facing": "E"}
def turn_right(robot):
i = HEADINGS.index(robot["facing"])
robot["facing"] = HEADINGS[(i + 1) % 4]
def turn_left(robot):
i = HEADINGS.index(robot["facing"])
robot["facing"] = HEADINGS[(i + 3) % 4]
def cell_ahead(robot):
dr, dc = STEP[robot["facing"]]
return robot["row"] + dr, robot["col"] + dc
def wall_ahead(robot): # the robot's only sensor
r, c = cell_ahead(robot)
return WORLD[r][c] == "#"
def forward(robot):
if wall_ahead(robot):
print("Bump! A wall is in the way, so the robot stays put.")
else:
robot["row"], robot["col"] = cell_ahead(robot)
def show(robot):
for r in range(len(WORLD)):
line = ""
for c in range(len(WORLD[r])):
if r == robot["row"] and c == robot["col"]:
line += ARROW[robot["facing"]]
else:
line += WORLD[r][c]
print(line)
print()
show(robot)
forward(robot)
forward(robot)
turn_right(robot)
forward(robot) # there is a wall below: bump!
turn_left(robot)
forward(robot)
forward(robot)
turn_right(robot)
forward(robot)
forward(robot)
show(robot)
print("The robot is at row", robot["row"], "column", robot["col"], "facing", robot["facing"])How it works:
HEADINGSlists the four directions in clockwise order. Turning right moves one place along the list; turning left moves three places, because three right turns face the same way as one left turn. The% 4("remainder after dividing by 4") wraps round fromWback toN.STEPsays how the row and column change when the robot moves one square in each direction. Moving north decreases the row number, because rows are counted from the top.wall_aheadis the robot's sensor: it looks at the square in front and reportsTrueif it holds a#.forwardchecks the sensor first. If there is a wall, it prints "Bump!" and the robot stays where it is.showprints the world with an arrow (^,>,v,<) where the robot stands.
The robot started at row 1, column 1, facing east. It moved two squares, turned right and tried to move south into the wall below (bump!), turned back east, moved two more squares, turned right and moved two squares down. It ends at row 3, column 5, facing south.
Try it: add commands at the end to drive the robot to the bottom-left corner, or change the world by adding a # somewhere and see your old commands bump into it.
Loops and decisions: escaping a maze
Typing every move by hand works in a small room, but not in a maze whose layout the robot doesn't know. We need a rule: a decision the robot makes again and again, in a loop, using only what its sensors tell it. One of the oldest is the right-hand rule.
Definition— right-hand rule
To follow a wall with the right-hand rule, repeat:
- If there is no wall on your right, turn right and step forward.
- Otherwise, if there is no wall ahead, step forward.
- Otherwise, turn left (and decide again).
It is like walking through a dark maze with your right hand always touching the wall. The program below gives the robot two sensors (wall ahead, and wall to the right) and runs the rule in a loop. It tries the rule twice: in a maze, and in an open room with a door. Each run has a step limit, max_steps, so that if the robot never gets out, the program still ends.
# The right-hand rule: keep your right hand on the wall and walk.
MAZE = [
"###########",
"#...#.....#",
"#.#.#.###.#",
"#.#...#...#",
"#.#####.###",
"#.....#....",
"###########",
]
ROOM = [
"#########",
"#.......#",
"#.......#",
"#.......#",
"#.......#",
"#........",
"#########",
]
HEADINGS = ["N", "E", "S", "W"]
STEP = {"N": (-1, 0), "E": (0, 1), "S": (1, 0), "W": (0, -1)}
def turn_right(robot):
robot["facing"] = HEADINGS[(HEADINGS.index(robot["facing"]) + 1) % 4]
def turn_left(robot):
robot["facing"] = HEADINGS[(HEADINGS.index(robot["facing"]) + 3) % 4]
def wall_to_the(world, robot, side): # side: "ahead", "right" or "left"
i = HEADINGS.index(robot["facing"])
if side == "right":
i = (i + 1) % 4
elif side == "left":
i = (i + 3) % 4
dr, dc = STEP[HEADINGS[i]]
return world[robot["row"] + dr][robot["col"] + dc] == "#"
def forward(robot):
dr, dc = STEP[robot["facing"]]
robot["row"] += dr
robot["col"] += dc
def follow_right_wall(world, robot, exit_cell, max_steps):
trail = [(robot["row"], robot["col"])]
for step in range(1, max_steps + 1):
if not wall_to_the(world, robot, "right"): # opening on the right: take it
turn_right(robot)
forward(robot)
elif not wall_to_the(world, robot, "ahead"): # else straight on, if we can
forward(robot)
else: # else turn left, think again
turn_left(robot)
trail.append((robot["row"], robot["col"]))
if (robot["row"], robot["col"]) == exit_cell:
print("Out after", step, "steps!")
return trail
print("Gave up after", max_steps, "steps.")
return trail
def show(world, trail):
for r in range(len(world)):
line = ""
for c in range(len(world[r])):
line += "*" if (r, c) in trail else world[r][c]
print(line)
print()
print("The maze:")
robot = {"row": 1, "col": 1, "facing": "S"}
show(MAZE, follow_right_wall(MAZE, robot, (5, 10), max_steps=200))
print("An open room with a door in the right-hand wall:")
robot = {"row": 3, "col": 4, "facing": "N"}
trail = follow_right_wall(ROOM, robot, (5, 8), max_steps=200)
show(ROOM, trail)
print("The first 9 positions:", trail[:9])In the maze, the rule works: the robot is out after 44 steps (a step here is one pass round the loop, so turns count as steps too). It wanders into the dead end at the bottom left, because that is where its right hand leads it, then comes back and carries on.
In the open room, it fails. The robot starts in the middle, where there is no wall on its right, so it turns right and steps forward; there is still no wall on its right, so it does it again, and again. The first nine positions show it going round the same four squares: (3, 4), (3, 5), (4, 5), (4, 4) and back to (3, 4). Without the step limit, it would go round for ever.
The fix is to give the robot a sensible start: first drive straight until you meet a wall, then turn left so that the wall is on your right, and only then start following. You will write that in the exercises, and then the robot reaches the door in 16 more steps.
The rule has a second weakness. If the exit is in the middle of the maze, surrounded by walls that are not joined to the outer wall (like an island), a wall-follower can walk round and round the outside for ever without reaching it. For mazes like that, a robot needs a map and a planning method, which you will meet in Graph search for planning. Maze-solving robot mice have competed in Micromouse contests since the late 1970s, especially in Japan, Taiwan, the United Kingdom and the United States; the fastest explore the maze, build a map and then race along the shortest route.
A bug that steers round obstacles
Often a robot knows where it wants to go (a charging dock, a table to deliver to) but not what is in the way. In the 1980s the researchers Vladimir Lumelsky and Alexander Stepanov studied simple, guaranteed strategies for this, now called bug algorithms because they are as simple as an insect's behaviour. Here is a grid version in the same spirit:
- Go mode: turn to face the goal and step towards it.
- If a wall blocks the way, remember how far you are from the goal, and switch to follow mode: follow the obstacle's edge with the right-hand rule.
- While following, whenever you are closer to the goal than where you hit the obstacle, and the way towards the goal is clear, switch back to go mode.
The robot measures "how far" by counting squares across plus squares up or down, ignoring walls, which is easy to work out from rows and columns.
# A "bug" robot: head for the goal; if blocked, follow the obstacle's edge
# until you are closer to the goal than where you hit it, then head off again.
FIELD = [
"############",
"#..........#",
"#.....#....#",
"#.....#....#",
"#.....#...G#",
"#.....#....#",
"#..........#",
"############",
]
GOAL = (4, 10)
HEADINGS = ["N", "E", "S", "W"]
STEP = {"N": (-1, 0), "E": (0, 1), "S": (1, 0), "W": (0, -1)}
def turn_right(robot):
robot["facing"] = HEADINGS[(HEADINGS.index(robot["facing"]) + 1) % 4]
def turn_left(robot):
robot["facing"] = HEADINGS[(HEADINGS.index(robot["facing"]) + 3) % 4]
def wall_to_the(robot, side):
i = HEADINGS.index(robot["facing"])
if side == "right":
i = (i + 1) % 4
elif side == "left":
i = (i + 3) % 4
dr, dc = STEP[HEADINGS[i]]
return FIELD[robot["row"] + dr][robot["col"] + dc] == "#"
def forward(robot):
dr, dc = STEP[robot["facing"]]
robot["row"] += dr
robot["col"] += dc
def distance_to_goal(robot): # steps along the grid, ignoring walls
return abs(GOAL[0] - robot["row"]) + abs(GOAL[1] - robot["col"])
def face_goal(robot):
if GOAL[1] > robot["col"]:
robot["facing"] = "E"
elif GOAL[1] < robot["col"]:
robot["facing"] = "W"
elif GOAL[0] > robot["row"]:
robot["facing"] = "S"
else:
robot["facing"] = "N"
robot = {"row": 4, "col": 1, "facing": "E"}
mode = "go"
trail = [(4, 1)]
steps = 0
while (robot["row"], robot["col"]) != GOAL and steps < 100:
steps += 1
if mode == "go":
face_goal(robot)
if wall_to_the(robot, "ahead"):
mode = "follow"
hit_distance = distance_to_goal(robot)
print("Blocked at", (robot["row"], robot["col"]), "- following the edge")
turn_left(robot) # keep the obstacle on the right
else:
forward(robot)
else: # mode is "follow": the right-hand rule from the maze
if not wall_to_the(robot, "right"):
turn_right(robot)
forward(robot)
elif not wall_to_the(robot, "ahead"):
forward(robot)
else:
turn_left(robot)
if distance_to_goal(robot) < hit_distance: # closer than when we hit it?
old_facing = robot["facing"]
face_goal(robot)
if wall_to_the(robot, "ahead"):
robot["facing"] = old_facing # still blocked: keep following
else:
mode = "go"
print("Free at", (robot["row"], robot["col"]), "- heading for the goal")
here = (robot["row"], robot["col"])
if here != trail[-1]:
trail.append(here)
if (robot["row"], robot["col"]) == GOAL:
print("Reached the goal in", len(trail) - 1, "moves.")
else:
print("Gave up after", steps, "steps.")
for r in range(len(FIELD)):
line = ""
for c in range(len(FIELD[r])):
line += "*" if (r, c) in trail and FIELD[r][c] == "." else FIELD[r][c]
print(line)The robot drives east until the wall blocks it at (4, 5), where it is 5 squares from the goal. It follows the wall up, round the top and back down; at (3, 7) it is only 4 squares from the goal and the way east is clear, so it heads for the goal again, arriving after 15 moves.
When things go wrong
Every robot programmer, from beginners to the engineers who drive Mars rovers, spends much of their time finding out why a robot did something unexpected. Here are the problems you are most likely to meet, and what to do about them.
It goes on for ever. A loop whose stopping condition is never reached runs for ever, like the wall-follower in the open room. Always give a robot loop a step limit (or, on a real robot, a time limit), and when it is reached, print a message rather than quietly stopping.
It gets stuck. A robot can be "busy" without making progress: turning left and right in a corner, or bumping the same wall again and again. One test for this is to keep a list of where the robot has been and check whether it keeps returning to the same squares facing the same way.
It goes the wrong way. A swapped sign or a mixed-up row and column sends the robot north when you meant south. These mistakes are easy to make and easy to find, if you look.
How to look:
- Print a trace. Print the robot's row, column, heading and decision on every pass round the loop, and read it next to a drawing of the world. The moment the trace disagrees with what you expected is where the bug is.
- Test in tiny worlds. A 3-by-3 room with one wall is much easier to reason about than a big maze. Check each function on its own: does
turn_leftfour times bring you back to the start? - Change one thing at a time, and run the program after each change.
- Explain it out loud, line by line, to a friend or even a toy. You will often hear yourself say the mistake.
Lumenary CS's Finding and fixing mistakes has much more on this.
Trying it on real robots
The ideas in this lesson are exactly the ones used on educational robots, and you can try them for real or in a free simulator.
- The BBC micro:bit, from a foundation in the United Kingdom, is a small programmable board used in schools in many countries; many low-cost robot cars are built around it. You can program it with blocks or in MicroPython.
- LEGO Education kits, from Denmark, combine motors and sensors with a block-based or Python programming app.
- Arduino boards, from Italy, are at the heart of countless hobby robot kits, programmed in a version of C++.
- The Thymio, developed in Switzerland, is a small robot full of sensors, designed for schools.
- Open Roberta Lab, from the Fraunhofer institute in Germany, lets you program several educational robots in your browser and test the programs in its built-in simulator; Webots, from Switzerland, is an open-source simulator that universities use.
Here is a taste of real hardware code: a sense–think–act loop for a micro:bit, which shows an arrow when the board is tilted. It is MicroPython for the micro:bit itself, so it is not run here.
# MicroPython for a BBC micro:bit (not run here: it needs the real board)
from microbit import *
while True:
tilt = accelerometer.get_x() # SENSE: how far it is tilted sideways
if tilt > 300: # THINK
display.show(Image.ARROW_E) # ACT: show an arrow
elif tilt < -300:
display.show(Image.ARROW_W)
else:
display.show(Image.HAPPY)
sleep(100) # wait 100 milliseconds, then repeatWhen you work with a real robot, choose a small, slow, battery-powered one, run it on the floor rather than on a table, keep fingers and hair away from wheels and gears, and have a way to stop it quickly. Professionals take the same care, and in Robots and people you will see why big industrial robots need much more.
Professional robots run loops like yours many times a second, and their programs are split into many cooperating parts that read sensors, plan and drive motors at the same time. You will meet the software that most research robots use in ROS 2 and robot software, and much better simulators in Simulation.
Common misconceptions
Misconception
"If the program has no error messages, it is correct." Python happily runs a robot that goes round in circles for ever. Errors that crash the program are the easy kind; a robot that does the wrong thing calmly is the kind you find only by testing and tracing.
Misconception
"The right-hand rule solves every maze." It is guaranteed only when the walls are all joined together. If the robot starts in open space, or the goal sits on an island of walls, it can loop for ever.
Misconception
"A simulation is just a game." Simulations are serious engineering tools, used to test robots, self-driving cars and spacecraft before they meet the real world. The art is knowing what a simulation leaves out (here: slipping wheels, noisy sensors, imperfect turns) and checking those things on the real machine.
Misconception
"Turning left needs its own special code." Three right turns face the same way as one left turn, which is why turn_left adds 3 instead of subtracting 1. Spotting that two actions are really the same is a useful programming habit.
Exercises
Several exercises ask you to trace a robot by hand, and two ask you to program one. Draw the grid on squared paper if it helps.
1. Your first robot program
Warm-upComputationalUse the world from the first program in the lesson:
########
#......#
#.###..#
#......#
########
The robot starts at row 1, column 1, facing east (rows and columns count from 0 at the top left). It runs these commands:
forward(robot)
forward(robot)
forward(robot)
turn_right(robot)
forward(robot)
forward(robot)
How many times does it print Bump!?
2. Your first robot program
Warm-upComputationalIn the lesson, HEADINGS = ["N", "E", "S", "W"], and turn_left uses HEADINGS[(i + 3) % 4], where i is the position of the current heading. The robot faces N (position 0) and turns left. What does it face now, and why?
3. Your first robot program
CoreComputationalWrite run(commands). The robot starts at row 0, column 0, facing "E", on an open floor with no walls. commands is a string of letters: "F" means one step forward, "R" means turn right and "L" means turn left. Return the robot's final (row, col, facing).
The starter already handles "F", but ignores turns. For example, run("FFRFF") should return (2, 2, "S").
4. Your first robot program
CoreHumanThe wall-following program has a step limit, max_steps=200. In the maze, the robot gets out after 44 steps, so the limit never matters. Why is it there?
5. Your first robot program
CoreHumanIn which of these situations can a robot using the right-hand rule fail to reach the goal, even though a path exists?
6. Your first robot program
CoreComputationalKofi copies the robot program but types this line:
STEP = {"N": (1, 0), "E": (0, 1), "S": (1, 0), "W": (0, -1)}
His robot turns correctly, but whenever it faces north and moves forward, it goes down the screen. Which change fixes it?
7. Your first robot program
StretchComputationalFix the open-room problem. Write drive_to_wall(world, robot), which drives the robot forward until there is a wall straight ahead, and returns how many steps it took. (If a wall is already ahead, it takes no steps and returns 0.)
The tests then use your function to fix the wall-follower: drive to a wall, turn left so the wall is on the right, and follow it out of the room's door.
Further reading and resources
- Open Roberta Lab · Fraunhofer IAISA free, open-source online environment for programming educational robots, with a built-in simulator.
- micro:bit · Micro:bit Educational FoundationA small programmable board used in schools in many countries, with lessons and projects; many robot kits are built around it.
- Webots · CyberboticsAn open-source robot simulator used in universities and research, with ready-made models of many real robots.
- ArduinoOpen-source microcontroller boards and software, the heart of many hobby and school robots.