packageQSS

Quantised State Systems

Information

Quantised State Systems

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={Q₀,Q₁,...,Q_r} be a set of real numbers where Q_k-1< Q_k 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) =	Q_m	if t=t₀
	Q_k+1	if x(t)=Q_k+1 and q(t^-)= Q_k and k < r
	Q_k-1	if x(t)=Q_k -ε and q(t^-)= Q_k and k > 0
	q(t^-)	otherwise

and

m =	0	if x(t₀) < Q₀
	r	if x(t₀) >= Q_r
	j	if Q_j <= x(t₀) < Q_j+1

The discrete values Q_i and the distance Q_k+1 - Q_k (usually constant) are called the quantisation levels and the quantum respectively. The boundary values Q₀ and Q_r 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.