This section explains a) why the DEVS
formalism is suited to simulate a continuous system and b) how
this is done in a correct way preserving the DEVS formalism's rule
of legitimacy.
Discrete Simulation of a Continuous
System
For a system to be representable by a DEVS model, the only
condition is to show an input/output behaviour that is describable
by a sequence of events. In other words, the DEVS formalism is able
to model any system with piecewise constant input/output
trajectories, since piecewise constant trajectories can be
described by events [Cellier05].
Hence, if we want to simulate a continuous system by a DEVS model,
we "just" have to transform the continuous system into a system
with piecewise constant input/output trajectories.
This was the basic idea of a quantisation based method developed in
the late nineties by Zeigler et al. [Zeigler98] to approximate a
continuous system by a discrete-event simulation: a quantisation
function was used to transform the continuous state variables into
quantised discrete valued variables (a quantisation function maps
all real numbers into a discrete set of real values).
Let us see now what it needs to quantise a continuous system.
Consider the following system given in its state-space
representation (remember that usually, continuous systems are
described by a set of differential equations):
dx/dt= f(x(t), u(t),t)
where x(t) is the state vector and u(t) is the input vector, i.e. a
piecewise constant function.
The corresponding quantised state system has the following
form:
dx/dt= f(q(t), u(t),t)
where q(t) is the (componentwise) quantised version of the original
input vector x(t), whereas a very simple quantisation function
could be
q(t)= floor(x(t))
The figure below shows the respective block diagrams for the
systems defined above. Note that the representation by block
diagrams will be useful as soon as we will want to map the system
onto a (coupled) DEVS model.
Unfortunately the subject is not as simple as it may seem: the
transformation of a continuous system into a discrete one by
applying an arbitrarily chosen quantisation function can yield an
illegitimate system (definition [Cellier05]: "A DEVS model is
said to be legitimate if it cannot perform an infinite number of
transitions in a finite interval of time." Illustrative
examples of cycling (illegitimate) systems can be found in
[Kofman01] and [Cellier05]). Hence, such an illegitimate system
would perform an infinite number of transitions in a finite time
interval. As a matter of fact, even Zeigler's quantisation based
method featured this problem, as the original approach of using a
piecewise constant quantisation function did not preclude
illegitimate systems automatically [Kofman01]. Thus, the
quantisation function has to be chosen very carefully, such that it
prevents the system from switching states an infinite number of
times in a finite time interval. This property can be achieved by
adding hysteresis to the quantisation function (proven in
[Kofman01]), which leads straightforward to the notion of Quantised
State Systems that have been introduced by Kofman in 2001 in order
to circumvent the issue of illegitimate system
transformations.
The subsequent paragraphs shall give a brief introduction into the
theory and use of Quantised State Systems as a (sufficient) means
to approximate continuous systems by discrete events. Special
attention is paid to the role of hysteresis in the quantisation
function.
Quantised State Systems
(QSS)
Quantised State Systems are defined as follows [Kofman01]: "QSS
are continuous time systems where the input trajectories are
piecewise constant functions and the state variable trajectories -
being themselves piecewise linear functions - are converted into
piecewise constant functions via a quantisation function equipped
with hysteresis."
The goal of Quantised State Systems is to provide a legitimate
system that can be simulated by the DEVS formalism. These two
properties are achieved by a) the fact that the input/output
trajectories are piecewise constant functions, which allows the
simulation by the DEVS formalism, and b) the addition of hysteresis
to the quantisation function by which the continuous system is
transformed into the discrete representation.
A hysteretic quantisation function is defined as follows
[Cellier05]: Let Q={Q0,Q1,...,Qr}
be a set of real numbers where Qk-1< Qk
with 1<= k<= r. Let Omega be the set of piecewise continuous
trajectories and let x element of Omega be a continuous trajectory.
The mapping b: Omega -> Omega is a hysteretic quantisation
function if the trajectory q=b(x) satisfies:
q(t) =
Qm
if t=t0
Qk+1
if x(t)=Qk+1 and q(t-)= Qk and
k < r
Qk-1
if x(t)=Qk -ε and q(t-)= Qk
and k > 0
q(t-)
otherwise
and
m =
0
if x(t0) < Q0
r
if x(t0) >= Qr
j
if Qj <= x(t0) <
Qj+1
The discrete values Qi and the distance Qk+1
- Qk (usually constant) are called the quantisation
levels and the quantum respectively. The boundary values
Q0 and Qr are the upper and the lower
saturation values, and ε is the width of the hysteresis window. The
following figure shows a quantisation function with uniform
quantisation intervals.
The figure below reveals the difference between a quantisation step
without and with hysteresis: the left part represents a
quantisation function without hysteresis that may change the value
of q(t) due to an infinitesimal variation of the state variable
x(t) (Δx=0), which entails of course a potential change of q(t)
within the same time step (Δt=0). The right part embodies a
hysteresis window of width ε and thus the change of q(t) is
delayed, i.e. only performed when x(t) has changed to a sufficient
extent (defined by ε: Δx=ε) which introduces a time delay depending
on how long it takes x(t) to change for the given extent (Δt=ε).
A formal prove why adding hysteresis to a quantisation function
guarantees a legitimate system transformation is given in
[Kofman01].
The Quantised State System described above is a first-order
approximation of the real system trajectory. Kofman however has
also introduced second- and third-order approximations that -
without the application of smaller "step" sizes (i.e. a smaller
quantum value) - may reduce the error made by the approximation.
These systems are referred to as QSS2 and QSS3. The higher-order
Quantised State Systems are based on the Taylor series up to first-
or second-order (for QSS2 and QSS3, respectively).
Since the possibility of having different types of QSS has only
been mentioned in view of the chapter about ModelicaDEVS,
they are not discussed any further here. However, a detailed
description of the QSS2 and the QSS3 can be found in [Kofman02] and
[Kofman05] respectively.
.ModelicaDEVS.UsersGuide.QSS
