Coördination Modelling

Model Representation

The coordination of a system can be modeled as a discrete-event system (DES). The behaviour of these systems is governed by discrete events occurring asynchronously over time. To model this discrete behaviour one can use Finite State Machines (FSM) or Petri Nets (PN). FSM are used where the decision making is centralized, instead PN are used where the decision making is distributed (multiple agents) (more on centralized vs. distributed: view a previous chapter). These two modelling tools are sufficient to model every DES. Every PN can be converted to an FSM and vice versa. These modeling tools can be used to visualize, analize, designing and optimizing the coordination of a system.

Finite State Machines (FSM)

FSM models a discrete-event system as a combination of these model primitives: a set of states and a set of transitions. To go from a state to another, one has to satisfy the appropriate condition (the occurrence of an event) between the two states. For more elaborated documentation: view the corresponding section in this Wikibook, the wikipedia page, or the appendix.

FSM model primitives

The idea of FSM can be expanded; when the outcome of events are not deterministic but stochastic, this can be modelled by a Markov Decision Process (MDP)

Petri Nets (PN)

PN models a discrete-event system as a combination of these model primitives: a set set of places, a set of transitions and a set of tokens. Places represent conditions and transitions represent events. The state of a PN is described by the marking of the PN. A marking is an assignment of tokens to places in the net. These tokens represent the conditions indicated by particular places which hold at a moment of time. A transition can only fire when it is enabled. A transition is enabled if each of its input places has at least one token in it. When it fires one token from each input place will be taken and one token will be put in each output place of the transition. For more a more detailed explanation: view the corresponding section in this Wikibook, the wikipedia page, or the appendix.

PN model primitives

Descrete Event System Properties

This section handles the general properties of discrete event systems.

Discrete

In nature everything is a continuous process. When modelling a system with a discrete-event system, one assumes that certain behaviour doesn't change through time. This constant behaviour is represented by a state.

Asynchronous nature

Because FSM and PN are discrete models, time isn't measured. Consequently, one doesn't know how long a transition from one state to another takes. Only the order of event occurrence is important. In reality transitions take time, so during a transition the system will be in an undefined state because instantaneous transitions are assumed. These timing aspects can be modelled but this makes the model more complex and harder to understand.

Deadlocks

When modelling distributed systems, one must taken account for the occurrence of never being able to fire a transition because there are no tokens left to fill the empty transition inputs (because alle other tokens are also waiting on a transition). This situation of mutual waiting is called a deadlock.

Uninterpreted model

The states and transitions in FSM and PN are labeled with statements. These labels make clear what the state represents and what fysical condition will trigger an transition. If one would change the name of these labels, this wouldn't affect the execution of the models. That's why PN and FSM are uninterpreted. The same FSM or PN can describe many systems.

Hierarchy

Every FSM can be a sub-FSM of another, bigger FSM. The same is true for PN. The sub-FSM is represented by a separate state, while a sub-PN is replaced by one transition or one place. Hierarchy makes a model better to understand.

Design lessons

From the previous properties one can derive some design rules. These are summarised in this section.

General

When designing the coordination of a system as a discrete event system, one should always keep the timing aspects in mind. Transitions in DES take no time at all, in contrast to real life. Outputs could for example take some time to emerge and neglecting this could make your model behave in an unpredictable way. Always model time when it's an important property of your system.

Other concerns are the starting-up and the shutting down behaviour. Often FSM and PN are represented as if they never have to boot up or to shut down, while real-life systems do encounter these conditions. Neglecting these conditions can cause the system to behave unpredictable and maybe even hazardous. The start and end procedures could be modelled as a separated FSM or PN.

Always use a hierarchical structure to clearify your design. With hierarchy it is also easy to model starting and ending. Starting for example is a state of a system. When all conditions are met, the system can go to its next state, the normal behaviour. When the system needs to shut down, it can go to its last state, the shut-down-state.

Design of FSM

FSM are widely used to design control systems. However, there are no general indications as to which type of FSM model (Moore vs. Mealy) is best to use in your design. Choice of a model depends on the application, execution means (for instance, hardware systems are usually best realised as Moore models) and preferences of a designer or programmer (Moore or Mealy Model?). The most simple model to understand and to program is the Moore model. The exit actions of the Mealy model should be treated as an auxiliary feature to simplify design or to reduce the number of states. This way you'll get a mixed model of both Moore and Mealy structure. However, be careful to mix synchronous Mealy and Moore models when synchronising two FSM. From experience it appears that this can cause the FSM to receive inputs from each other at unpredicted moments in time.

There are many programming tools like Xilinx to convert state charts to electrical circuits, to program an FPGA for example. VHDL, a programming language to design synchronous FSM, is also used. Matlab Simulink is also a useful tool to design FSM.

Design of Petri nets

Petri nets are less intuitive but very useful to check a system for deadlocks. A PN should be used to model a system when an FSM behaves unpredictable or when there appears to be a synchronisation problem.