Quantized state systems method

The quantized state systems (QSS) methods [CK06] are a family of numerical integration solvers based on the idea of state quantization, which are dual to the idea of time discretization. Unlike traditional numerical solution methods, which approach the problem by discretizing time and solving for the next (real-valued) state at each successive time step, QSS methods keep time as a continuous entity and instead quantize the system's state, instead solving for the time at which the state deviates from its quantized value by a quantum. QSS methods are therefore neatly modeled by DEVS, a discrete-event model of computation, in contrast with traditional methods, which form discrete-time models of the continuous-time system.

First-order QSS method – QSS1

Let an initial value problem be specified as follows.

${\dot {x}}(t)=f(x(t),t),\quad x(t_{0})=x_{0}.$

The first-order QSS method, known as QSS1, approximates the above system by

${\dot {x}}(t)=f(q(t),t),\quad x(t_{0})=x_{0}.$

where $x$ and $q$ are related by a hysteretic quantization function

$q(t)={\begin{cases}x(t)&&{\text{if }}\left|x(t)-q(t)\right|\geq \Delta Q\\q(t^{-})&&{\text{otherwise}}\end{cases}}$

where $\Delta Q$ is called a quantum. Notice that this quantization function is hysteretic because it has memory: not only is its output a function of the current state $x(t)$, but it also depends on its old value, $q(t^{-})$.

This formulation therefore approximates the state by a piecewise constant function, $q(t)$, that updates its value as soon as the state deviates from this approximation by one quantum.

High-order QSS methods – QSS2 and QSS3

The second-order QSS method, QSS2, follows the same principle as QSS1, except that it defines $q(t)$ as a piecewise linear approximation of the trajectory $x(t)$ that updates its trajectory as soon as the two differ from each other by one quantum. The pattern continues for higher-order approximations, which define the quantized state $q(t)$ as successively higher-order polynomial approximations of the system's state.

It is important to note that, while in principle a QSS method of arbitrary order can be used to model a continuous-time system, it is seldom desirable to use methods of order higher than four, as the Abel–Ruffini theorem implies that the time of the next quantization, $t$, cannot (in general) be explicitly solved for algebraically when the polynomial approximation is of degree greater than four, and hence must be approximated iteratively using a root-finding algorithm. In practice, QSS2 or QSS3 proves sufficient for many problems and the use of higher-order methods results in little, if any, additional benefit.

Software implementation

The QSS Methods can be implemented as a discrete event system and simulated in any DEVS simulator.

QSS methods constitute the main numerical solver for PowerDEVS[BK011] software. They have also been implemented in as a stand alone version

References

• [CK06] Francois E. Cellier and Ernesto Kofman (2006). Continuous System Simulation (first ed.). Springer. ISBN 978-0-387-26102-7.

• [BK11] Bergero, Federico and Kofman, Ernesto (2011). "PowerDEVS: a tool for hybrid system modeling and real-time simulation" (first ed.). Society for Computer Simulation International,San Diego.{{cite news}}: CS1 maint: multiple names: authors list (link)

External links

• Stand-alone implementation of QSS Methods
• PowerDEVS at SourceForge