"We cannot solve our problems with the same thinking we used when we created them."
Albert Einstein
State machines are a nice way to write many programs, especially those for embedded and robotic applications. But for someone new to programming, they often seem like a complex, black art subject. That is too bad, because they are very useful and really one of the simplest and best ways to write many programs. So, let's change that. My aim is to show you how and why to use a state machine in your programs, and especially how easy it is.
State machines are quite common. In fact, EVERY program that runs on a computer is a state machine. But what we will discuss here is a more formal way of designing a program to look specifically like a state machine. Many programs you use on your pc and many libraries you use with arduinos and such are designed that way. In addition, much of the computer hardware you use is designed as a state machine. Some examples: The "network stack" in your PC or network shield, the USB chips in your PC and peripherals, the USB software stacks in both, the interface to your hard disk, the I2C interface on your microcontroller. There are many, many more examples. That is just a taste. Notice that about half those examples are hardware. That is because state machines are really simple and easy to implement in hardware. They are just as simple and useful in software, but often the descriptions and explanations are overly complex. Quite often, if you Google for state machines, you will come across some complex looking explanations with lots of theory and jargon. Let's get rid of most the complexity and concentrate on the basics. You can find the rest later if you want or need to, and it should be a lot easier to understand once you know what is really going on.
A state machine is a group of pre-defined steps (states) that indicate a stage of processing, and a defined way to move between them based on input.
That is all there is to it. But that probably still isn't very clear. So let's look at an example. Suppose we want to build an obstacle avoiding robot, with a single obstacle sensor on the front. The robot should move forward until it detects an obstacle, then turn until the path is clear. Once the path is clear, it should continue to move forward in the new direction. In addition, the robot can measure its battery voltage, and when the voltage falls below a threshold, it should stop. We will give each state a descriptive name. Here is the list of states:
There we have our four states. The next thing we need is a defined way to move from one state to another. This is pretty simple: what conditions will make the machine change state, and what state will it change to? Let's make some rules for our desired behavior. Here are our rules:
That is the complete definition of the state machine. We just need to turn it into a program, or part of a program. There are many ways to do that, and I will show you my favorite shortly. But first, let me show you a shorthand way of describing a state machine.
The normal way of describing a state machine is not with a bunch of text as we have, but with a "state diagram." It usually has a rounded box to indicate each state, with labeled arrows from one to another indicating the "transitions" between states. Like this:
The state boxes are labeled with the name of the state, and the arrows are labeled with the condition(s) that will cause that transition. I don't normally write the state machine as text, prefering to go straight to a state diagram. The diagram above was drawn with the open source program "dia" which I recommend for not only state diagrams, but many other types of drawing as well. ( like UML diagrams)
Now, how do we make this into a program fragment? As I mentioned, there are many ways to do it. I will show my favorite way in C language, since that is what I mostly use and is the closest thing to a standard we have for small computers. Since Arduino is based on a mix of C and C++ this method will work fine there.
The first thing we need to do is give names to each of our states in a way that can be used in the program. The program will be much simpler and efficient if we used integers, so we will define named constants to represent the states. I will introduce a part of C you may not be familiar with, but was designed for exactly this sort of thing: the enum.
enum MOVEMENT_STATES
{
MOVEMENT_INITIAL,
MOVEMENT_FORWARD,
MOVEMENT_TURNING,
MOVEMENT_HALT
};
that creates four constants with the given names and will assign them values
from 0 to 3 in sequence. If we wanted each one to have a specific value,
we could put that in by placing an equal sign and the value after the name,
like this:
MOVEMENT_INITIAL = 99,But we don't care about the actual values, just the names. Let the C compiler worry about the details. The enum actually creates a new data type but they are compatible with integers, and that is how we will use them.
Next, our machine should be a function, so we will create a function that does the work of our machine:
int movement_state_machine(void)
{
static int state = MOVEMENT_INITIAL;
int new_state = state;
return new_state;
}
That is the skeleton of our machine. It doesn't do anything yet, but let's
take a look at what we have so far.
We defined a function named "movement_state_machine" that will handle the details of the machine. It will return an integer value and will not take any input ("void"). Inside the function, we declare two local variables: state and new_state, both integers. "state" is also declared as "static" which means it will retain its value when the function returns. It will also be intialized to "MOVEMENT_INITIAL" when the program starts, but can be changed inside the function as we see fit. The variable "new_state" is not static, so it will be created anew every time the function is called, with garbage as the value. That's ok, because we assign it a value when we create it, the same value as "state" is holding. At the end of the function, we return the value of "new_state" in case our program needs to know what state we are in after the machine does its processing.
Well, that is the machine, but like a car with no engine it doesn't do much other than look good. Let's put an engine in it. The engine of our state machine needs to do a couple things. It needs to decide what actions to take, and what state to move into or stay in the current state, depending on the current state and the inputs. C has another construct that is perfectly suited to these tasks: the "switch" statement.
The switch statement takes an integer input value (characters are a type of integer, by the way) and "jumps" to a label with the same value if one exists. If none of the constant labels match, it jumps to the "default" clause if one exists. I urge you to ALWAYS include a default clause, even though the language doesn't require it. I assure you, that habit will save you a lot of grief at some time in your programming. Anyway, here is what the function looks like with the switch statement in it:
int movement_state_machine(void)
{
static int state = MOVEMENT_INITIAL;
int new_state = state;
switch(state)
{
case MOVEMENT_INITIAL:
// perform intialization here
new_state = MOVEMENT_FORWARD;
break;
case MOVEMENT_FORWARD:
break;
case MOVEMENT_TURNING:
break;
case MOVEMENT_HALT:
break;
default:
// If the state somehow became something else, it is an error.
// In that case, the safe thing to do is HALT
new_state = MOVEMENT_HALT;
break;
}
state = new_state;
return new_state;
}
We added in the switch statement, and filled in a bit of code. It still
isn't complete, but you can see the structure of it. The way the switch
works is this: when it enters at the top ( the "switch(state)" ) it checks the
value of state and compares it to each "case" value. If one of them
matches the value, it jumps to the code following that label and begins
to execute the code from that point. The "break" statement causes the
switch statement to exit, moving to the code following (the line "state =
new_state" in our example.) If we didn't include the break at the end
of each block of code, it would "fall through," which is a sometimes
useful neat trick that causes more problems than it solves. Always
include your break statements. If none of the labels match, it jumps to
the "default" clause. In our case, that means something went terribly
wrong, so we will assign the new state to HALT for safety.
After the switch statement executes, it assigns new_state to state, so
if we changed state it gets updated as the current state. Then we exit
the function, returning the value of the new state. The state machine,
as we have built it here, runs only once and exits. Your main code needs
to call this function periodically to continue updating the state and
actions as needed. We could have included a loop to run the machine over
and over, but since most robot and embedded programs already have loops
like that, we can just put our function call inside the main loop.
We have an engine in our machine, but it still needs a steering wheel and
accelerator. Let's add those now:
int movement_state_machine(void)
{
static int state = MOVEMENT_INITIAL;
int new_state = state;
switch(state)
{
case MOVEMENT_INITIAL:
// perform intialization here
new_state = MOVEMENT_FORWARD;
break;
case MOVEMENT_FORWARD:
// turn both motors on to go forward
left_motor_forward();
right_motor_forward();
// check the input condition, change state if needed
if( get_battery_volts() < MINIMUM_VOLTS)
{
next_state = MOVEMENT_HALT;
}
else if( obstacle_detected())
{
next_state = MOVEMENT_TURNING;
}
break;
case MOVEMENT_TURNING:
// turn to the left by spinning wheels opposite directions
left_motor_backward();
right_motor_backward();
if( get_battery_volts() < MINIMUM_VOLTS)
{
next_state = MOVEMENT_HALT;
}
else if( ! obstacle_detected())
{
next_state = MOVEMENT_FORWARD;
}
break;
case MOVEMENT_HALT:
// low battery or other error condition
// shut down everything except warning LED
left_motor_off();
right_motor_off();
distance_sensor_off();
warning_light_on();
break;
default:
// If the state somehow became something else, it is an error.
// In that case, the safe thing to do is HALT
new_state = MOVEMENT_HALT;
break;
}
state = new_state;
return new_state;
}
And that is all. We have a complete state machine. Each time the function
is called, it decides what it should do based on the current state and
the inputs (battery voltage and obstacle sensor.) The main program loop
needs to call it every so often, like each time through the loop. Notice
that the state machine calls other functions to find out the battery voltage,
control the motors, and determine if there is an obstacle. The code within
the state machine should ONLY determine what actions need to be taken for
the machine itself.
State machines can be very simple, like our example, or much more complex. The quad core cpu in your new desktop computer uses a very complex group of state machines to execute instructions. The registers in the cpu (both the ones "visible" to the programmer and those hidden away internally) hold the current state, and the incoming instruction and data it operates on are the input that determine next state.
I hope this introduction has been useful. State machines are everywhere. Many problems that seem complex at first become simple when programmed as a state machine. I encourage you to try it out on a problem of your own, and as you get more familiar to read some of the more in-depth information available. State machines are a very handy tool in your kit.