State Machines 101

This thread http://forum.arduino.cc/index.php?topic=308044 prompted me to try to explain a bit about state machines, not that:

  • I know much about them
  • They haven’t been explained a gazillion times

Then I changed my mind, I’m going to take the liberty of having a tutorial here rather than posting some code I just wrote. Mods please move if you like.

So what I’m going to do is pose a question here and I’d like anyone who need to find out about state machines to try to code a solution.

Here’s my scenario. When the Arduino starts up, have a call to a calibration routine from inside setup(). The routine, and indeed any others you create, can just be a print line saying where the code has gone. Then when calibration has finished, have the program pause pending the press of a button. Use a while() for that: as long as a certain pin is high (use internal pullups), the code does nothing. Once that pin goes low (button to ground but do not forget the pullup) then let the flow resume and that of course will take you to loop().

I’m proposing two modes of operation for loop(); say “automatic” and “manual”. Have loop() start in manual edit… auto mode, so it runs and re-runs a function called doAuto or whatever. But have a push button which toggles between the two states, and obviously call a routine doManual when it’s in manual mode. Those functions need only say where they are with serial prints.

Have the following hardware:

  • 2 status LEDs. One to show the system is ready to leave setup(), ie calibration is done and awaiting the first button. The other is on for auto mode
  • 2 momentary buttons: one to release the flow from setup() to loop() and the other to toggle auto / manual mode.

I’d very much appreciate it if members who know about states don’t dive in with solutions; of course it’s a free world and you might well want to do that. Might be better though to answer specifics rather than give solutions.

The attached state diagram shows how this should work:

  • Start by running calibration automatically in setup()
  • When that’s done, move to ready state and wait the GO button
  • When GO is pressed, enter auto mode in loop, do stuff automatically, awaiting TOGGLE
  • If TOGGLE is pressed, move to manual mode, do stuff manaually, awaiting TOGGLE

I’ll be back in a day or two with some code; meantime I’ll monitor the thread and answer or defer any questions.

Those of you who need advice on state machines, I think it’s best that you ponder this first, then we’ll chat…

Hint: think variables to hold various states. You might not need one for each, since eg automatic and manual are mutually exclusive. So if you have a boolean variable called AutomaticMode, it’s true when in auto but false in manual

ps… if you don’t want to tackle it all at once, just do the calibration / ready part, or just the automatic / manual part. It’s not for marks… :slight_smile:

simple state machine.jpg

have the program pause pending the press of a button. Use a while() for that: as long as a certain pin is high (use internal pullups), the code does nothing.

My preferred approach would be to make the waiting for an input one of the several states the program could be in rather than having the program stall in a while loop. Using switch/case to execute the code for the current state makes the program much easier to read than a series of ifs in my experience. Using an enum to give the states names makes the program easier to read.

I look forward to seeing your program as from what you say about variables I think that my approach will vary from yours.

Anyone's welcome to take any approach they like, it's all about experimenting and thinking about states and what they mean in practice and how to get from one to another.

I have a working solution and if you have another UKHB, then that's awesome since it encourages that thinking.

States are discussed in so many places, and in so many diverse ways, with varying degrees of success, and I thought I'd take a new approach and try to get some thinking going.

My version is written and tested but I won't post it yet. Give me a shout when you want it posted.

I’m with UKHeliBob. No “while()”, big “switch/case”, using “enum”.

JimboZA, that means a single variable for the state. The single variable with the big “switch/case” will be the umbrella or backbone of the sketch. More variables can be added, as needed.

I also prefer to split the gathering of information and running the state machine into two seperate parts.

Example : http://forum.arduino.cc/index.php?topic=290915.msg2035290#msg2035290
If you look at that sketch, you see the “enum”, the part that gathers information from the inputs and the big “case/switch”. For every state a small piece of code is needed.

From looking at many Threads on the Forum this is an issue which some people find very hard to get their head around. A good tutorial is very welcome.

I wonder if the open style that @JimboZA has chosen will make it too difficult for him to control the content?

...R

Robin2:
I wonder if the open style that @JimboZA has chosen will make it too difficult for him to control the content?

But it's not my intent to do that, on the contrary in fact, although I'll perhaps try to summarise the content, that's about it.

Main thing is I hope that the people who need some help will ponder how to do this, before diving into code and worse, immediately asking for a solution.

(If it degenerates into a pissing contest, well then I can't do anything about that and if Robin2 that's what you meant by content, that will indeed be bad luck.)

All I ask is it's kept at the simple level, and any solution or suggestion posted is fully documented so that a) the concepts and b) the coding techniques are clear.

JimboZA:
Use a while() for that: as long as a certain pin is high (use internal pullups), the code does nothing.

UKHeliBob:
My preferred approach would be to make the waiting for an input one of the several states the program could be in rather than having the program stall in a while loop.

Speaking of (not) procedural programming, I suspect what would be most helpful to the broadest Arduino audience is to start with a procedural (blocking) solution and then incrementally transform it into a state machine. There are countless procedural examples and many state machine examples but, as far as I know, nothing to help the beginner transition from a procedural perspective to a state machine perspective.

Good idea CB...

So far there is no evidence of anyone who does NOT know how do program states showing any interest - which is what I meant by controlling the content.

Part of the problem may be an issue of timing - Joe Bloggs does not, today, know he will need to use a State Machine next week.

And I don't think it is practical (yet) to say to a newbie "State programming is all explained clearly on this Thread"

...R

I have implemented many State Machine solutions over the years, hard wired logic and now coded on Arduino.

I found this tiny State Machine library (SM) to be very useful for all my current projects.
http://playground.arduino.cc/Code/SMlib

SM timeout is very useful and easily handles switch debounce and other time without delay states.

And I don't think it is practical (yet) to say to a newbie "State programming is all explained clearly on this Thread"

I agree. There are threads on state machines and plenty of information on the Web but first you need to realise that a state machine would be appropriate to meet your requirements. By the time that someone asks for help and the answer is "use a state machine" they have usually invested a lot of time and effort in their program and are often not willing to start again.

Personally I have begun to consider a state machine as the first port of call for anything other than a trivial program. As soon as someone writes "when the button is pressed" I immediately think AHA, the state changes when the button is pressed so a state machine may be the way to handle it.

So, how do we make people consider using a state machine in the first place ? Can we think of a better phrase to stop it sounding so scary ? Seeing how many times code is posted without code tags and/or code is posted that using delay() inappropriately we know that users do not read the stickies at the top of the forum page so what can we do ?

By the way, I don't think that introducing a state machine library helps much as it can actually obscure what is going on and is yet another concept to get your head around. Maybe after the principle is understood it could be appropriate but to me a switch/case state machine implementation makes it more obvious how and why things work. Perhaps you would like to write a program to meet Jim's specification using the SM library and we can compare notes. Maybe I will be converted.

I have to confess my own code started with "state machines" managed by booleans & state bytes (obviously pretty limiting). I've been tinkering with migrating it to a proper implementation using Nilton's library.

IMHO, Jimbo's idea is sound. Show people how to migrate from something clunky thats specific to a situation, into using a framework thats easy to expand/debug and some of them will see the benefit.

It needs to be something tangible, since concepts get brushed aside in the rush to 'just get something working'. So start with a simple example showing two machines interacting and heavily comment the code.

Its like the whole blink without delay thing, you can talk about it until the cows come home, but the second you give someone a working code example that they can tinker with to understand, thats when you start seeing progress.

ps. dont take silence as lack of interest, this forum can be particularly off putting for newbies.

As i see it state machines are not about coding. They are all about planning/designing/organizing. If one starts by approaching (suitable) problems from a state machine point of view the solution will often be "amazingly simple". Once the solution is found resulting in a correct state diagram it is a no-brainer to convert the state diagram into code. This can be done with tables, switch statements, function pointers, state-classes, my state machine library or by any other means.
Once learned this process is very easy.
So starting with some procedural definition and converting that into a state machine seems very awkward to me.

Yup, i tend to view them as a logical flow. They force a more organised way to approach things.

As a relative newcomer to coding/arduino, some of the happy side effects are they make code easier to extend and easier to debug*

*: lets just ignore the swearing I've been doing recently merging them with u8glib :wink:

let me exemplify what i mean by taking morse code:

Each character (letter or numeral) is represented by a unique sequence of dots and dashes. The duration of a dash is three times the duration of a dot. Each dot or dash is followed by a short silence, equal to the dot duration. The letters of a word are separated by a space equal to three dots (one dash), and the words are separated by a space equal to seven dots. The dot duration is the basic unit of time measurement in code transmission.

This description will translate into this state diagram. Before converting this into a program there is an other issue to be considered: Not all characters do have a corresponding morse code. The state machine should handle this. My solution is just discarding those characters resulting in the second state diagram.

Once the state diagram is verified (and not a second before that) it can be converted into code. Using the SM lib one can write function stubs like this being positively confident that the final program will work since there is a 1:1 relation between states and state functions:

#include <SM.h>

SM Morse(Wait);
const int LEDPIN = 13;
void setup(){
  pinMode(LEDPIN, OUTPUT);
  Serial.begin(115200);
}//setup() 

void loop(){
  EXEC(Morse);
}//loop{}

State Wait(){}//Wait()

State startBit(){}//startBit()

State off5t(){}//off5t

State on1t(){}//on1t()

State on2t(){}//on2t()

State off1t(){}//off1t

State off2t(){}//off2t

Morse state diagram no filter.png

Morse state diagram.png

Understanding state machines seems very tricky in the abstract. Examples are extremely helpful to take someone down the road from "Huh?" to "Is that all there is to it?"

This sounds very helpful in that regard:

I expect I've mentioned this here before, but I once saw a short piece on building an OO piece of code. It only had three or four classes but it was just complex enough that the design wasn't immediately obvious. The instructional value was that the author showed his work warts and all, including the back-tracking and redesign that eventually culminated in a nice clean solution - the sort that is so often presented fait accompli.

Coding Badly's suggested approach sounds as though it would have similar positive value. As ever though, when we see so many posts that ignore everything in Nick's stickies, I wonder who would read such a necessarily long explanation.

Finally, since a state machine is so simple to construct with a switch statement, I don't think there's any value in adding a library into the mix for initial instruction. That can come once you know what a state machine is and how it works. The abstruse contortions of a library will be more likely to make sense then.

UKHeliBob:
So, how do we make people consider using a state machine in the first place ? Can we think of a better phrase to stop it sounding so scary

wildbill:
Understanding state machines seems very tricky in the abstract. Examples are extremely helpful to take someone down the road from "Huh?" to "Is that all there is to it?"

For me these are two very important points.

...R

wildbill:
Understanding state machines seems very tricky in the abstract. Examples are extremely helpful to take someone down the road from “Huh?” to “Is that all there is to it?”

This is for some reason very often the conception. And i think it is this conception the refrains people from taking that path. Of course if you read one description more complicated than another you will be lead to believe this (and yes, finite automata are a branch of abstract algebra but that is just academic bs).
The truth is that a state machine is no more complex than a board game with one figure and very explicit rules.

  • Place the figure on the starting state
  • If any condition for moving to another circle comes true you must make that move and forget about everything hat has happened before.

And that is all there is!

Finally, since a state machine is so simple to construct with a switch statement, I don’t think there’s any value in adding a library into the mix for initial instruction. That can come once you know what a state machine is and how it works. The abstruse contortions of a library will be more likely to make sense then.

What do you mean by “abstruse contortions”? Including a header file is one of the most common things to do. And i strongly believe that writing stub functions from a state diagram that clearly show the structure of the program and let you focus on one function a a time without worrying about anything else and knowing that your code will be fully functional and non blocking is hardly difficult.

Here is the complete code for the morse machine. Note that the longest function is just 10 lines with one level of indention which is quite typical. The important thing is that adding the code has not changed the original structure from the state diagram.

#include <SM.h>

const int LEDPIN = 13;
const byte MinASCII = 34;//lowest character code
const byte MaxASCII = 90;//highest character code
const byte RANGE = MaxASCII-MinASCII+1;
const byte lcode[RANGE] = {74, 0, 0, 0, 0, 122, 182, 0, 0, 0, 206, 134, 170, 0, 252, 244, 228, 196, 132, 4, 12, 28, 60, 124, 30, 0, 0, 0, 0, 50, 0, 160, 24, 88, 48, 64, 72, 112, 8, 32, 232, 176, 40, 224, 96, 240, 104, 184, 80, 16, 192, 144, 136, 208, 152, 216, 56};
const int tUnit = 300;//ms for 1 time unit, dot or space

SM Morse(Wait);
byte c;
byte s;
byte l;

void setup(){
  pinMode(LEDPIN, OUTPUT);
  Serial.begin(115200);
}//setup() 

void loop(){
  EXEC(Morse);
}//loop{}

State Wait(){
  if(Serial.available()){
    c = Serial.read();
    if(c==32) Morse.Set(off5t);
    else Morse.Set(startBit);
  }//if(Serial.avaliable()
}//Wait()

State startBit(){
  Morse.Set(Wait);
  c = toupper(c);//only uppercase letters
  if(c<MinASCII) return;//out of range
  if(c>MaxASCII) return;//out of range
  c -= MinASCII;//c is valid, create index
  s = lcode[c];//get code byte
  if(!s) return;//no symbols for this char
  for(l = 7; (s&1)==0; --l) s >>= 1;//find startbit
  Morse.Set(on1t);
  digitalWrite(LEDPIN, 1);//turn led on
}//startBit()

State off5t(){
  if(Morse.Timeout(5*tUnit)) Morse.Set(Wait);
}//off5t

State on1t(){
  if(Morse.Timeout(tUnit)){
    s >>= 1;//get symbol bit into bit 0, 0=dot, 1=dash
    if(s&1) Morse.Set(on2t);//symbol was dash, leave on for another 2 tUnits
    else{//symbol was dot, turn off
      digitalWrite(LEDPIN, 0);
      Morse.Set(off1t);
    }//else
  }//if(Timeout)  
}//on1t()

State on2t(){
  if(Morse.Timeout(2*tUnit)){
    digitalWrite(LEDPIN, 0);
    Morse.Set(off1t);
  }//if(Timeout)
}//on2t()

State off1t(){
  if(Morse.Timeout(tUnit)){
    if(--l){//more symbols
      Morse.Set(on1t);
      digitalWrite(LEDPIN, 1);
    }else Morse.Set(off2t);
  }//if(Timeout)
}//off1t

State off2t(){
  if(Morse.Timeout(2*tUnit)) Morse.Set(Wait);
}//off2t

I was thinking of the library that requires you to set up an array of pointers to functions for each state - possibly it's an array of struct. It's nice in that it has optional pointers for transition into state, manage when in state, transition out.

The trouble is, trying to figure out state machines at the same time as mastering the library is just a bridge too far for me, plus the previously mentioned issue that if you do use it, you're significantly restricting the pool of people who can help you with it.

I have nothing against state machine libraries, yours or anyone else's, but given how hard people find it to understand the basic concept I still believe that in this particular edge case, it's better to roll your own to start with than it is to use a library.