Transitions in state machines

Jan 11, 2012 No Comments by

I will write a little bit here about transitions in state machines just for myself but if you want to spend time reading it, go ahead. The reason for me to write about it here is that it is easier for me to write down something more suitable for others to read compared to the notes I take and don’t take if I’m the only one who are going to read them. Things I write here might also end up in my master thesis in the end, just so you know.

State machines are a really old concept and is used in computer science a lot. It is most widespread in the world of software modeling and robotics (I do believe, but can not base that statement on facts because I don’t care to google it right nao). The reason for me to suddenly have a interest in state machines, when I merely have used them in one course before, is that they turned up to be an important part of my thesis and therefore I must obtain some interest and knowledge about them. While  playing around with a newly developed language called ThingML I found that the way transitions were defined may not be the best and most effective way to write them. It sure wasn’t the most intuitive way to write them. This is one transition definition in ThingML:

transition -> NameOfNextState
event Port?Message
guard ( CONDITION )

Here we say that we are going to have a transition which will lead us from the current state to NameOfNextState. This will happen if we get a message through the port and that message meat the guard condition. Easy, right? Yes indeed.

So what is the problem then? you might ask. Well, the transition definition you can see above is supposed to be written inside a state, and each state that have a transition that can lead to another transition need one of these transition definitions. So given that we have three states as seen in the next diagram, here we have three transitions one from S1 to S2, one from S2 to S3 and one from S3 to S1.

In this scenario there is really no need to change anything, there is perfectly alright to write each of the three transition statements in their corresponding state. But if we infer that every state should be able to transact into any of the other states when a specific event occurs, then the diagram will look like this:

In this example we actually have to write all the transition definitions twice, this is because both S3 and S1 leads to S2 and therefore the same transition declaration have to be written both places. This results in us writing six transition definitions instead of three. That is double the amount. Now if we add one state and let the same rules apply we will end up writing twelve transition definitions instead of four. This starts to seem like a lot of work, right? Now imagine a sophisticated robot which have eight different states and that no mater which state it is in, it can jump to any of the other states directly. This means a lot of transition definitions and remember when you look at the picture you have to write one for each line…. That is 56 to be rather precise for once. And we can abstract the rule n*n-1 = number of transitions where n = number of states. and all states leads to all other states.

In all of the above examples there is a small detail that I have neglected and that is the fact that a state can also transact to itself. This will add n to the equation and the rule will look like this n+(n*n-1) = number of transitions. Which can be shortened into n*n = number of transitions.

My solution

So as you already might have understood I want to eliminate the redundancy that occurs when you write the same declarations several times, but to be able to do this I must create a new way of declaring transitions and take into account all the special cases that might occur. It is important to say that what I am about to propose as a great change to the ThingML language is only a great change in the cases where several states can lead to a number of other states and that most of the transitions leading to one state are triggered by the same message no mater which state the state machine are in at the current time. If this is not the case then the old way of writing transition declarations are still a good alternative. The first example I wish to offer is a visual one, you have seen a state machine with eight states where each state have a transitionto every other state. This is how I wish for four states to be symbolized. The arrows comes from an outlying event queue

My first suggestion on how to write the transition definitions looks like this:

transitions m : Light.value {
    (m.value < 40) -> State2
    (m.value >= 40) -> State3
}

This code block is to be placed outside the statechart, but inside the thing scope(these are ThingML components, to learn more about them go to thingml.org).  The transitions scope are intended to contain all transitions that are to trigger depending on a given message from a given port, in this example the value message from the Light port (Light.value). Then each transition are defined with one line, the first part of the line is the guard condition, this part is essential since without a guard the first transition would be triggered every time. The guard condition should also be a logical expression with the received message as one of the attributes. The last part of the line is the State that the transition are  leading to. In this part there is also an optional part which is the name of the transition, this one is only good to have if you are to make a model of your code, then the transition on the model will receive the name you have given it. The name are written between the guard condition and the arrow. like this:

 (m.value < 40) TransitionName -> State2

This way of writing transitions might at first glance seem like a good way of doing it, at least it did for me. But when you stop to think about it there are several things that isn’t covered and could cause problems. But I will try to solve them one by one from here on out. The first thing I need to do now is to create a real “functional” example that makes sense that we can use forward in this post. I found a example online using the popular robot Bender, that example was showing one implementation that are quite ok, but it is still a couple of things there that I don’t agree with. Anyhow, they display two State machine diagrams, the first one shows what Bender should be able to do, the other one is an optimization, but I believe that it takes away states and are not as good in showing of what bender should be able to do. You can see them here:

In the optimalizated version the stopped state seems to be missing, or it could be included in TurnedOn. But I feel that Bender should be awesome enough to go directly from one activity to another without going back to the turned on state first (ref figure one) and I think that Bender should be able to go from a activity to the turned off state without going through the turned on state first (ref figure two). Therefore to illustrate this I drew my own state machine diagram, it looks really complex and messy, but that is what we get from having the possibility to go from a state to almost any other state.

To bad there ain’t a bidirectional arrow…. Anyhow, When the Bender program is started he is in TurnedOff mode, consider this the initialization of Bender, After this he can move into turnedOn mode from here Bender can turn into every state in the diagram. In the activity states, Walking, running, raising arms, stopped and so on he can switch to any other state EXCEPT from TurnOn, this is because the obvious fact that Bender have to be turned on in order to perform any activities except from actually turning himself on. So what is Benders setup? I want to imagine that he have a knock sensor in his head and if this sensor register that he is hit in the head he is supposed to chant out a negative comment in a fashion that fits Bender. Also he have a distance sensor in his eyes that makes him run if he is more then 5 meters away from anything, he walks if he is closer then 5 meters and if he is about 10 centimeters away from any object he stops.  At this point you might shout out that I am stupid and that if he is chasing anything and gets closer he will first be running, then walking an then when he gets close enough he will be stopping. Therefore you might argue that he always have to walk before he stops. But I say that a meteor might fall in front of him while he runs forcing him to stop, therefore he must be able to come to a full stop while running. Bender also have functional ears and can hear chanting and will react to positive chanting like “Go Bender” and “You Rock”, if he hears those frases he will raise his hands and if he hears negative frases like “you suck” or “Fry is better then you” he will be depressed and lower his arms. Bender is a persistent robot and will not consider turning off unless he runs out of alcohol, which means that he will turn off until he receives a message about low alcohol levels.

The outline of the program will look like this:

import "legs.thingml"
import "arms.thingml"
import "head.thingml"
import "ears.thingml"
import "power.thingml"
import "alcohol.thingml"
import "../../thingml.thingml"

thing Bender includes LegsMsgs, ArmsMsgs, HeadMsgs, EarsMsgs, PowerMsgs, AlcoholMsgs{

    property booted : UInt16 = 0

    required port Ears{
        receives positive
        receives negative
    }
    required port Arms{
        sends rise
        sends lower
    }
    required port Legs{
        sends run
        sends walk
        sends stop
    }
    required port Head{
        receives knock
        receives distance
    }
    required port Power{
        recieves powerOn
        recieves powerOff
    }
    required port Alcohol{
        receives low
    }
    statechart BenderImpl init PowerOff{

        state PowerOff{
            on entry do
                Legs!stop()
                booted  = 0
            end
        }
        state PowerOn{
            on entry do
                //Code that boots system goes here
                booted = 1
            end
        }
        state Running{
            on entry do
                Legs!run()
            end
        }
        state Walking{
            on entry do
                Legs!walk()
            end
        }
        state Stopped{
            on entry do
                Legs!stop()
            end
        }
        state RaiseArms{
            on entry do
                Arms!rise()
            end
        }
        state LowerArms{
            on entry do
                Arms!lower()
            end
        }
        state Talking{
            on entry do
                Arms!rise()
            end
        }
    }
}

It is assumed that all ports are connected to a actual working part of a Bender robot on the other side of the interface. At this point the ThingML program is written so that it is functional with the current way of writing transitions and the way that i want to propose transitions to be written. As you can see there are seven messages that bender can receive and interact on, this means that we have to write seven transition statements in the thing scope. This is a great improvement compared to how it is done in the current version where you have to write seven transition statements in almost every state. The states are written so that they will trigger an action when the state are entered, there is no way to do some clean up and stop the walking procedure while bender is supposed to rise his arms for example since bender is capable of multitasking. Firstly lets compare one of the current style transition to my suggestion. The transition from any state to running would look like this:

transition -> Running
event m : Head?distance
guard booted == 1 and m.distance > 5000

My suggestion looks like this:

transitions m : Head?distance {
    (booted == 1 and m.distance > 5000) -> Running
}

At this point we can start to see the advantage of my proposed way of writing transitions, because we will also need to define transitions on the events of the distance being less then 5000 cm and less then 10 cm in order to decide on the correct behavior. In the current implementation this would mean two more transitions, two more event listeners and two more guards, resulting in six more lines of code, in every state, which sums up to 21 lines of code. So the benefits are great in writing it as this:

transitions m : Head?distance {
    (booted == 1 and m.distance > 5000) -> Running
    (booted == 1 and m.distance < 5000 and m.distance > 10) -> Walking
    (booted == 1 and m.distance > 10) -> Stopped
}

Problems

This way of writing the transitions gives us some problems though, in this example one of the problems is solved by the booted == 1 check. This does so that we can never go directly from the TurnedOff state to an activity state. Instead of using control variables like this there should be a construct in the transition declaration where the programmer can exclude states that will not allow these transitions to take place. One solution to this might be to add a comma separated list behind the transition that the are not to happen from a specific state, like this:

(m.distance > 5000) -> Running, PowerOff

This symbolize that the transition that goes to the Running state is not available from the PowerOff state. More states can be added with commas between. In this example neither of the three transitions are to be accessible from the PowerOff state and in the spirit that surrounds this article writing things several times is a abomination. Therefore I suggest that it shall be possible to write a comma separated list of states that will not trigger these transitions behind the closing curly brace, like this:

transitions m : Head?distance {
    (m.distance > 5000) -> Running
    (m.distance < 5000 and m.distance > 10) -> Walking
    (m.distance < 10) -> Stopped
} PowerOff

Another problem that occurs with this way of writing transitions is how to handle transition to the same state as the program currently are in. In some programs it don’t matter if a transition goes from a state to itself and thereby running the on exit and the on entry clausula again, but in other programs it might be crucial that it does not loop in a specific state. This problem I want to solve by introducing a new keyword: notself. This is to be placed at the end of the transition declaration, after a eventually comma separated list of excluded states. Here is an example that show that if bender is in the Running state he can not loop into the Running state again, if he is walking he can not start to walk, but if he is stopped he can still stop one more time. No mater how illogical that seems. Remember that Bender is from Futurama and dosn’t need to be logical.

transitions m : Head?distance {
    (m.distance > 5000) -> Running, notself
    (m.distance < 5000 and m.distance > 10) -> Walking, notself
    (m.distance < 10) -> Stopped
} PowerOff

Lets move on to the third problem that needs to be solved. Unfortunately this problem does not fit into the Bender example, at least not right now, so I will explain it in a more generic way. Say that we have a state machine with four states S1 to S4 these have all one transition to each of the other three states and are triggered by the same messages, as we have seen in the previous examples. But lets say that S4 is a little different, instead of transiting to S2 on a specific condition as the rest of the states, S4 wants to transit to S3 instead on that specific condition. To solve this problem I propose that it should still be aloved to write transitions inside the states as it is currently done in ThingML. This will allow the compiler to first check the global transitions and thereafter check if there is a local transition inside the state, and if it is give that local transition precedence over the global transition. To show this in the Bender example lets add a rule, for example that Bender is not allowed to rise his arms while Running because this will be to dangerous to his surroundings. So as a safety measure we will instead go into the LowerArms state, since we actually dosn’t know if his arms are pointing upwards or downwards. The code will look like this:

transitions m : Ears?positive {
    -> RiseArms
} PowerOff
...
statechart BenderImpl init PowerOff{
...
    state Running{
        on entry do
            Legs!run()
       end

        transition -> LowerArms
        event Ears?positive
    }
...

Now it is time to make a quick comparison between the Bender program written in my proposed way to the way it should be written in the current version of ThingML. Here you can see my implementation:

import "legs.thingml"
import "arms.thingml"
import "head.thingml"
import "ears.thingml"
import "power.thingml"
import "alcohol.thingml"
import "../../thingml.thingml"

thing Bender includes LegsMsgs, ArmsMsgs, HeadMsgs, EarsMsgs, PowerMsgs, AlcoholMsgs{

    required port Ears{
        receives positive
        receives negative
    }
    required port Arms{
        sends rise
        sends lower
    }
    required port Legs{
        sends run
        sends walk
        sends stop
    }
    required port Head{
        receives knock
        receives distance
        sends chantMessage
    }
    required port Power{
        recieves powerOn
        recieves powerOff
    }
    required port Alcohol{
        receives low
    }

    transitions m : Head?distance {
        (m.distance > 5000) -> Running
        (m.distance < 5000 and m.distance > 10) -> Walking
        (m.distance < 10) -> Stopped
    } PowerOff

    transitions m : Ears?positive {
        -> RiseArms, PowerOff
    }
    transitions m : Ears?negative {
        -> LowerArms, PowerOff
    }
    transitions m : Head?knock {
        -> Talking, PowerOff
    }
    transitions m : Alcohol?low {
        -> PowerOff
    }

    statechart BenderImpl init PowerOff{

        state PowerOff{
            on entry do
                Legs!stop()
                Arms!lower()
                //Code to shut down goes here
            end
        }
        state PowerOn{
            on entry do
                //Code that boots system goes here
            end
        }
        state Running{
            on entry do
                Legs!run()
            end
            transition -> LowerArms
            event Ears?positive
        }
        state Walking{
            on entry do
                Legs!walk()
            end
        }
        state Stopped{
            on entry do
                Legs!stop()
            end
        }
        state RaiseArms{
            on entry do
                Arms!rise()
            end
        }
        state LowerArms{
            on entry do
                Arms!lower()
            end
        }
        state Talking{
            on entry do
                Head!chantMessage()
            end
        }
    }
}

Here I managed to implement Bender in a smashing 103 lines long program, we do of course look away from the interfaces and actual implementation of the electronics that goes into Bender since it is not important to the scope of this article. By doing it the traditional ThingML I got astonishing 254 lines of code, that is more then twice the amount of code.  The file is available here :Download.  Now imagine that you have discovered that one of your transactions are subject to change, that means that you have to traverse through the code and find everywhere that the transition is written and change it accordingly. This is time consuming work that can be avoided by implementing my proposed way of defining transitions in ThingML. Another argument for implementing my proposed changes into the language is that Internet of Thing (IoT) is something that is becoming more and more common and we need better languages to program our things. I feel that ThingML is a step in the right direction of bringing stuff online and I feel that we will see a lot more autonomous things in the future.  These things, who often are robots, are relying on getting sensory data in order to navigate and interact with their surroundings. Therefore it is often important for them to be able to react to every kind of input no matter what state they are currently in. My proposed changes makes this easier to accomplish and I believe that this will allow us to create better robots which can operate more smoothly in every kind of environment. I hope you can see the benefits from it as well and will give ThingML a try.

If you have any thought on this topic or any other things that might be relevant, donæt by shy to drop a line.

Master, School, Uncategorized, University

About the author

Sometime I write, sometime I don't. But most of the time I program, build a curcuit or just do something completely different.
No Responses to “Transitions in state machines”

Leave a Reply