The Finite State Machine

Due to WordPress’s abysmal handling of code blocks this blog post is now hosted at https://majenko.co.uk/blog/

Many of the programming questions on the Arduino forum can be answered with one simple response:

Implement a “Finite State Machine.”

But what actually is a “Finite State Machine”?

Put simply, a Finite State Machine (I’m bored with typing that now, let’s call it an FSM – not to be confused with the Flying Spaghetti Monster, of course) is a computer program that, at any point in time, can be in one of a pre-determined number of states. A state is a specific action, such as “Waiting for button 3 to be pressed”, or “Moving the servo to 69°”, for example.

An FSM can replace most of your while, for and similar loops, as well as annoying functions such as delay which get in the way if you want to do more than one thing at a time.

Let’s take a simple example to help illustrate how to make an FSM. Let’s say you have an automatic gate controlling access to a car park. The gate wants to stay closed until a car drives up to it. When the car arrives you want to open the gate and flash a warning light while it opens. Once the gate is open, you need to wait for the car to go through, then give a little extra time, and close the gate, flashing the light while you do.

Sounds pretty straight forward, but how would you go about programming that on, for example, an Arduino?

Well, your first thought is probably “That’s pretty simple. Wait for the signal that the car has arrived, open the gate, wait for the signal that the car has gone through, wait a little extra time, then close the gate. Return to start.

But what about the flashing light? While we’re opening the gate we want to flash a light. Yes, you could go out and buy a light that flashes, but that’s not the point. We want our program to do it. Sounds like a job for an FSM!

Ok, so let’s first sort out a few definitions, shall we? These aren’t “official” terms, but ones I like to use:

• Stimulus

This is any input coming in from outside the FSM, be it a light sensor, a button, some other part of the program, or whatever. More importantly, and this is where it differs from just an “input”, it is a change in a value from a sensor. Such as a button changing from “not pressed” to “pressed”, or a light sensor changing from “light” to “dark”.

• Action

An instruction for something to actually happen, such as opening the gate, turning the light on, etc.

• Static State

A state where the FSM is waiting for stimulus, and is taking no actions.

• Transitional State

A state which causes actions, but doesn’t look for stimulus. A Transitional State runs once and immediately moves on to a Static State.

Let’s take a look at those last two definitions in a little more detail, shall we?

The FSM is, at any one time, in a state. That state is one of two types of state: static or transitional. A static state can be though of one where you are waiting for something to happen. The FSM lingers in that state until whatever it is waiting for has happened. A typical static state is such as “waiting for car to arrive”. The state doesn’t change until the stimulus it is waiting for arrives.

Conversely, a transitional state is one which the FSM is only in very briefly while it actually does something. Atransitional state immediately moves on to another state, typically a static state. An example would be “open gate”, which would immediately move on to “waiting for gate to open”.

Ok, so let’s have a think about what states our FSM might want. States marked with (S) are static, and (T) aretransitional.

1. Wait for car to arrive. (S)
2. Open barrier & start light flashing (T)
3. Wait for barrier to open (S)
4. Stop light flashing (T)
5. Wait for car to drive through (S)
6. Make a note of the current time (T)
7. Wait for a certain number of seconds to pass (S)
8. Close barrier and start light flashing (T)
9. Wait for barrier to close (S)
10. Stop light flashing and go back to step 1 (T)

But hang on, you may say, what about the flashing light? All we have said there is “start light flashing” and “stop light flashing”. How do we actually flash the light? Well, that’s quite simple. The light has its own little FSM that is separate to the barrier FSM.

That one might look like this:

1. Wait for an instruction to start flashing. (S)
2. Turn the light on and remember the current time (T)
3. Wait for time to pass (S)
4. Turn the light off and remember the current time (T)
5. Wait for time to pass (S)
6. Go to step 2 (T)
7. Turn off the light and go to step 1 (T)

Step 1 doesn’t actually have to do anything at all. It can be thought of an “idle” state, where the FSM doesn’t actually do anything. The beauty of Finite State Machines is that one FSM can change the state of another. So, when we say “start the light flashing” in the gate FSM, what we actually mean is “set the state of the light FSM to 2”, and for “stop the light flashing” we mean “set the state of the light FSM to 7. Once the light has started flashing it will continue flashing forever unless something outside the FSM changes the state. This can be thought of as a forced state changebecause something outside the FSM is forcing it to change state, rather than one of the states waiting for a signal to change state. The great thing with a forced state change is that no matter what state the FSM is in it always goes to the same new state. Whether the light is on or off it’s going to turn off the light and go to the idle state.

But how do we actually implement an FSM in code? Well, the simplest way is the switch construct (covered in an earlier tutorial). A simple numeric variable can be used to store the current state, and each case of the switch construct can be one of the states.

For example, this might be how you implement the flashing light FSM:

void setup()
{
  pinMode(13,OUTPUT);
}

void loop()
{
  static int state = 1; // initial state is 1, the "idle" state.
  static unsigned long ts;  // To store the "current" time in for delays.

  switch(state)
  {
    case 1:
      // We don't need to do anything here, waiting for a forced state change.
      break;
    case 2:
      digitalWrite(13,HIGH);  // Turn on the light
      ts = millis();  // Remember the current time
      state = 3;  // Move to the next state
      break;
    case 3:
      // If one second has passed, then move on to the next state.
     if(millis() - ts > 1000)
      {
        state = 4;
      }
      break;
    case 4:
      digitalWrite(13,LOW);  // Turn off the light
      ts = millis();  // Remember the current time
      state = 5;
      break;
    case 5:
      // If one second has passed, then go back to state 2.
      if(millis() - ts > 1000)
      {
        state = 2;
      }
      break;
    case 6:
      // We only get here when forced from outside.
      digitalWrite(13,LOW);  // Turn off the light
      state = 1;  // Return to the "idle" state.
      break;
    default:
      state = 1;
      break;
  }
}

You notice we have combined steps 5 and 6 into state 5, and step 7 has become state 6. This is just for cleanliness. We could have done it exactly the same, but we’d have effectively had a redundant state where it just went straight on to another state.

Also, this snippet won’t actually do anything, as there is no way to force a state change out of the idle state. You might want to experiment by setting the initial state to 2 instead of 1.

So, each time through the loop() function it examines the current state. That state value is uses to perform a selected small snipped of code. If the conditions are right, then the state is changed, so next time through the loop() function a different snippet of code is run.

Implementing multiple FSMs that run at the same time is as simple as having multiple switch() constructs in the loop() function. Notice how there isn’t a single loop of any form in there, except the main loop() function that wraps it all? Delays are all done by comparing the return value of millis() to the stored “ts” variable. for loops can be done by simply incrementing a variable until it reaches a certain value then moving on to another state. Of course, if your for loop is only a couple of iterations and doesn’t cause enough delay to be a problem to the operation of the FSMs you can still use a traditional for loop for small tasks.

One more tip before you go off and make your own FSM. The numbers assigned to the states are purely arbitrary. They could be anything. Anything as long as each state has a unique identifier. If you have more than just a few states it can become quite confusing and hard to remember what number means what state. Make good use of #define to create meaningful names to label your states with. For example, the flashing light FSM above could be rewritten using #definemacros like such:

#define S_IDLE 1
#define S_LEDON 2
#define S_WAITON 3
#define S_LEDOFF 4
#define S_WAITOFF 5
#define S_TURNOFF 6

void setup()
{
  pinMode(13,OUTPUT);
}

void loop()
{
  static int state = S_IDLE; // initial state is 1, the "idle" state.
  static unsigned long ts;  // To store the "current" time in for delays.

  switch(state)
  {
    case S_IDLE:
      // We don't need to do anything here, waiting for a forced state change.
      break;
    case S_LEDON:
      digitalWrite(13,HIGH);  // Turn on the light
      ts = millis();  // Remember the current time
      state = S_WAITON;  // Move to the next state
      break;
    case S_WAITON:
      // If one second has passed, then move on to the next state.
      if(millis() - ts > 1000)
      {
        state = S_LEDOFF;
      }
      break;
    case S_LEDOFF:
      digitalWrite(13,LOW);  // Turn off the light
      ts = millis();  // Remember the current time
      state = S_WAITOFF;
      break;
    case S_WAITOFF:
      // If one second has passed, then go back to state 2.
      if(millis() - ts > 1000)
      {
        state = S_LEDON;
      }
      break;
    case S_TURNOFF:
      // We only get here when forced from outside.
      digitalWrite(13,LOW);  // Turn off the light
      state = S_IDLE;  // Return to the "idle" state.
      break;
    default:
      state = S_IDLE;
      break;
  }
}

Makes it much more readable, yes?

So go and play. Make your next Arduino sketch a Finite State Machine.