446
Discrete Time Systems
Tudoroiu, N.; & Khorasani, K. (2005). Fault detection and diagnosis for satellite's attitude
control system using an interactive multiple model approach, Proceedings of 2005
IEEE Conf. Control Applications, pp. 28-31, Toronto, Ont.
Venkatasubramanian, V.; Rengaswamy, R.; Kavuri, S.N.; & Yin, K. (2003a). A review of
process fault detection and diagnosis part III: process history based methods.
Computers and Chemical Engineering, vol. 27, no. 3, pp. 327-346
Venkatasubramanian, V.; Rengaswamy, R.; Yin, K.; & Kavuri, S.N. (2003b). A review of
process fault detection and diagnosis part I: quantitative model-based methods.
Computers and Chemical Engineering, vol. 27, no. 3, pp. 293-311
Willsky, A. (1976). A survey of design methods for failure detection in dynamic systems.
Automatica, vol. 12, pp. 601—611
Yen, G.G.; & Ho, L.W. (2003). Online multiple-model-based fault diagnosis and
accommodation, IEEE Transactions on Industrial Electronics, vol. 50, no. 2, pp. 296 -
312
Zhang, Y.; & Jiang, J. (2001). Integrated active fault-tolerant control using IMM approach,
IEEE Transactions on Aerospace and Electronic Systems, vol. 37, no. 4, pp. 1221 - 1235
Zhang, Y.; & Li, X.R. (1998). Detection and diagnosis of sensor and actuator failures using
IMM estimator. IEEE Transactions on Aerospace and Electronic Systems, vol. 34, no. 4,
pp. 1293—1311
25
Discrete Time Systems with Event-Based
Dynamics: Recent Developments in Analysis
and Synthesis Methods
Edgar Delgado-Eckert1, Johann Reger2 and Klaus Schmidt3
1 ETH Zürich
2 Ilmenau University of Technology
3 Cankaya University
1 Switzerland
2 Germany
3 Turkey
1. Introduction
1.1 Definitions and basic properties
Discrete event systems (DES) constitute a specific subclass of discrete time systems whose
dynamic behavior is governed by instantaneous changes of the system state that are triggered
by the occurrence of asynchronous events. In particular, the characteristic feature of discrete
event systems is that they are discrete in both their state space and in time. The modeling
formalism of discrete event systems is suitable to represent man-made systems such as
manufacturing systems, telecommunication systems, transportation systems and logistic
systems (Caillaud et al. (2002); Delgado-Eckert (2009c); Dicesare & Zhou (1993); Kumar &
Varaiya (1995)). Due to the steady increase in the complexity of such systems, analysis and
control synthesis problems for discrete event systems received great attention in the last two
decades leading to a broad variety of formal frameworks and solution methods (Baccelli et al.
(1992); Cassandras & Lafortune (2006); Germundsson (1995); Iordache & Antsaklis (2006);
Ramadge & Wonham (1989)).
The literature suggests different modeling techniques for DES such as automata (Hopcroft
& Ullman (1979)), petri-nets (Murata (1989)) or algebraic state space models (Delgado-Eckert
(2009b); Germundsson (1995); Plantin et al. (1995); Reger & Schmidt (2004)). Herein, we focus
on the latter modeling paradigm. In a fairly general setting, within this paradigm, the state
space model can be obtained from an unstructured automaton representation of a DES by
encoding the trajectories in the state space in an n-dimensional state vector x( k) ∈ Xn at each
time instant k, whose entries can assume a finite number of different values out of a non-empty
and finite set X. Then, the system dynamics follow
F( x( k + 1), x( k)) = 0,
x( k) ∈ Xn
where F marks an implicit scalar transition function F : Xn × Xn → X, which relates x( k) at
instant k with the possibly multiple successor states x( k + 1) in the instant k + 1. Clearly, in
the case of multiple successor states the dynamics evolve in a non-deterministic manner.
448
Discrete Time Systems
In addition, it is possible to include control in the model by means of an m-dimensional control
input u( k) ∈ Um at time instant k. This control input is contained in a so called control set (or
space) Um, where U is a finite set. The resulting system evolution is described by
F( x( k + 1), x( k), u( k)) = 0,
x( k) ∈ Xn, u( k) ∈ Um
In many cases, this implicit representation can be solved for the successor state x( k + 1),
yielding the explicit form
x( k + 1) = f ( x( k), u( k))
(1)
or
x( k + 1) = f ( x( k))
(2)
when no controls are applied. As a consequence, the study of deterministic DES reduces to
the study of a mapping f : Xn → Xn, or f : Xn × Um → Xn if we consider control inputs,
where X and U are finite sets, X is assumed non-empty, and n, m ∈ N are natural numbers.
Such a mapping f : Xn → Xn is denoted as a time invariant discrete time finite dynamical system.
Due to the finiteness of X it is readily observed that the trajectory x, f ( x), f ( f ( x)), ... of any point x ∈ Xn contains at most |Xn| = |X|n different points and therefore becomes either cyclic
or converges to a single point y ∈ Xn with the property f ( y) = y (i.e., a fixed point of f ). The
phase space of f is the directed graph ( Xn, E, π : E → Xn × Xn) with node set Xn, arrow set E
defined as E := {( x, y) ∈ Xn × Xn | f ( x) = y} and vertex mapping
π : E → Xn × Xn
( x, y) → ( x, y)
The phase space consists of closed paths of different lengths that range from 1 (i.e. loops
centered on fixed points) to |Xn| (the closed path comprises all possible states), and directed
trees that end each one at exactly one closed path. The nodes in the directed trees correspond
to transient states of the system. In particular, if f is bijective1, every point x ∈ Xn is contained
in a closed path and the phase space is the union of disjoint closed paths. Conversely, if every
point in the phase space is contained in a closed path, then f must be bijective. A closed path
of length s in the phase space of f is called a cycle of length s. We refer to the total number of
cycles and their lengths in the phase space of f as the cycle structure of f .
Given a discrete time finite dynamical system f : Xn → Xn, we can find in the phase space
the longest open path ending in a closed path. Let m ∈ N0 be the length of this path. It is easy
to see, that for any s ≥ m the (iterated) discrete time finite dynamical system f s : Xn → Xn
has the following properties
1. ∀ x ∈ Xn, f s( x) is a node contained in one closed path of the phase space.
2. If T is the least common multiple of all the lengths of closed paths displayed in the phase
space, then it holds
f s+ λT = f s ∀ λ ∈ N
and
f s+ i = f s ∀ i ∈ { 1, ..., T − 1 }
We call T the period number of f . If T = 1, f is called a fixed point system.
In order to study the dynamics of such a dynamical system mathematically, it is beneficial to
add some mathematical structure to the set X so that one can make use of well established
mathematical techniques. One approach that opens up a large tool box of algebraic and graph
theoretical methods is to endow the set X with the algebraic structure of a finite field (Lidl &
1 Note that for any map from a finite set into itself, surjectivity is equivalent to injectivity.
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
449
Niederreiter (1997)). While this step implies some limitations on the cardinality2 |X| of the set
X, at the same time, it enormously simplifies the study of systems f : Xn → Xn due to the
fact that every component function fi : Xn → X can be shown to be a polynomial function of
bounded degree in n variables (Lidl & Niederreiter (1997), Delgado-Eckert (2008)). In many
applications, the occurrence of events and the encoding of states and possible state transitions
are modeled over the Boolean finite field F2 containing only the elements 0 and 1.
1.2 Control theoretic problems – analysis and controller synthesis
Discrete event systems exhibit specific control theoretic properties and bring about different
control theoretic problems that aim at ensuring desired system properties. This section
reviews the relevant properties and formalizes their analysis and synthesis in terms of the
formal framework introduced in the previous section.
1.2.1 Discrete event systems analysis
A classical topic is the investigation of reachability properties of a DES. Basically, the analysis
of reachability seeks to determine if the dynamics of a DES permit trajectories between given
system states. Specifically, it is frequently required to verify if a DES is nonblocking, that is, if it
is always possible to reach certain pre-defined desirable system states. For example, regarding
manufacturing systems, such desirable states could represent the completion of a production
task. Formally, it is desired to find out if a set of goal states X g ⊆ Xn can be reached from a
start state ¯ x ∈ Xn.
In the case of autonomous DES without a control input as in (2), a DES with the dynamic
equations x( k + 1) = f ( x( k)) is denoted as reachable if it holds for all ¯ x ∈ X that the set X g is reached after applying the mapping f for a finite number of times:
∀ ¯ x ∈ Xn∃k ∈ N s.t. f k( ¯ x) ∈ X g.
(3)
Considering DES with a control input, reachability of a DES with respect to a goal set X g holds
if there exists a control input sequence that leads to a trajectory from each start state ¯ x ∈ Xn
to a state x( k) ∈ X g, whereby x( k) is determined according to (1):
∀ ¯ x ∈ Xn∃k ∈ N and controls u(0), . . . , u( k − 1) ∈ Um s.t. x( k) ∈ X g.
(4)
Moreover, if reachability of a controlled DES holds with respect to all possible goal sets X g ⊆
Xn, then the DES is simply denoted as reachable and if the number of steps required to reach
X g is bounded by l ∈ N, then the DES is called l-reachable.
An important related subject is the stability of DES that addresses the question if the dynamic
system evolution will finally converge to a certain set of states ((Young & Garg, 1993)).
Stability is particularly interesting in the context of failure-tolerant DES, where it is desired to
finally ensure correct system behavior even after the occurrence of a failure. Formally, stability
requires that trajectories from any start state ¯ x ∈ Xn finally lead to a goal set X g without ever
leaving X g again.
Regarding autonomous DES without control, this condition is written as
∀ ¯ x ∈ Xn∃l ∈ N s.t. ∀k ≥ l, f k( ¯ x) ∈ X g.
(5)
In addition, DES with control input require that
∀ ¯ x ∈ Xn∃k ∈ N and controls u(0), . . . , u( k − 1) ∈ Um s.t. ∀l ≥ k x( l) ∈ X g, (6)
2 A well-known result states that X can be endowed with the structure of a finite field if and only if there
is a prime number p ∈ N and a natural number m ∈ N such that |X| = pm.
450
Discrete Time Systems
whereby k = 1 for all ¯ x ∈ X g.
It has to be noted that stability is a stronger condition than reachability both for autonomous
DES and for DES with control inputs, that is, stability directly implies reachability in both
cases.
In the previous section, it is discussed that the phase space of a DES consists of closed paths
– so-called cycles – and directed trees that lead to exactly one closed path. In this context, the
DES analysis is interested in inherent structural properties of autonomous DES. For instance,
it is sought to determine cyclic or fixed-point behavior along with system states that belong
to cycles or that lead to a fixed point ((Delgado-Eckert, 2009b; Plantin et al., 1995; Reger &
Schmidt, 2004)). In addition, it is desired to determine the depth of directed trees and the
states that belong to trees in the phase space of DES. A classical application, where cyclic
behavior is required, is the design of feedback shift registers that serve as counter circuits in
logical devices ((Gill, 1966; 1969)).
1.2.2 Controller synthesis for discrete event systems
Generally, the control synthesis for discrete event systems is concerned with the design of a
controller that influences the DES behavior in order to allow certain trajectories or to achieve
pre-specified structural properties under control. In the setting of DES, the control is applied
by disabling or enforcing the occurrence of system events that are encoded by the control
inputs of the DES description in (1). On the one hand, the control law can be realized as a
feedforward controller that supplies an appropriate control input sequence u(0), u(1), . . . , in
order to meet the specified DES behavior. Such feedforward control is for example required
for reaching a goal set X g as in (4) and (6). On the other hand, the control law can be stated
in the form of a feedback controller that is realized as a function g : Xn → Um. This function
maps the current state x ∈ Xn to the current control input g( x) and is computed such that the
closed-loop system
h : Xn → Xn
x → f ( x, g( x))
satisfies desired structural properties. In this context, the assignment of a pre-determined
cyclic behavior of a given DES are of particular interest for this chapter.
1.3 Applicability of existing methods
The control literature offers a great variety of approaches and tools for the system analysis
and the controller synthesis for continuous and discrete time dynamical systems that are
represented in the form
˙ x( t) = f ( x( t), u( t))
or
x( k + 1) = f ( x( k), u( k)),
whereby usually x( t) ∈ R n, u( t) ∈ R m, and x( k) ∈ R n, u( k) ∈ R m, respectively.
Unfortunately, traditional approaches to analyzing continuous and discrete time dynamical
systems and to synthesizing controllers may fail when dealing with new modeling paradigms
such as the use of the finite field F2 for DES as proposed in Section 1.1. From a mathematical
point of view, one of the major difficulties is the fact that finite fields are not algebraically
closed. Also non-linearity in the functions involved places a major burden for the system
analysis and controller synthesis. In general, despite the simple polynomial shape of the
transition function f (see above), calculations may be computationally intractable.
For
instance, determining the reachability set ((Le Borgne et al., 1991)) involves solving a certain
set of algebraic equations, which is known to be an NP-hard problem ((Smale, 1998)).
Discrete Time Systems with Event-Based Dynamics:
Recent Developments in Analysis and Synthesis Methods
451
Consequently, one of the main challenges in the field of discrete event systems is the
development of appropriate mathematical techniques. To this end, researchers are confronted
with the problem of finding new mathematical indicators that characterize the dynamic
properties of a discrete system. Moreover, it is pertinent to establish to what extent such
indicators can be used to solve the analysis and control problems described in Section 1.2.
In addition, the development of efficient algorithms for the system analysis and controller
synthesis are of great interest.
To illustrate recent achievements, this chapter presents the control theoretic study of linear
modular systems in Section 2, on the one hand, and, on the other hand, of a class of nonlinear
control systems over the Boolean finite field F2, namely, Boolean monomial control systems in
Section 3, (first introduced by Delgado-Eckert (2009b)).
2. Analysis and control of linear modular systems3
2.1 State space decomposition
In this section, linear modular systems (LMS) over the finite field F2 shall be in the focus. Such
systems are given by a linear recurrence
x( k + 1) = A x( k),
k ∈ N0 ,
(7)
where A ∈ F n×n
2
is the so-called system matrix. As usual in systems theory, it is our objective
to track back dynamic properties of the system to the properties of the respective system
matrix. To this end, we first recall some concepts from linear algebra that we need so as to
relate the cycle structure of the system to properties of the system matrix.
2.1.1 Invariant polynomials and elementary divisor polynomials
A polynomial matrix P( λ) is a matrix whose entries are polynomials in λ. Whenever
the inverse of a polynomial matrix again is a polynomial matrix then this matrix is called
unimodular. These matrices are just the matrices that show constant non-zero determinant. In
the following, F denotes a field.
Lemma 1. Let A ∈ F n×n be arbitrary. There exist unimodular polynomial matrices U( λ), V( λ) ∈
F[ λ] n×n such that
U( λ)( λI − A) V( λ) = S( λ)
(8)
with
⎛
⎞
c 1( λ)
0
· · · 0
⎜
.
⎜
⎟
0
c
.. ⎟
S( λ) = ⎜
2( λ)
⎝ .
⎟
.
.
.
. .
0 ⎠ ,
(9)
0
· · · 0 cn( λ)
in which ci( λ) ∈ F[ λ] are monic polynomials with the property ci+1 | ci, i = 1, . . . , n − 1 .
Remark 2. Th