Problem 4.2
The state partitioning problem of
quantised systems
Jan Lunze
Institute of Automation and Computer Control
Ruhr-University Bochum
D-44780 Bochum
Germany
1 DESCRIPTION OF THE PROBLEM
Consider a continuous system whose state can only be accessed through a quantizer. The quantizer is defined by a partition of the state space. The system generates an event if the system trajectory crosses the boundary between adjacent partitions.
The problem concerns the prediction of the event sequence generated by the system for a given initial event. As the initial event does not define the initial system state unambiguously but only restricts the initial state to a partition boundary, when predicting the system behavior the bundle of all state trajectories have to be considered that start on this partition boundary. The question to be answered is: under what conditions on the vector field of the system and the state partition is the event sequence unique?
In more detail, consider the continuous-variable system
which formally can be represented as the result of the operator Quant applied to the state trajectory. H is the number of events generated by the system within the time interval [0, T]. The following considerations concern only those initial events e0 for which the quantized system generates an event sequence with H > 1.
In order to define the events precisely, the state partition should satisfy the following assumptions:
A1. The trajectories do not lie in the hypersurfaces that represent the partition boundaries.
A2. The system cannot generate an infinite number of events in a finite time interval.
A3. No fix-point of the vector field f lie on a partition boundary.
These assumptions can be satisfied by appropriately defining the state partitions for the given vector field f .
This problem can be reformulated in two versions:
Problem: For given vector field f , find a partition of the state space such that the quantized system is deterministic.
Problem B: For given vector field f and a state quantization Q, test whether the quantized system is deterministic.
Both formulations have their engineering relevance. Where problem A concerns the practical situation in which a state partition has to be selected, problem B refers to the test of the determinism of the system for given partition.
The problem stated so far is, possibly, too general in two respects. First, the problem for testing the determinism of the system should be as simple as possible. For a given partition consisting of N disjoint sets, Problem B can be solved by considering all trajectory bundles that start on all partition boundaries. Here, the characterization of classes of vector fields f and partitioning methods is interesting for which the complexity of the test is constant or grows only linearly with N. Second, for problem A it is interesting to find partitions that can be distinguished with only a few measurements. For example, rectangular partitions are interesting from a practical viewpoint which result from separate quantizations of all n state variables xi.
Nonautonomous systems.
The problem can be extended to nonautonomous quantized systems
systems a supervisor defines the quantized input in the same time instant in which an output event occurs.
Here the state partitioning problem includes also to define an output partition and an input set 
such that the quantized system is deterministic for all input sequences.
2 MOTIVATION AND HISTORY OF THE PROBLEM
The problem results from hybrid systems, whose simplest form is a continuous- variable system with discrete inputs. Many technological systems that are controlled by programmable logic controllers (PLC) have a continuous state space and are controlled by discrete inputs. The contrast of the conti-nous state and the discrete input does not matter because many systems are designed in such a way that any accessible input results in an unambiguous state or output event.
For example, the (simplified) state space of a lift has the state variables “vehicle position, ” and “door position” both of which are quantized where the vehicle position refers to the floor in which it stops and the two discrete door position are called “open” or “closed.” For the performance of this system, only the events are important, which refer to the beginning and the end of the presence of the vehicle or the door in one of these positions. As the PLC can only switch on or off, the motors of the vehicle or the door and it is programmed so that the next command is given only after the next output event has occurred, every new input event is followed by exactly one output event (unless the system is faulty). So, the lift is a continuous-variable system (3), (4) with quantized input and output, that is deterministic.
In this case, the solution to the state partitioning problem is simple. The determinism of the quantized system results from the fact that the system trajectories are parallel to the coordinate axes of the state space for all accessible inputs and the quantization refers to separate intervals of both state variables. So, the end point of any movement initiated by a PLC command is a point in the state space and every trajectory of the closed-loop system results in precisely one output event.
In a more general setting, continuous-variable systems are dealt with as quantized systems for process supervision tasks. Then the system is not designed to behave like a discrete-event system but has a continuous state space. The quantizers are introduced deliberately to reduce the information to be processed. For example, alarm messages show that a certain signal has exceeded a threshold. The state partitioning problem asks for the a choice of discrete sensors such that the system behavior is deterministic.
As the third motivation for the state partitioning problem, hybrid systems theory concerns dynamical systems with continuous-variable and discrete-event subsystems. The interfaces between both parts are the quantizer and the injector introduced above that transform the discrete output signal of the discrete subsystem into a real-valued input signal of the continuous subsystem and vice versa. The problem occurs under what condition the overall hybrid system has a deterministic input-output behavior if only the discrete inputs and outputs of the discrete subsystem are considered. The main source of nondeterminism results from the quantization of the signal space of the continuous subsystem, which again leads to the state partitioning problem.
In all these situations, the discrete behavior of a continuous system is considered. In the literature on fault diagnosis and verification of discrete control algorithms the hybrid nature of the closed-loop system is removed by using a discrete-event representation of the quantized system. As in many practical situations the quantizers can be chosen, the state partitioning problem asks for guidelines of this selection. For a deterministic discrete behavior, a deterministic model can be used to describe the quantised system. If, however, the discrete behavior is non-deterministic, a nondeterministic model like a nondeterministic or stochastic automaton or a Petri net has to be used. Several ways for determining such models for a given quantized system have been elaborated recently ([3], [4], [6], [7], [8], [9]).
3 AVAILABLE RESULTS
The first result on the state partitioning problem concerns discrete-time systems (rather than continuous-time systems) with
quantized state space. Reference [4] gives a necessary and sufficient condition for the determinism of the discrete behavior
for linear autonomous systems with a state space partition that regularly decomposes each state variable into intervals of
the same size. In [5] it has been shown how state partitions can be generated by mapping a given initial set 
(1) by the model (1) that is used with reversed time axis.
For the problem stated here, only preliminary results are available. If the system trajectories are, like in the lift example, parallel to the coordinate axes of the state space and the quantization boundaries define rectangular cells whose axes are parallel to the coordinate axes, the discrete behavior is deterministic. This situation is encountered if, for example, the state variables are decoupled and controlled by separate inputs. Hence, the model can be decomposed into
which corresponds again to the simple lift example. Another example is an undamped oscillator with a state partition that decomposes the state space into the two half-planes. Then the fix-point lies on the partition boundary (and, thus, violates assumption A3). However, the oscillator generates, for each initial state, a unique (alternating) event sequence.
Results on symbolic dynamics are closely related to the problem stated here (cf. [1], [2]). A bundle of trajectories (or flows) is considered, which generate a symbolic output if some partition boundary is crossed. The partition is called Markovian if all trajectories of the bundle cross the same partition boundary and, hence, generate the same symbol. In the terminology used there, the problem posed here asks the question how to find Markovian partitions.
BIBLIOGRAPHY
[1] A. Lasota, M. C. Mackey, Chaos, Fractals and Noise, Springer-Verlag, New York, 1994.
[2] D. Lind, B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995.
[3] J. Lunze, “A Petri net approach to qualitative modelling of continuous dynamical systems, ” Systems Analysis, Modelling, Simulation, 9, pp. 885-903, 1992.
[4] J. Lunze, “Qualitative modelling of linear dynamical systems with quan-tized state measurements, ” Automatica, 30, pp. 417-431, 1994.
[5] J. Lunze, B. Nixdorf, J. Schrod
er, “On the nondeterminism of discrete-event representations of continuous-variables systems, ” Automatica, 35, pp. 395-408, 1999.
[6] H.A. Preisig, M.J.H. Pijpers, M.Weiss, “A discrete modelling procedure for continuous processes based on state-discretisation, ” 2n MATHMOD, Vienna, pp. 189-194, 1997.
[7] J. Raisch, S. O’Young, “A totally ordered set of discrete abstractions for a given hybrid or continuous system, ” pp. 342-360 In: P. Antsaklis, W. Kohn, A. Nerode, S. Sastry, eds., Hybrid Systems II, Springer-Verlag, Berlin, 1995.
[8] J. Schröder, Modelling, State Observation and Diagnosis of Quantised Systems, Springer-Verlag, Heidelberg, 2002.
[9] O. Stursberg, S. Kowalewski, S. Engell, “Generating timed discrete models, ” 2n MATHMOD, Vienna, pp. 203-207, 1997.