Deciding what to do: state machines

Watch the robot vacuum from the first module a little longer than you did then. It rolls across the floor, meets a chair leg, stops, backs off a little, turns, and rolls on. Later, low on charge, it heads for the dock in the corner and parks itself. At any moment it is doing one of a few things, and something it senses moves it from one to the next. This module is about how that is written down. If you came here through the maps and planning modules, the flat map is theirs and the rover on it is the same one; this time it carries no map and no plan, and it is playing the vacuum.

A few things it can be doing

Here is the vacuum's whole brain, in words: five things it can be doing, and it is always doing exactly one of them.

Clean: drive forward. Back up: reverse. Turn: turn on the spot, to the left. Go to dock: turn toward the dock and drive to it. Docked: stop.

And here are the rules that move it from one to another. While it is cleaning, if the dock comes into view, go to the dock; if it bumps something, back up; if a wall is close ahead, turn. While backing up, after one second, turn. While turning, when the way ahead is clear, clean. While going to the dock, when the dock is reached, stop; if it bumps something, back up.

That is all of it. Engineers call the five things states and this way of writing a brain a state machine: a short list of states, each one thing the robot does, with rules for leaving each state for another. The robot is in one state at a time and does what that state says, and every trip round the sense-think-act loop it checks only whether one of the rules leaving its current state has come true. Each rule is a transition: the state it leaves from, the condition the robot must sense for it to fire, and the state it goes to.

A state machine is usually drawn: each state a circle, each transition an arrow between two circles with its condition written beside it, and the start state marked. The box below draws the vacuum's, and lights the circle it is in.

Once round the loop

Put this against the loop from the first module. Sense: the rover reads its five distance sensors, drawn in the box as beams fanned out from its nose, and whether its nose is pressed against something. It also senses the dock, which the box calls the beacon as the first module did: "in view" means within about a meter, roughly ahead, with nothing between, as if the dock sent out a signal the rover recognizes, which is what a real dock does. Think: ask of each arrow leaving the circle it is in, in the order written, whether its condition holds right now; the first that does fires, and the robot is in the circle at its other end. If none does, it stays. Act: do what the circle says. Then round again, many times a second.

The think step is tiny, and that is the point. In Clean the robot considers three arrows and nothing else; in Docked, none. It never asks what it should be doing, only whether it is time to stop doing this. The order matters, because the first arrow whose condition holds is taken: in the box, "the dock is in view" is written above "a wall is close ahead", so a vacuum that sees its dock past a nearby wall heads for the dock rather than turning away.

The state is the memory

Here is what a state machine gives a robot that the first module's brain did not have. That brain was a reflex: this instant's readings, turned straight into this instant's command for the wheels. It needed to remember nothing, and it could not.

Now watch the Turn state, and two numbers inside its arrows. "A wall is close ahead" means one of the three forward beams reads under thirty centimeters; "the way ahead is clear" means all three read over sixty. The rover drives at a wall, the first fires, and it starts turning. Within a fraction of a second the beams read more than thirty, and a reflex with one rule, turn while a wall is within thirty centimeters and otherwise drive, would drive again, read twenty-nine, turn again, and chatter along the wall's edge. The rover in the box keeps turning because it is in Turn, and the only way out of Turn is the sixty-centimeter arrow. Nothing in a reading between thirty and sixty says which state it is in; the state says.

Back up is plainer still. The rover bumps, and for one whole second it reverses, though from the first moment nothing it senses says "back up": the bump is over and the beams show open floor. What keeps it reversing is a timer that started when it entered the state. A state is a decision the robot has made and is holding to until a rule written in advance says it is finished: the difference between "turn away from the wall" and "turn away, and then carry on".

The box

The room is seen from above, three meters by two and a half. A sofa stands against the top wall, a table's four legs make a square on the right, a chair leg sits lower left, and the dock is the gold dot on the right wall. The rover starts near the bottom left corner, facing up the page, with its five beams drawn to wherever they hit. The picture on the right is the state machine: five circles, with the state the rover is in lit orange, the start state ringed thick, and every arrow labeled with its condition in short: wall ahead, way clear, bumped, beacon in view, at the beacon, after 1 s. When an arrow fires it lights up for a moment.

Under the picture are the buttons: Play and Pause run the clock, and Reset puts everything back. Below them, one line says which state the rover is in, how many seconds it has been going, what its front beam reads, and how many changes of state it has made. Then comes the machine written out, and you can change it: each state's name, what it does and whether it is the start; each transition's from, when and to; a Remove button on every line, and buttons to add. Run puts the rover back at the start and sets it going with the machine as written, whatever you have changed; Reset puts the original back. The box opens paused, with Clean lit.

Waiting for the first frame…

Starts the rover again with the machine as written below.

States — what it does in each

starts here

Changes — when it moves from one state to another

Fromwhengo to

Fromwhensgo to

Fromwhengo to

This is easier on a larger screen, but it works here too.

What you saw

Nobody wrote the rover's route. Five states and seven arrows met one room, and a route came out: up the wall, turn, down, turn, along, in. Change the room or the machine and a different route would. That is how a robot with a few lines of rules does something that looks, from outside, like a plan.

The second try showed two roads out of one state. The beams' arrow was the polite road: turn before the wall arrives. The bumper's was the backup, and with the first gone the robot still docked, rougher and a few seconds later. A real vacuum is written this way on purpose: a sensor can miss what a bumper cannot, and the backup costs one arrow.

The third try is the one to remember. Every arrow fired exactly as written, and the rover cleaned the same lap for ever without once facing its dock. A state machine does exactly what its arrows say, and no arrow said "after a while, try something else". It is not stuck the way a wheel against a wall is stuck; it is doing precisely what it was told, which is worse, because nothing will ever look wrong.

When it goes wrong

Two ways a state machine fails are on this page, and a third is worth trying. On the machine as written the rover never bumps in this room, so use the second try's machine, which does: take the arrow "after one second" out of Back up and press Run. The rover bumps, reverses into the wall behind it, and stays there. Back up has no way out, so the robot is in it for ever. A state with no arrow leaving it is a trap, and the fix is always the same: one more arrow.

The third way matters as robots grow. Add a state for a low battery, one for being lifted, one for a cliff ahead, one for carpet, and each needs arrows to and from most of the others: bumped must be handled in Clean, in Go to dock, in the carpet state, in the low-battery state. Ten states can need forty arrows, a tangle nobody can check by eye.

That tangle is why many robots now write the same decisions as a behavior tree: a list of behaviors in order of priority, checked from the top every trip round the loop, so that the robot runs the first behavior on the list whose condition holds. A behavior that takes time, such as backing up for a second, keeps its own count of whether it is finished, so the memory lives inside the behavior rather than in an arrow. For the vacuum: back up if bumped, and until the second is up; else go to the dock if it is in view; else turn if a wall is close, and until the way is clear; else clean. The bump rule is written once, at the top, and interrupts whatever was running, instead of being copied into every state it could interrupt. The behaviors and conditions are the same; nobody has to draw the arrows. For five states either is easy to read; for fifty, only the list is.

What it is for

Nearly every robot has one or the other at the top of its brain. A vacuum's states are the ones here, with a dozen more for the battery, the bin and the stairs. A warehouse robot's are drive to the shelf, wait, carry, unload, return, charge. An arm on a line runs approach, grasp, lift, place, release. And if you have read the earlier modules of this part, their ideas are states too: plan a route, follow it, dodge what the route did not know about, and when the dodging has carried the robot off the route, plan again. Each is a module's worth of thinking, and the state machine is the line above them all, deciding which to be running now.

What the simulation leaves out

The rover here is a drawing, not a body: its wheels do exactly what they are told, a bump costs nothing, and it never slips or tips. Its beams are exact and instant, and the dock's signal is a plain yes or no. The numbers inside the conditions, thirty centimeters, sixty, one second, were chosen by hand; on a real robot they are tuned by trying them. And a real machine has dozens of states and runs above planners like those in the last few modules; this one runs alone in a room.

Watch

Making a State Machine: Part VII - Robot in Action with 3 states — Carlotta A. Berry, PhD (1:42 of it, starting at 0:06)

Why this video: A real robot running a state machine of three states, built by students, with one light on its back for each state so you can see which one it is in, the way the box lights a circle. The professor who set the project says in half a minute what each state does and what moves the robot between them: wander when there is nothing to do, track a phone's flashlight when it sees one, and back up and turn away when the distance sensor finds something ahead. Then the robot is on the floor in the dark, and you watch the light change color as the machine changes state, with the state's name written on the picture. It is this page's machine with a flashlight for the dock, on a robot you could build.
What to watch for: At 0:13 she names the three states and their lights: green for random wander, blue for tracking the light, red for avoiding an obstacle. At 0:33 the avoid state is two of the box's states in one, "back up and turn away", triggered by the sonar the way the box's Back up is triggered by a bump. From 0:42 watch the light and the caption together: the robot wanders green, meets something and turns red as it backs off and turns, and goes blue when the phone light is held out for it to follow. Every change of color is an arrow on the diagram firing.

Words introduced

state machine: A way of writing a robot's brain as a short list of states, each one thing the robot does, with rules for leaving each state for another. The robot is in exactly one state at a time, does what that state says, and every trip round the sense-think-act loop checks only whether one of the rules leaving its current state has come true.
transition: One rule of a state machine, an arrow on its diagram. It names the state it leaves from, the condition the robot must sense for it to fire, and the state it goes to. The transitions leaving a state are checked in order, and the first whose condition holds is the one that fires.
behavior tree: A way of writing the same decisions as a list of behaviors in order of priority, checked from the top every trip round the loop, so that the robot runs the first behavior on the list whose condition holds; a behavior that takes time keeps its own count of when it is done. A rule like "if bumped, back up" is written once, at the top, instead of once for every state it could interrupt.

Where next

Suggested next: 33. Telling a robot what to do: commands, loops, timing — The arm is back with no sliders under it, only a program: eleven lines that lift it, wait, wave three times and report where the shoulder ended up. Read it, run it, change a number, and ask for an angle it cannot reach.