Nested Finite State Machines

The standard design pattern for a finite state machine can produce very clear and simple to follow code even for complex real world problems. These are normally implemented as a switch statement and the cases represent the states.

The phasing is so that the case statement for the precursor state sets up the initial conditions for the successor state (switching a led or relay on etc.). That is, when a case statement is entered for a particular state, that state is already active. This would be clear if you attempt to write debug message at the beginning of the case statement and see that it is printed continuously. Anyway, this model is usually fine for the majority of applications.

However, it does sometimes mean that dummy or minor states have to added. For example, if the application includes an external event and that external event can only be processed after a pause, then a dummy buffer state has to be added to implement the pause.

Here is an example of a simple state machine, a button controlled mixer, which waits on an external event, in this case a button press, and requires a pause before starting the mixer motor.

Wait for button press
Wait an additional 1 second and start the mixer motor
Quit after 5 seconds, switching off the motor and back to the start.

The state diagram is something like this:

The code is here https://wokwi.com/projects/455398703321183233

Code

const int button = 4 ;
const int mixerPin = 5 ;

enum class States { WAIT_BUTTON_PRESS, WAIT_BUFFER, IN_MIX } ;
States state = States::WAIT_BUTTON_PRESS ;

uint32_t stateTimer = millis() ;


void setup() {
  Serial.begin(115200);
  pinMode( button, INPUT_PULLUP) ;
  pinMode( mixerPin, OUTPUT) ;
}

void loop() {

  switch ( state ) {

    case States::WAIT_BUTTON_PRESS :
      if ( !digitalRead( button ) ) {
        state = States::WAIT_BUFFER ;
        stateTimer = millis() ;
      }
      break ;


    case  States::WAIT_BUFFER :
      if ( millis() - stateTimer > 1000 ) {
        state = States::IN_MIX ;
        stateTimer = millis() ;
        digitalWrite( mixerPin, HIGH ) ;
      }
      break ;


    case  States::IN_MIX :
      if ( millis() - stateTimer > 5000 ) {
        state = States::WAIT_BUTTON_PRESS ;
        stateTimer = millis() ;
        digitalWrite( mixerPin, LOW ) ;
      }
      break ;

  }
}

The dummy wait states are, of course, simple to implement but can cause clutter that has to be shown in the state diagram.

This design pattern can be extended with an addition to eliminate the need for these dummy states. This, however, requires an addition to the standard design pattern so that, on the new entry to the case statement implementing the state, a variable can be read indicating that this is indeed a new entry. Hence, it can then do its own initialisation. That is at the end of the precursor state there is no longer any setup for the next state. Using this method, the above application could be implemented as follows, dropping the dummy wait:

Wait for button press and pause 1 second
Start mixer motor, run for 5 seconds and return to start.

The state diagram is something like this:

The code is here https://wokwi.com/projects/455398738491473921

Code
/*
Nested state example.

Here a variable is set on change of state so the successor state logic can 
do its own initialisation.




*/


const int button = 4 ;
const int mixerPin = 5 ;

enum class States { WAIT_BUTTON_PRESS_DELAYED,  IN_MIX } ;
States state = States::WAIT_BUTTON_PRESS_DELAYED ;

uint32_t stateTimer = millis() ;
bool stateChangeNew = true ;   // indicating a new entry to state


void setup() {
  Serial.begin(115200);
  pinMode( button, INPUT_PULLUP) ;
  pinMode( mixerPin, OUTPUT) ;
}

void loop() {

  switch ( state ) {

    case States::WAIT_BUTTON_PRESS_DELAYED : {
        enum class StatesIntern { INIT, WAIT_BUTTON_PRESS,  WAIT_BUFFER_TIME } ;
        static StatesIntern stateIntern ;
        static uint32_t stateTimerIntern = 0 ;

        if (stateChangeNew) {
          stateChangeNew = false ;  // reset 
          Serial.println("we are new in state WAIT_BUTTON_PRESS_DELAYED so initialise") ;
          stateIntern = StatesIntern::WAIT_BUTTON_PRESS ;
          stateTimerIntern = millis() ;
        }

        switch ( stateIntern ) {
          
          case StatesIntern::WAIT_BUTTON_PRESS :
            if ( !digitalRead( button ) ) {
              Serial.println("button press detected. Pausing.") ;
              stateIntern = StatesIntern::WAIT_BUFFER_TIME ;
              stateTimerIntern = millis() ;
            }
            break ;

          case StatesIntern::WAIT_BUFFER_TIME :
            if ( millis() - stateTimerIntern > 1000 ) {

              state = States::IN_MIX ;
              stateTimer = millis() ;
              stateChangeNew = true ;
            }
            break ;
        }

        break ;
      }



    case  States::IN_MIX :
      if (stateChangeNew) {
        stateChangeNew = false ;  // reset
        Serial.println("we are new in state IN_MIX so initialise") ;
        digitalWrite( mixerPin, HIGH ) ;
      }

      if ( millis() - stateTimer > 5000 ) {
        Serial.println("terminating and back to start") ;
        state = States::WAIT_BUTTON_PRESS_DELAYED ;
        stateTimer = millis() ;
        stateChangeNew = true ;
        digitalWrite( mixerPin, LOW ) ;
      }
      break ;

  }
}

The pattern has been extended so that a state in a state machine can itself contain an entire state machines, nested like a Russian doll.
I avoided including functions or adding classes to keep the example simple, or at least at a single level. However, it is clear that on a larger implementation, some parts could be made less verbose by adding a function. For example, a change of state involves setting a state timer and also a variable to indicate a new state and a function call removes the repetition. A class could also be used to wrap the state variables together with the function(s) for maintaining them.

One (other) advantage of this model is that it is much easier to add debug messages when in the state itself using the initialisation routine.

Maybe someone finds it interesting or useful.

2 Likes

Is there a reason why you declared the states as a class and used the scope resolution operator in your case statements rather than just the state names ?

I generally do it like that because it is less clutter in the global name space and, in particular with state machines where you may have 2 or more running in parallel with states having the same name such as "START", "WAIT" etc. it is tidier.
It is a bit more typing but I think cleaner.

1 Like

Thanks for sharing.

I understand that sometimes it's useful to have another state machine that could be imbricated into the state machine but in this second example its feels like more clutter than needed.

If your system is the "button + led" and the behavior is that there must be a waiting phase after the button is pressed then that state does belong to your system and the first design seems appropriate.

May be a better example would be a vending machine with a top-level FSM whose states are Idle when no money is inserted, HasCredit when sufficient credit is available, Dispensing when a product is being delivered, and OutOfService when the machine is unavailable. The Dispensing state is not atomic and requires a sub-FSM to manage item selection, stock verification, product release, and change return before control goes back to Idle or HasCredit.

(still could be argued it's just one machine)

The TCP protocol can be modeled with a top-level FSM whose states include CLOSED when no connection exists, LISTEN or SYN_SENT during connection establishment, ESTABLISHED when the connection is active, and termination states such as FIN_WAIT and TIME_WAIT. The ESTABLISHED state requires a sub-FSM to manage data transmission, acknowledgments, retransmissions, and flow control without leaving the established connection state.

Anyway - your code highlights the idea and possibility - so leads to some ideas.

1 Like

Thanks for looking at it.
I agree that the rather simple example I chose may not have been the best to illustrate the concept of a state machine within a state. It may be more appropriate where there a number of "high level" states each composed of a number of "lower level" states a in your examples.
Also, if the sub states of one state are cooperating with the sub states of another state then care has to be taken that these sub states are visible to each other.

1 Like

Yes - all good food for thoughts !

thanks for sharing.