History

Current version 1.2

Changes:

  • 1.2Reverted Timeout and Statetime back to millis() for compability reasons
  • 1.2Added guard to prevent duoble calls when using Finish()
  • 1.2Added a State Nop() function for convenience
  • 1,1Added macros for edge detection

A novel and relaxed view on finite state machines


State machines lend themselves to the solution of many computational problems. Especially of industrial and/or real time nature. Part of what makes them attractive is that once the problem is described in terms of states and transitions the solution is almost trivial. The traditional approach to state machines Statemachines are normally defined by a number of interrelated sets:

  • A finite set of states
  • A set of conditional transitions between the states
  • A set of input conditions
  • A set of output signals generated by either:
    • The current state, a Moore automaton
    • Any transition, a Mealey automaton

Description methods

There are two general description methods for state machines

  • Tables describing the combination of current states and conditions leading to the nest state.
  • Graphical diagrams showing states as circles or squares and arrows between them describing the transitions.

Implementation

The implementation of statemachines differs whether they are made in hardware or software

Hardware

The normal hardware implementation consists of a set of registers in which the current states are coded using different coding methods and some combinational logic generating the transitions and output signals from the current state and inputs. This can be done by discrete or programmable logic

Software

Software implementation are based on either the table approach with logic or jump tables or use switch statements. Neither of which are easy to interpret.

The new approach

The complexity led me to a new and somewhat more relaxed idea:

  • Each state is represented by a single void function taking no parameters and meeting certain demands.

This function will be called repeatedly, most often from inside Arduinos loop function but other options are possible. This leads to a number of interesting features. More of this later. Demands on state functions In order for the statemachine to function efficiently the functions representing the states must fulfil a number of prerequisites:

  • The function must handle those input signals that affect the statechanges and output signals by itself
  • The function must generate the appropriate output signals
  • The function must initiate statechange through a well defined mechanism
  • The function must not introduce any unnecessary delays, that is loops and similar things should be avoided. Often there is no need for them anyway because of the repeated calling of the function. This is especially true when working with concurrent states.

Implementation using function pointers

The idea of having one function for each state leads to the concept of representing the statemachine by one function pointer. Changing the state then becomes assigning this function pointer to a new state function. In order to provide a well defined mechanism for state changes, two typedefs are introduced (these must be in separate .h file):

typedef void State;
typedef State (*Pstate)();

Statefunctions are declared of type State with no parameters. The function pointer representing the statemachine is of type Pstate. Example 1 is a simple statemachine toggling a led using this principle.

The SM library

The SM library can be found HERE:Attach:SM.zip

Finding myself using the concept of function pointer based statemachines over and over I decided that it was time to write a library to facilitate them. This gave also the opportunity for some useful enhancements.

Basic concepts

The SM library offers the concept of a function pointer based statemachine encapsulated in a C++ class with some added bells and whistles. These are:

  • The ability to use head and body states
  • Timing functions
  • The ability to stop/finish and restart statemachines. This also opens the possibility for concurrent and/or hierarchical statemachines.

Simple state machine

This is the as using the raw function pointers but encapsulated and more user friendly. Example 2 has the same function as example1 but using the SM library instead.

Machine with head and body states

I often found the need to do a specific set of tasks the first time a state is entered (or re-entered). Those task could be sending something over the serial port, increasing or resetting a counter, resetting a timer and so on. In order to facilitate this I created a mechanism where a state change involved to new states:

  • A head state called only the first time after a statechange. All the tasks described above go here except for timers, there a separate mechanism for that.
  • A body state which does the bulk work. Checking inputs, initiating state changes etc.

Example 3 is a simple machine with a head state that sends a serial message and a body state that waits for a specified amount of time before re-entering.

Creating statemachines

Creating a statemachine consists of two parts

  • Writing the state functions
  • Declaring an SM object with initial states

The SM constructor is overloaded. The options are

SM Machine(State Initial_state);//simple machine
SM Machine(State Initial_head, State Initial_body);//machine with head and body states

Running statemachines

The SM class is actually a statemachine with function pointers in itself. That’s how the head state and timer mechanisms are implemented. The syntax for calling a member function through a function pointer is a bit awkward so there is a macro to tidy it up a bit:

EXEC(Machine)

It is possible to have several statemachines running at once. In order to do that each machine must be called with a EXEC macro repeatedly. Remember, loops inside state functions should be avoided.

Changing states

Changing states is accomplished by calling the statemachines Set() function. Just like the constructor this function is overloaded:

Machine.Set(State Next_state)//simple machine
Machine.Set(State Next_head, State Next_body)//machine with head and body states

The new state function will be invoked by the next execution of EXEC(Machine). The Set() function will normally called from within the current state function but this is not mandatory. It is fully possible to call a statemachines Set() function from elsewhere in the program, even from within another statemachine.

Timing functions

Statemachines are very closely related to timing, at least in the field of industrial automation. Therefore I have included two timing functions:

unsigned long Statetime();//returns the number of ms since the state was enterered or re-entered
boolean Timeout(unsigned long Time);//returns true if specified time is exceeded

Their use should be clear from the examples

Finishing and restarting

A machine can be stopped/suspended by calling its Finish() function. All EXEC calls return immedediately and the Finished flag is set.

A machine can be restarted with a call to Restart(). This will reä-enter the last executed state. Or on can use the Set() functions to restart the machine with a specified state

Utilities

Two macros for edge detection are now inculded, both must have a int varialble as the second parameter. This is for storing the signal state between calls

RE(signal, int state)//true if signal was 0 last call and is 1 this call
FE(signal, int state)//true if signal was 1 last call and is 0 this call

Examples

Example 1

Simple statemachine using function pointers toggling a LED on PIN13

#include "example1.h"//tydefs for State and Pstate

Pstate Exec;

#define toggle 9//input pin to toggle LED
#define led 13

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

void loop(){
  Exec();
}

State S1(){
  digitalWrite(led, HIGH);//LED on
  if(digitalRead(toggle)) Exec = S2;//wait for toggle pin to go high and change to S2
}

State S2(){
  if(!digitalRead(toggle)) Exec = S3;//wait for toggle pin to go low and change to S3
}

State S3(){
  digitalWrite(led, LOW);//LED off
  if(digitalRead(toggle)) Exec = S4;//wait for toggle pin to go high and change to S4
}

State S4(){
  if(!digitalRead(toggle)) Exec = S1;//wait for toggle pin to go low and change to S1
}

Example 2

Simple statemachine using the SM library, same function as example 1

#include <SM.h>


SM Simple(S1);//create simple statemachine

#define toggle 9//pin to toggle led on and off
#define led 13

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

void loop(){
  EXEC(Simple);//run statemachine
}

State S1(){
  digitalWrite(led, HIGH);//turn led on
  if(digitalRead(toggle)) Simple.Set(S2);//wait for toggle pin to go high and change state to S2
}

State S2(){
  if(!digitalRead(toggle)) Simple.Set(S3);//wait for toggle pin to go low and change state to S3
}

State S3(){
  digitalWrite(led, LOW);//turn led off
  if(digitalRead(toggle)) Simple.Set(S4);//wait for toggle pin to go high and change state to S4
}

State S4(){
  if(!digitalRead(toggle)) Simple.Set(S1);//wait for toggle pin to go low and change state to S1
}

Example 3

Machine with head and body states

#include <SM.h>

SM M(S1H, S1B);//create statemchine with initial head and body state functions

void setup(){
  Serial.begin(115200);
 }//setup()

void loop(){
  EXEC(M);//run statemachine
}//loop()

State S1H(){//state head function, run only once at each entry
  Serial.println("S1 head");//print message on each re-entry
}

State S1B(){//state body function run constantly
  if(M.Timeout(500)) M.Set(S1H, S1B);//re-enter state after 0,5s
}//

Example 4

Concurrent states

#include <SM.h>


SM m1(m1s1h, m1s1b);//machine1
SM m2(m2s1h, m2s1b);//machine2
SM m3(m3s1h, m3s1b);//machine3
SM Blink(On);//machine to blink led continously

static int m2c = 0;//counter for machine2

int ledPin = 13;// LED connected to digital pin 13

void setup(){
  Serial.begin(115200);
  pinMode(ledPin, OUTPUT);      // sets the digital pin as output
}//Setup()

void loop(){
  EXEC(m1);//run machine1
  EXEC(Blink);//blink led concurrently for ever
}//loop()

State m1s1h(){
  Serial.println("Machine1:State1");
}//m1s1h()

State m1s1b(){
  if(m1.Timeout(300)){
    m1.Set(m1s2h, m1s2b);
    Serial.println("chaging to 2");
  };
}//m1s1b()

State m1s2h(){
  Serial.println("Machine1:State2:Splitting execution");
}//m1s2h()

State m1s2b(){
  EXEC(m2);//run machine2
  EXEC(m3);//run machine3
  //machines 2 & 3 now run concurrently
  if(m2.Finished && m3.Finished){
    Serial.println("Split completed");
    m1.Finish();
  };
}//m1s2()

State m2s1h(){
    Serial.print("Machine2:State1:Count");
    Serial.println(m2c++);
}//m2s1h()

State m2s1b(){
  if(m2.Timeout(200)) m2.Set(m2s1h, m2s1b);
  if(m2c>10) m2.Finish();
}//m2s1b()

State m3s1h(){
  Serial.println("Machine3:state1");
}//m3s1h()

State m3s1b(){
  if(m3.Timeout(250)) m3.Set(m3s2h, m3s2b);
}//m3s1b()

State m3s2h(){
  Serial.println("Machine3:state2");
}//m2s2h()

State m3s2b(){
  if(m3.Timeout(250)) m3.Set(m3s3h, m3s3b);
}//m3s2b()

State m3s3h(){
  Serial.println("Machine3:state3");
}

State m3s3b(){
  if(m3.Timeout(250)) m3.Finish();
}//s3m1()

State On(){
  digitalWrite(ledPin, HIGH);// sets the LED on
  if(Blink.Timeout(400)) Blink.Set(Off);
}

State Off(){
  digitalWrite(ledPin, LOW);   // sets the LED on
  if(Blink.Timeout(400)) Blink.Set(On);
}

Share