Embedded Control Systems Design/Finite State Machines and Petri Nets

Finite State Machines (FSM) and Petri Nets (PN) are conceptual models to represent the discrete interactions in a system.

A FSM is a conceptual model that represents how one single activity can change its behaviour over time, reaction to internally or externally triggered events.
A PN is a conceptual representation of how multiple activities are coordinated.

FSM's and Petri Nets are at a higher level than the actual software. This means it explains the behavior, but not how it can be implemented. It is an ideal representation, it doesn’t take time delays in account.

Categories of system complexity

Systems of different complexity are represented in different ways. An FSM or UML statechart (similar to FSM, but with more possibilities) can only represent a centralized system, so there is no coordination needed with other systems of its type. Examples of systems of this type are a soda machine, an elevator, ...

Systems with distributed hardware and a centralized software state can be represented using Petri Nets. The centralized software coordinates how the different pieces of hardware act on each other.

A system with distributed hardware and distributed software state can also be represented by a Petri Net, but in this case there is no central control unit. The different pieces of hardware have their own software state and they all 'know' the Petri Net. Now the different pieces have to coordinate themselves.

An example of a distributed system is Robocup. This is a soccer game played by robots. Every robot is a system. If there is a control tower coordinating the robots, this is a case of a centralized software state. The control tower itself can be seen as a system of its own, represented by a statechart with states like 'ball controlled by own team', 'ball controlled by other team', ... In each state, the robots have to cooperate in a different way; this is represented by different Petri Nets.

If there is no control tower, each robot has to control itself and they have to coordinate themselves. Each robot then 'knows' the Petri Net and has to make its own decisions, which can introduce some problems. These are handled later in the section 'Petri Net'.

Finite State Machine

A finite state machine is a model of discrete behavior, which consists of: a finite number of states, transitions between two of those states, and actions. A state represents a certain behavior. A transition indicates a state change and is guarded by a condition. An action is a description of an activity that is to be performed. If this action depends on the state, it’s called a Moore machine. If the action is performed when a transition occurs, so when the state and condition are satisfied, it’s called a Mealy machine. Most machines are both a Moore and Mealy machine at the same time.

Some integrated development environments (IDE) allow a designer to draw a FSM diagram on screen, and then the IDE automatically translates the diagram into a software or FPGA or ASIC implementation. This allows the designer to use a natural way of representation of the system.

Example 1

A robot is working at high speed. When someone opens the door to enter the room, the robot continues its work but at a lower speed to guarantee the safety of the person. When the person leaves the room through the door, he/she has to push a button after closing the door. Now the robot can continue its work at high speed.

File:Fsm example 1.png

Notice that this a Moore machine, because the outputs (actions) are state-based.

Also notice the fact that there is a difference between reality and the model of the reality. In the model, there is no time needed to check the condition. In reality, it takes some time to check the door-sensor and to check the pushbutton.

Example 2

In the train project, the lamps have to light up when the train passes through a tunnel. Although, when the train drives in daylight, the lamps should be dimmed. Depending on the driving direction, either the white or red light should be working.

File:Fsm example 2.png

Notice that this a Mealy machine, because the outputs(actions) are input-based.

File:Fsm example 3.png

Example 3

In the train project, the train has to slow down when it takes a turn. The motor has to work harder when the train is riding upon a hill. The transitions between states are controlled by beacons. The image shows the possible transitions from/to driving in a straight line, other transitions are possible too.

UML Statecharts

FSM, explained before, is limited in a way. You cannot have two states active at the same moment, next to each other. The UML statechart is an attempt to overcome this limitation while retaining its good features. This is only one of the many graphical representations of a system that are defined in UML. UML (Unified Modeling Language) is designed to specify, visualize, construct and document software-intensive systems. For more information, we refer to the Wikipedia page. The essential syntax of statecharts is very much like FSM's. In a statechart, it is possible that there are states within states, so there is a kind of a hierarchical structure. They are called substates and superstates or parentstates.Another possibility is concurrent states. By using branching, a state can be followed by more than one other state. Each transition can be guarded with its own condition. When more than one condition is satisfied, two states can be active at the same moment.

Compared to FSM, the design of an embedded system can be visualised a lot better and less complicated with sub- and superstates. You can see better how the system works and it's also easier for the designer to locate problems and to adapt the system. Because it's a standard, large number of simulation tools are available (StateMate, StateFlow, BetterState...). These simulation tools are just made to check the theoretical system, but you can never be sure that the embedded system will function properly. Available „back-ends“ translate StateCharts into C or VHDL. This enables software or hardware implementations.

Example

A good example to explain the usage of a statechart is a soda machine. The user inserts a quarter and the machine waits until the user has inserted a second quarter. After the user has chosen his drink, the drink is dispensed. The machine waits again. You have two big states: collecting and dispensing. They have substates because there are different drinks and every time the user inserts a coin a new state is entered. In theory this seems a good visualisation, but in practice there are a lot of other factors. These problems can be solved partially. The bottle could get stuck in the machine, so we make a new state next to the collecting and dispensing part like shown in the figure below.

Petri Net

Introduction

Petri Net(PN) is an abstract model to show the interaction between asynchronous processes. It is only one of the many ways to represent these interaction. Asynchronous means that the designer doesn't know when the processes start and in which sequence they'll take place. A common manner to visualize the concepts is with the use of places, tokens, transitions and arcs. We refer to the basics of Petri Net for a first introduction in notations. We want to mention that a transition can only fire when there are tokens in every input-place. When it fires, one token is taken from every input-place and every output-place from the transition gets an (extra) token.

File:Petrinet.png

Places can play the following roles:

a type of communication medium: the wireless connection in Robocup;
a buffer: all the robots send messages to each other. When one robot checks the first message, the other incoming information is placed in his memory;
a geographical location: the environment of a robot, a place he has to go to;
a possible state or state condition: normal mode and safe mode of a machine(see FSM);

Tokens can play the following roles:

a physical object: a robot;
an information object: a message between two robots;
a collection of objects: the people mover;
an indicator of a state: the state in which a robot is: defender/attacker;
an indicator of a condition: a token indicates whether a certain condition is fulfilled (ex. Soccer game starts when the referee gives the signal).

Transitions can play the following roles:

an event: start a thread, the switching of a machine from normal to safe mode;
a transformation of an object: a robot who changes his role, see further;
a transport of an object: the ball is passed between the robots.

An arc connects only places and transitions and indicates the direction in which the token travels.

Coordination problems

In a PN, situations can occur where two or more systems wait for each other before an action can take place. This is called a deadlock. It can also occur that a single system has to wait forever at the beginning of a transition because another process has always higher priority. This problem is called starvation.

In the mathematical model a transition takes no time. In the real world executing a transition takes some time and the sequence or timing of events becomes important. This problem relates to race conditions or race hazards. When the PN is rather big, these problems are hard to find.

Robocup examples

The problems and solutions that can occur will be introduced using the example Robocup. There has to be communication between the robots to achieve a certain purpose. We suppose that the autonomous robots are perfectly designed, so we use a behavior engineering approach.

When a robot stands on the field his behavior consists of a number of options. With these options and incoming information he decides what he is going to do.

Every robot can do some basic actions:

stand still
turn around
walk
go to ball
grab
pass
kick the ball
...

Two or more robots have to work together and therefore there actions have to be synchronized. The designer uses Petri Net as a virtual model to show the interactions.

Example: double pass scenario

When a robot sees an opponent in front of him and there is a teammate close to him, he can set up a double pass action. We refer to the petri net figure in the introduction. With this model, the software in the first robot can communicate with the software in the second robot. Sometimes instructions must wait on an input signal which indicates that the other robot has finished his action.

There can be problems when the double pass is planned in such a way. When the second robot dribbles and loses the ball, the first robot will wait forever to accept the pass. A better implementation would require continuous communication between the 2 robots. The second robot can tell that he has lost the ball or that he wants to pass to another player.

Example: wrong decision

Robots have to take decisions during the game. It takes some time to check several conditions and during this time the previous decisions can change from true to false. Consequently the robot does a wrong action. For example: A robot asks the ball. The robot who has the ball has to check two conditions. IF teammate asks ball AND I have the ball THEN give a pass. When this robot has checked the first condition, there can be an opponent who jumps in front of the asking robot, so the robot says he doesn't want the pass anymore. The first robot checks the second condition and he passes the ball which is then intercepted by the opponent. This simple example can be extended by a third condition(IF there's no opponent)

Example: deadlock situations

The principle of mutual exclusion says that a resource can only be assigned to one robot. When it isn't, the resource is free. When two robots claim the ball(=resource) a deadlock situation can occur because the ball is assigned to two different agents. This problem also relates to a circular wait condition because each robot waits for the other to release the ball.

The robots have to play a role(=resource) in their team. The role allocation can be as follows: primary attacker, offensive supporter, defensive supporter and goalkeeper. The role of goalkeeper is fixed throughout the game. The other three roles are more fluid. The robots signal one another constantly, broadcasting their estimate of the distance between themselves and the ball. Based on the various estimates, the robot that is closest to the ball takes on the role of primary attacker, proceeds towards the ball and tries to kick it towards the opposing team's goal. The offensive supporter also moves towards the ball, but stops before it gets too close. The defensive supporter waits until the ball approaches him (before switching to a primary attacker mode). There can occur problems when assigning those roles to the robots. Consider the role as primary attacker which can be allocated to exactly one robot. If no robots are allocating this resource, the team suffers since no robot will try to move to the ball. If several robots are allocating this resource then the team will suffer as they interfere with one another because they all try to get the ball. Another problem is the time delay which occurs during the switching between two roles. A robot must first release resources so another robot can take it. Within this time the robot freezes and can't perform an action.
In a critical situation when the attacker robot loses power, a deadlock situation can occur. The robot can't release his attacker role, so there are no agents who run towards the ball because they can't be primary attacker(the resource isn't released). This problem can be avoided with the communication between the robots or with an automatic release function when the power shuts down.

Other models

The previous models have a lot of extensions and variations. Because the list is so elaborate, only a few models are discussed.

Colored Petri Nets

In a colored PN every token is an object with some properties. These properties can change when it travels through the structure. With these properties a certain object can, for example, get priority to other objects. Every object has some kind of Finite State Machine to follow and the coordination between the different objects is done by the colored Petri Net. So colored PNs can be considered as a combination of coordination and computation.

Communicating sequential processes (CSP)

Communicating sequential processes (CSP) is a language, used in computer science, to describe the interaction in concurrent systems. Due to this concurrency, communication is essential. Every "message" is a combination of coordination and communication. This way, a formal verification between the processes is possible.