Module 1.2: Discrete event systems

An essential ingredient of synthesis-based engineering is the synthesis of a supervisory controller model. The synthesis procedure allows a computer to automatically compute a supervisory controller model, from a model of the plant (uncontrolled system) and a model of the requirements. The synthesis procedure requires that the cyber-physical system that is to be controlled can be seen as a discrete event system (DES). The plant model can then be modeled as a discrete event model.

Discrete event system

A discrete event system is a system that can be defined by a discrete set of all its possible states. The kind of cyber-physical systems that we consider in this course, such as water locks, bridges and X-ray machines, can all be characterized as discrete event systems. For instance, a bridge may have a bridge deck, which may be in various discrete states, as it is either fully opened, partially opened/closed, or fully closed. And opening and closing the bridge likely requires a motor, which may be either on or off. The states are usually named. For instance, we may name the states of the bridge deck as deck_is_open, deck_is_partially_open and deck_is_closed, and the states of the motor as motor_is_on and motor_is_off.

A discrete event system can transition from one state to another. For instance, a bridge deck that is opened, may be closed to allow cars to pass over the bridge. The motor is turned on first, making the motor transition from its off to its on state. The bridge deck then transitions from its fully opened state to its partially opened/closed state, and ultimately to its fully closed state. Then, the motor is turned off again, making it transition from its on state back to its off state. In discrete event systems, these transitions from one state to another occur at discrete points in time.

Each transition has an associated event that indicates a discrete change in the system. Events should be thought of as instantaneous changes. An event can represent different things. It may for instance represent a specific action like pressing a button, or a spontaneous occurrence dictated by mere chance like the breaking down of a machine. It may also represent conditions that are suddenly met, like temperature reaching a certain threshold. Events are the driving factors that can lead to changes in state. For instance, the motor has two events, since it can be turned on and off. And the bridge deck has three events, as it can become fully opened, partially opened/closed, and fully closed. A discrete event system may transition between its states many times, as for instance a motor is turned on, off, on, off, and so on. The events are usually named as well. They are ideally named after what happens in the system, rather than the effect of that change on the state of the system. For instance, the events to turn the motor on and off may be named turn_motor_on and turn_motor_off. And the events that indicate that the bridge deck has reached a different position, could be named deck_has_opened, deck_has_become_partially_open and deck_has_closed.

System behavior

A system consists of multiple parts, called components, like a bridge deck and a motor. A state of the entire system consists of a state for each of its components. That is, a single system state is a combination of states of the components of the system. For instance, the bridge as a whole may be in six different states, which cover all the combinations of the states of the deck and the motor: (deck_is_open, motor_is_on), (deck_is_open, motor_is_off), (deck_is_partially_open, motor_is_on), (deck_is_partially_open, motor_is_off), (deck_is_closed, motor_is_on) and (deck_is_closed, motor_is_off). (deck_is_open, motor_is_on) then indicates the state where the deck is fully open and the motor is turned on. The collection of all the possible states of a system is called the state space of the system.

Note that not all system states are always desired states, as some may be undesired or even unsafe. For instance, consider that there would also be a traffic light that indicates to road traffic when it is safe to cross the bridge. The state where the bridge deck opens, while the traffic light is green, is then clearly unsafe, as cars could drive over the opening bridge deck and fall into the water under the bridge. A supervisory controller may then be added to the system, to prevent the system for getting into such an unsafe state.

A system may transition from one state to another, when certain events occur. For instance, with event turn_motor_off the bridge may transition from state (deck_is_open, motor_is_on) to (deck_is_open, motor_is_off), from (deck_is_partially_open, motor_is_on) to (deck_is_partially_open, motor_is_off), or from (deck_is_closed, motor_is_on) to (deck_is_closed, motor_is_off).

As different events occur over time, a system may transition from state to state. In different situations, the system may behave differently, leading to different events to occur in different orders. In the theory behind discrete event systems, all the events of the system together are called the alphabet of the system. Each possible sequence of events that may occur in the system is called a word. And all the possible sequences of events that may occur in a system are together called the language of the system. This terminology comes from the fact that each event can be viewed as a unique letter, and together all the events (letters) form an alphabet. Using the letters of the alphabet, words can be formed (like sequences of events), and all the words together form a language. The language of an uncontrolled system represents the system's possible behaviors, all the different orders in which the events can occur. With a supervisory controller added to the system, undesired and unsafe situations are prevent, and thus certain orders of events are prevented. The language of a controlled system thus represents the system's desired behaviors, all the different orders in which the events are allowed to occur.

The concept of state space, and specifically how to compute state spaces, is later revisited in Module 2.

Time-driven and event-driven systems

Discrete event systems differ from continuous-time systems. For a continuous-time systems, such as a speedometer of a car, the system's state may change continuously as time progresses. In the figure below, the speed of a car is shown as a smooth curve, with time progressing from left to right, and the speed of the car increasing from bottom to top. In continuous-time systems, the state of the system depends on the time that has passed, and time thus 'drives' such systems. Such systems are therefore also referred to as time-driven systems.

Discrete event systems, as we discussed earlier, are defined by discrete states, and transitions between the states when certain events occur. In this course, we primarily consider discrete event systems where the events may occur at any moment in time, rather than at fixed moments in time. It is then the events, not time, that drive the system. Such systems are therefore also referred to as event-driven systems.

Since we need to model the plant as a discrete event system to be able to apply the synthesis procedure, the system should be event-driven. If a supervisory controller needs to be developed to control a time-driven system, that system needs to first be abstracted to an event-driven system. Rather than relying directly on continuous values, such as time, temperature and speed, relevant discrete events should be identified that signify relevant changes to these values. For instance, events could indicate when a certain amount of time has passed, when a temperature becomes too high, or when a car slows down so much that it stands still. How the events are chosen, depends on the system itself and the requirements to be imposed on the system. For instance, if a controller needs to ensure that the temperature of a system does not rise above a certain limit, it needs to be able to detect temperature changes around that limit.

Later in this course, in Module 5, we will also consider time-driven systems directly, for validation of synthesized controllers. The continuous-time part of the system is then no longer abstracted, but modeled as a time-driven system. And it is combined with a model of the discrete event controller. This combination of time-driven model and event-driven model of these different parts of the system is a so-called hybrid model.

Quiz