The Finite State Machine

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.

5 thoughts on “The Finite State Machine

  1. Peter Geisler

    This is by far the best program hint I ever had in the last time. You have want me to do a rather simple at first view, program to develop under the aspect of a finite state machine. Never I had such clear structur of a program, of an arduino program in special. I wrote some snippets for a dc motor control and had to respect two end-position switches. Exact these two switches have to change the turn-direction of the rather direction left or right. It was an easy game with the structure of a state machine. Have many thanks for that – I won’t forget that lesson and tell other people to do in the same manner.
    Have a nice time.
    Peter

    Like

    Reply
  2. Thomas

    Nice job for pointing out how important an abstract view on the system is. The switch-case pattern is rather typical for a simple state machine implementation. However, once you have more than a handful of states, it is hard to see from the code only how the states are connected to each other. In that case, a graphical model that you would have drawn by hand is useful to easier understand the system.

    In an ideal world, you would model the state machine in an graphical editor and press a button to generate the state machine code, so you would have both, the graphical view and the code always in sync. This can be realized with YAKINDU Statechart Tools, by the way.

    Best regards,
    Thomas

    Like

    Reply
  3. Apollo

    I’m just learning about state machine and found this very helpful , slightly disappointed you didnt stick with the example of the gate opening as my current project is 2 pir sensor lighting a walk way with 4 20w leds coming on at different times to light the way , still a great job 10/10 and a gold star thanks

    Like

    Reply
  4. Jelle

    I say the comment from Thomas about generating the state code. Thanks for that! I’ve made also a standard environment for making a fsm supported by a lot a functions for state conditions. Also a coupling with a scada system based on visual studio. Next step is making an environment for generating code out of a model. See also http://www.jbsiemonsma.nl

    Like

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s