Finite State Machine on an Arduino

Today, we will implement a finite-state machine (FSM) on an Arduino. This allows you to set up systems with a precisely defined behavior based on distinct states. You will learn what a finite-state machine is and what it’s good for.
In a nutshell, we will graphically model a light switch, generate code from that model, implement some glue code, and run it on an Arduino. Hence, this post is less about the project itself but about the development methodology behind it. You will see how easy it is to model your system as a state machine and run it on your Arduino. And, of course, all software tools we will use are for free - we will use the state machine modeling tool YAKINDU Statechart Tools, which you can download at https://www.itemis.com/en/yakindu/state-machine/. You can try it out for 30 days, and for hobbyists and academic use it's free. If you need further help with the tool, read the documentation, check out some examples or hit the user groups.

Supplies

• YAKINDU Statechart Tools
• Arduino Uno
• 1x LED
• 1x Resistor 220R
• 1x Resistor 1kR

Step 1: What Is a Finite-State Machine?

A finite-state machine, or FSM for short, is a machine (in an abstract way) that has a defined and finite number of possible states of which only one is active at a time. The states are connected via transitions. These transitions have a certain direction and can only be passed in that direction – think of it like a one-way street. Furthermore, a transition has certain inputs and outputs. You can think of these like a condition you have to fulfill before you can use the one-way street, and when you do use it, a signal is given to the outside world – for example, you have to pay a fee before you can use the street and then your car gets counted.
A very basic example of a FSM is found in many houses: pushing a button activates the light in the stairwell. After a certain time, the light switches off automatically. You could model this as a FSM with two states: Light On, and Light Off. There is a transition from one state to another and vice versa, and the condition is to press the button in one direction and that a certain time has passed in the other direction. We can model this behaviour in a diagram, the so-called statechart. Take a look at Picture 1.

The filled black circle marks the entry point of the state machine (everything has to start somewhere). So, if our machine starts running, the light is off. It stays like that, until we use a light switch – the light goes on then, and goes off after 30 seconds. Pushing the button when the light is already on does nothing, and after 30 seconds, the light goes off. This FSM does not have any outputs. From a traditional mathematical perspective, the state Light On is equivalent with the light being switched on, but when we really start to program our system, of course we'll need to add some kind of output that actually does something – like switching on the light.

This state machine works, but is it a good system? Is 30 seconds long enough? For most people, probably yeah, but the people on the 10th floor might not like our system. They might need longer than 30 seconds, let's say they need 40 seconds. But they need to wait for the 30 seconds to pass and the light to switch off to activate the light again, and they could be in the middle of a stair then. So, what we need to do is to allow the timer to be reset when the light is on and the button is pressed again. For that, we will need to re-model our system, modeling the start of the timer as an output of our transitions and adding another transition, as can be seen in Picture 2.

Here, you can see two things:

• It is perfectly okay for a transition to go to the state it came from
• A transition can have an event as a condition for that transition to happen as well as assigned outputs. The information left to the slash is the event, the information on the right is the output. Events are also considered inputs to the machine, and this is called an Input-Output-Automaton.

Step 2: Manually Implementing the FSM on an Arduino

When we want to implement this behavior on the Arduino, the code might look something like in this gist. The code is nothing too special, the switch-case statement simply contains one case for each possible state and checks inside there if the transition conditions are fulfilled. If so, the state is changed.

As you can see, the code is quite simple. But can you imagine what happens when you don't have 2, but 10 or 100 states? This is not uncommon for a real-world FSM. The code gets unreadable and can reach lengths of multiple thousand lines. Also, normally, we want to plan the FSM in a graphical manner, because we need to be able to see what it actually does as fast as possible. Then, we still need to code the actual state machine, and we need to be sure that our graphical design and our handwritten code actually do the same thing. This can be a huge issue.
Think about it: for every state our FSM has, our code needs one „case“ statement, and for every transition to other states, we need one if or a case statement inside there. If we would have a state machine where every state can reach every other state (the most extreme case), our code would grow with n squared, where n is the number of states. So, we would have 3 cases for 3 states, with 3 ifs inside, so the code length would be proportional to 9. When we have 10 states, which is not a lot more, the code length would be proportional to 100, and with 20 states, the code is already four times longer. A graphical representation of that FSM would be easier to grasp, and it would be nice if we would not have to handle all those switch case statements. If you are familiar with netlists that describe schematics for simulators – we would not want to design schematics with netlists, either. So, what do we do instead? See in the next step!

Step 3: Get the YAKINDU Statechart Tools

Yakindu SCT is a tool made for exactly that: Modeling your system and generating code from it. The modeling tools are far more advanced than simple finite-state machines, because they are based on the statechart theory by Harel. They extend the normal automaton theory by some further concepts – for example, a history state, where leaving a statechart saves the active state, so you can come back later, and much more. We won’t need these extra functions for this ‘Ible though.
Yakindu SCT is based on Eclipse, one of the most often used IDEs. So, we can use all the Eclipse plugins on the market and have an already known environment. And it is open source which means it is for free! At first, go to statecharts.org and select „Download SCT“. You will need to put in your name, your email and your profession. After you downloaded the tool, just unzip it (right click -> Extract All, or similar). Inside, you will find „SCT“. Start it. (No, a real installation is not needed.)

After you installed Yakindu SCT, you have the tools to model a FSM, but we will want to get the code to work on an Arduino. There is an excellent plugin for Eclipse to do that, you can find more about it on http://www.baeyens.it/eclipse/. It gives you the full Arduino toolchain inside of Eclipse, so you have the ease of use of the Arduino IDE as well as the intelligent code management and coding assistants of Eclipse. In SCT, go to Help -> Install new Software. The install wizard opens. Click on the Add... button near the upper right corner of the wizard. A dialog opens, asking you to specify the update repository you want to install the new software from. Enter some text into the Name field. This text is abitrary in principle, but you should choose something that makes it easier for you to identify this particular update repository among other update repositories. After entering name and location (http://eclipse.baeyens.it/update/V4/stable) of the update repository, click OK. Eclipse establishes a network connection to the update repository, asks it for available software items and shows them in the install wizard. Here, you simply accept the choice „Arduino“. Clicking Next a few more times and accepting the license agreements later, it will ask you to restart the tool. After you have done that, the plugin downloads all the needed libraries, so you don't have to copy them from an existing Arduino project. And here you go, having the Arduino tools installed in your Yakindu SCT installation. Now it is time to combine the possibilities of both.

Note: If you are on Windows and haven’t already, install the official Arduino IDE as well. It comes with the required drivers. I’m not sure about the situation on Mac. Linux already contains the drivers, so an installation of the Arduino IDE is not neccessary.

Step 4: Start Creating a Statechart

We will now start to model the statechart together. At first, we will create a new project. You should be on the welcome page of SCT / Eclipse. Go to File -> New -> Project... and choose Arduino -> New Arduino Sketch in the main menu. The normal wizard for new Eclipse projects will appear. You have to give your project a name. Let’s name it ArduinoFSM. In the next window, you can specify the port your arduino is connected to. If you don't know it and don't know how to find out, ignore this. You can now click Finish.
If you instead selected New -> Arduino Sketch, you will not be asked where your arduino is connected. Use Project -> Properties to do that later then. If you don't know how to figure out your Arduino's port, the last step of this instructable will help you out.

In case the welcome screen does not close after you created the project, just close it on your own, using the X in the tab. You should now have something similar to the first picture in the Project Explorer on the left.

We will now want to create a new folder called „model“. Right click your project and select New -> Folder. Type in the name and click Finish.
Right click that new folder, go to New again. Depending on your installation, you might be able to directly add a new Statechart Model, or maybe you have to use Other, select Yakindu, and choose Statechart Model. What you have now should look like the second picture: One entry state and one generic first state named StateA.

The text box on the left allows you to declare events and variables related to the statechart, while the area on the right is the graphical statechart editor.
We will need one event: the pushbutton. Double-click the textbox on the left, and under interface, insert the text

in event button

With that, you declare that there is an incoming event named „button“. Also, double click the word „default“ in that text box, and give the statechart a better name – how about „LightCtrl“? Now, add another state: just click on State in the palette on the right, and then somewhere in the graphical statechart editor. Double click on both states' names, and name the one with the black entry state attached to it Light Off, and the new state Light On. Now, we need the transitions: Select Transition from the palette, click on one state, hold, and drag to the other one. This should form the transition. It goes from the state you clicked first to the second state. Add the second transition by clicking the state you dragged to first now and drag to the other one, so that you have transitions in both directions. Now, click on a transition. A text field will appear. Here, you can input the events and outputs that you want to give that transition. On the transition from Light Off to Light On, type button, on the other one, type after 5s (that's faster than 30 seconds for testing). You should now have something that looks like the third picture!

That's it for now. You have a working model of a staircase light!

Step 5: Simulate the Statechart

Another nice feature of Yakindu SCT is that you can simulate the statechart without writing any code beforehand. You can try if your state machine does exactly what you wanted it to do.

Simulating a statechart is extremely easy. Right click the .sct-file in Eclipse / SCT, select Run As and then Statechart Simulation.
A new perspective opens. You should be able to see that the first state is red, this is the active state. (Take a look at the picture) On the right, there should be the Simulation View open. You can simulate the button push event by clicking the word button in the simulation view on the bottom right. The active state should change from Light Off to Light On. After five seconds, or after you click on the time event Light_On_timer_event_0, the active state changes back to Light Off. Fantastic! Now let's check how to get this to work on an Arduino.

Step 6: Bring Your System to the Real World

Okay, we clicked around, used a graphical editor (normally associated with low-level-languages), let's get that thing to life. First, we need a code generator that transforms our statechart into C Code. That's surprisingly simple, though it might look like black magic at first.

Right click your model-folder and select New -> Code Generator Model. Click yourself through the wizard, and attach the code generator to the statechart you made before. Attention: In that same window, there is a selector in the top that is easily overseen. Use it to select the C Code generator instead of the Java one, and click finish after you have checked the checkbox next to your statechart. Normally, the generator should now work directly and automatically all the time. Check if two folders were created, src and src-gen. If that is not the case, go to Project in the main menu and check if Build automatically is activated. Do so if it isn't, and right click your project and select Build Project. A progress bar should appear as well as both the mentioned folders. When you made any changes, you can also right-click the generator file and select Generate Code Artifacts.

The content of the folder src-gen is quite interesting. The file LightCtrl.c contains the implementation of the statechart. When you inspect it, you will find a function LightCtrlIface_raise_button(LightCtrl* handle). You can call this function to raise the button-event we declared earlier – for example, when you check your hardware button's pin and see it has a HIGH-level. Then there is the file LightCtrlRequired.h, at which you need to take a look. It declares functions you need to implement. For this statechart, there's only two functions: lightCtrl_setTimer and lightCtrl_unsetTimer. We need these functions because our statechart uses the construct after 5s. This is a pretty convenient function, but our statechart code generator does not deliver a timing service, because that is highly platform dependent – your computer can handle timers differently than the tiny Arduino, and timer handling on Mac & Linux works differently than on Windows.

Luckily, I will give you a timing service, so you don't need to implement your own. In your project, create a new folder, let's call it scutils for statechart utilities. You can name it whatever you want or choose not to create that folder, it's just a matter of organization. We will create two files in there, sc_timer_service.c and sc_timer_service.h. Copy the

code from GitHub inside there:

sc_timer_service.h

sc_timer_service.c

With YAKINDU SCT 2.7.0, there is a new option to obtain the project for this instructable:

In SCT, go to File -> New -> Example..., select "YAKINDU Statechart Examples", and click next. In the new Example Wizard, click "Download" to obtain the newest set of examples as indicated. Select "Basic Finite State Machine For Arduino" from the arduino category, and click Finish. The project will be copied into your workspace. Right-click it and hit 'Refresh' - just to be sure.

Now, we can start to work on the Arduino code in the *.ino-file the wizard generated.

Additionally to the Arduino.h, also include avr/sleep.h, and of course our state machine and the timer service: LightCtrl.h, LightCtrlRequired.h and sc_timer_service.h. Now, the regular Arduino stuff is needed: we define the pins for the button and the LED, and set these up inside of the setup-function (that's what it was made for). Then, we need to define the functions the statechart expects us to define - lightCtrl_setTimer and lightCtrl_unsetTimer, as explained earlier. Here, we just use the timer service, and we are done. Now, we should spare a thought on how we actually want to activate the LED when we reach the state Light On. Basically, we have three options:

1. We can check if the statemachine is in the state Light On, and activate / deactivate the LED based on that information
2. We can go to our statechart and set a variable when we reach the states, that we can poll
3. We could add an operation that manages the light that is called by the statechart on a transition.

The first solution is really bad. We would have logic concerning the statechart outside of it. If we would rename our states, it would cease to work correctly; but those names are meant to be prosaic and not logic related. Using variables is okay, especially when working with desktop applications. We could sync with them every x milliseconds or so. Here, we want to use an operation. Add the following to the statechart’s interface declaration:

operation setLight(LightOn: boolean): void<br>

This declares a function that accepts a boolean value as argument and returns nothing (void). This should not be new for you, only the syntax here is different. Remember – statecharts are not bound to a specific language, so the syntax is generic. This function appears in LightCtrlRequired.h automatically. If it does not, save your statechart, right click on your project and build it.

The function declared here looks like this:

extern void lightCtrlIface_setLight(const LightCtrl* handle, const sc_boolean lightOn); 

The input parameter handle is of the type LightCtrl, it is the referrer to the statechart. If you are not that experienced in C: the star denotes a so-called pointer, so the variable contains the address of the statechart variable. This helps us because we can operate on the original object and don't have to create a copy of it. So, let's implement this function:

void lightCtrlIface_setLight(const LightCtrl* handle, const sc_boolean lightOn) {<br>    if(lightOn)
        digitalWrite(LED_PIN, HIGH);
    else
        digitalWrite(LED_PIN, LOW);
}

As you can see, this function is bloody simple – we don't even use the handle to the statechart, we only write a HIGH on the LED pin if the operation's argument is true, and LOW otherwise.

We change the statechart itself so that it looks like in the first picture.

Remember step 1? Left to the slash is the needed input for the transition, right is the output of the state machine if this transition is taken. The output here is to call the specified operation with these arguments.

#include "Arduino.h"<br>#include "avr/sleep.h"
#include "src-gen/LightCtrl.h"
#include "src-gen/LightCtrlRequired.h"
#include "scutil/sc_timer_service.h"<br>
#define BUTTON_PIN 3
#define LED_PIN 6
#define MAX_TIMERS 20 //number of timers our timer service can use
#define CYCLE_PERIOD 10 //number of milliseconds that pass between each statechart cycle<br>
static unsigned long cycle_count = 0L; //number of passed cycles
static unsigned long last_cycle_time = 0L; //timestamp of last cycle
static LightCtrl lightctrl;
static sc_timer_service_t timer_service;
static sc_timer_t timers[MAX_TIMERS];<br>
//! callback implementation for the setting up time events
void lightCtrl_setTimer(LightCtrl* handle, const sc_eventid evid, const sc_integer time_ms, const sc_boolean periodic){
    sc_timer_start(&timer_service, (void*) handle, evid, time_ms, periodic);
}<br>
//! callback implementation for canceling time events.
void lightCtrl_unsetTimer(LightCtrl* handle, const sc_eventid evid) {
    sc_timer_cancel(&timer_service, evid);
}<br>
void lightCtrlIface_setLight(const LightCtrl* handle, const sc_boolean lightOn) {
    if(lightOn)
        digitalWrite(LED_PIN, HIGH);
    else
        digitalWrite(LED_PIN, LOW);
}<br>
//The setup function is called once at startup of the sketch
void setup()
{
    pinMode(BUTTON_PIN, INPUT);
    pinMode(LED_PIN, OUTPUT);<br>
    sc_timer_service_init(
            &timer_service,
            timers,
            MAX_TIMERS,
            (sc_raise_time_event_fp) &lightCtrl_raiseTimeEvent
            );<br>
    lightCtrl_init(&lightctrl); //initialize statechart
    lightCtrl_enter(&lightctrl); //enter the statechart
}<br>
// The loop function is called in an endless loop
void loop()
{
    unsigned long current_millies = millis();<br>
    if(digitalRead(BUTTON_PIN))
        lightCtrlIface_raise_button(&lightctrl);<br>
    if ( cycle_count == 0L || (current_millies >= last_cycle_time + CYCLE_PERIOD) ) {
            sc_timer_service_proceed(&timer_service, current_millies - last_cycle_time);
            lightCtrl_runCycle(&lightctrl);
            last_cycle_time = current_millies;
            cycle_count++;
        }<br><p>}<br></p>

Also, check out the code in this gist with line numbers.

• Lines 1-6 contain includes as discussed earlier.
• Lines 8 and 9 define hardware pins we will want to use for our arduino.
• Lines 11 and 12 define how many timers our statechart can use, and how many milliseconds should pass between each computing cycle of the statechart.
• Lines 15 and 16 declare variables that we can use to count the cycles and to manage the time of the last cycle.
• Lines 17, 19 and 21 declare important variables for the usage of the statechart: The statechart itself, the timer service, and an array of timers.
• Lines 24 and 33 define functions that the statechart needs for the timer, and line 33 is the function to set the LED we discussed earlier.
• In line 41, void setup() is a standard function of the Arduino. It's called once at startup. We use it to initialize stuff – our LED and button pins get their direction configured (INPUT is standard, we do that for clarity), the timer service is initialized, the statechart is initialized and entered. Entering means to start the state machine, so the first state is activated – this is the state the entry state points at. So, at startup, the light is off.
• In line 59, the loop function follows, which is called all the time by the Arduino.
• In line 61, we capture the current time with the millis() function, which is defined by the Arduino library.
• In line 63, we check if our button is pressed, and raise the button-event if it is.
• In line 66, we check if more than CYCLE_PERIOD milliseconds passed since we last cycled our statechart.
• This takes some load from our arduino and means we can reliably use up to 10 milliseconds for our own functions.
• In line 68, we tell the timer service how much time has passed since the last invocation, tell the statechart to run one cycle in line 70, save the current time in line 72, and increment the cycle count in line 73.

Using the arduino plugin, you can now connect the arduino with the LED and the button attached to your computer, and use the button in the top toolbar to upload the program to your arduino.

The circuit is shown in pictures two and three.

The LED is connected to a digital pin (6) with a resistor of roundabout 200 Ohms. The cathode is attached to GND.

Pushbuttons have four pins, please check which of these are always connected and which are connected when you push the button. Then, you attach the digital pin (3 is used here) to one side, and a pulldown resistor to GND. This stops the pin from „floating“, an undefined state, and keeps it on 0 Volts. When the button is pressed and the other side is attached to VCC, that side is „stronger“ because it has no resistor and the voltage goes up to 5 Volts – basically a voltage divider where one resistor is 0 Ohms. Please use a fairly high resistor here, because it limits the current going through the button. 1 kR is the minimum.

As you can see, this program’s logic is completely independent of the actual size of our statechart. It does not matter if our statechart has 2 or 20 states – of course, if we want to do something, we need to implement a function here and there. But the main code inside of void loop() always stays pretty small and allows for a modular program architecture. We only have to take care of the interfaces from the statechart to our Arduino's hardware inside of our code, the auto-generated statechart handles its internal logic. Remember how we discussed to reset the timer when the button is pressed again? You could now add a transition from the Light On state to itself with „button“ as guard event, and you would not need to change or add a single line in your code. Try it out, and start modeling your software instead of writing it!

Step 7: Additionally: Find Out Your Arduino's Port

So, you got stuck because you can't figure out which serial / USB-port your Arduino is connected to. Alright, you'll find instructions below for Windows and Linux.

Windows

Plug the arduino in your computer, go to "Devices and Printers" (from the start menu or the system control panel). Your arduino should show up there, as you can see in the image - for me, the port would be COM12. This can change, for example when you use another USB port, reboot your system... If something does not work, check if this is still correct.

Linux

With your arduino not connected, start a terminal. Type dmesg and return, this should give you lengthy text output. Plug in your arduino, and type dmesg again. The end should be some messages concerning the arduino, including a port - for example, /dev/USB0, /dev/ttyAMC3 - you get the hang of it. If you plug in your arduino and the LED doesn't come on and dmesg shows the exact same thing before and after you plugged it in, chances are your Arduino is toast.

If this method doesn't suit you fancy, you can also try ls /dev/ before and after you plug in the Arduino. This lists all available devices and you should be able to see that one is new after you attached the Arduino.