A UNIFIED REPRESENTATION FOR NUMERICAL AND QUALITATIVE SIMULATIONS

Daniel Berleant

University of Arkansas, Fayetteville

Abstract

Models fall naturally into two main categories, those of discrete systems and those of continuous systems. Our model-based reasoning work deals with continuous systems, augmented to provide for the possibility that one continuous system model transitions to another, as when a threshold event occurs such as a thermostat turning on.

One aspect of model-based reasoning is simulation. A model is defined and its behavior(s) inferred through qualitative or numerical simulation. The simulated trajectories then facilitate tasks that one expects model-based reasoning to aid in, such as prediction, monitoring, diagnosis, and design.

Here we describe an approach to representing simulation trajectories that results in descriptions of system behavior that contain both qualitative and quantitative information about trajectories closely integrated together. Those descriptions are supported by an internal representation methodology that also closely integrates qualitative and quantitative information. The internal representation methodology supports quantitative inferences about the trajectories, and an example trace of such inferencing is provided.

Keywords: qualitative simulation, semi-quantitative simulation, Q3, intervals, interval constraints.

Previous Work

Combining quantitative and qualitative simulation has been a goal of a number of researchers (e.g. de Kleer 1975 [1], Forbus and Falkenhainer 1992 [2], Bonarini and Maniezzo 1991 [3], DeCoste 1991 [4], Kay and Kuipers 1993 [5], Shen and Leitch 1993 [6]). Kuipers and Berleant [7] [8] showed how partial quantitative knowledge can be added to qualitative simulations of continuous systems, and the benefits to qualitative reasoning that ensue. Quantitative knowledge was expressed as intervals within which the values of variables in a qualitative simulation are known to lie at a given time point. Inference about the possible ranges of values of other variables at various qualitatively significant times was done using interval arithmetic (e.g. Moore 1979 [9]) to evaluate arithmetic expressions. The work has been applied to reasoning about chemical process control (Dalle-Molle 1989 [10]), hydroelectric dam water control (Farquhar and Brajnik 1994 [11]), and measurement, monitoring and diagnosis (Dvorak 1992 [12]).

Previous work on combining quantitative and qualitative information has treated quantitative and qualitative information as distinct types of knowledge. Kuipers and Berleant [7] integrated them to a degree. They used qualitative simulation to create sets of constraints such as additions, multiplications, and mean value theorem instantiations. Each qualitative behavior was represented with such a set of constraints. These constraints among symbolic variable values were then used to propagate partial quantitative information in the form of intervals to other variable values for which a priori quantitative information was not given. In this paper, we discuss a more unified approach to representing qualitative and quantitative information in a simulation trajectory, previously introduced in Berleant and Kuipers [8]. Here we review that work, describe how the representation it uses unifies qualitative and quantitative information, and provide a trace of quantitative inference using the representation.

A Single Representation for Quantitative and Qualitative Simulations

Figure 1 shows a qualitative simulation of an object dropped in a constant gravitational field, augmented with partial quantitative information. Figure 2 includes all of the qualitatively significant symbolic values of Figure 1, plus some new ones which are not qualitatively significant. Y45, for example, is a value for height that has the same qualitative properties as an infinite number of other values: it represents one of many heights which are between maximum height H and minimum height 0, and at which the object's height is decreasing. Let us look at how the improved representation illustrated by Figure 2 is both quantitative and qualitative.

Figure 2 is a quantitative simulation. There are three time points. T0 has the default value of 0, which is a precise number. The second time point, 0.45, is also a number, giving a step size of 0.45 - 0 = 0.45. The final time point, T1, is not a precise number, but it is a numerical value, albeit the imprecise one [0.521, 1.03]. Other values present in the simulation, such as H, G, and V23 (which have qualitative significance) are also imprecisely known numbers. Imprecise numbers are the best that can be obtained because the initial values of the simulation, H=[7.9, 8.1] and G=[-33, -31], are also imprecise. However some of this imprecision in the results could be improved by interspersing more time points (thereby reducing the average step size of the simulation), then running the quantitative inference algorithm on newly created constraints involving the newly explicit variable values. An example is provided later. Intuitively, it works for the same reason that a smaller step size typically produces better results in a purely numerical simulation, and indeed, interspersing new numerical time points is equivalent to reducing the time step size in a numerical simulation. Thus the representation in Figure 2 constitutes a quantitative simulation.

Figure 1: Qualitative simulation of an object dropped from about 8 feet. Intervals for H, G, and T0 are given. Resulting inferences about the values of V23 and T1 are rather weak. Note that all symbolic values (such as V23 and T1) have qualitative significance: they indicate starting or ending values, or in the case of INF and MINF, extreme values for the domain of a variable.

______________________________________________________

Figure 2 is a qualitative simulation. All qualitatively significant values are present. For example, T0 is when the object is dropped, T1 is when it hits the ground, H is the initial height from which it is dropped, G is gravitational acceleration, and V23 is the final, maximum velocity.

The simulation shown in Figure 2 illustrates the integrated representation which constitutes the conceptual contribution of this paper. A comparison of the weak quantitative conclusions shown in Figure 1 with the much stronger ones of Figure 2 shows that the conceptual improvement illustrated by Figure 2 leads to a useful improvement in inferencing capability as well.

Figure 2: Time 0.45 must be between T0 and T1. Actually putting it there explicitly is equivalent to simulating with a smaller step size, and results in inferences about variable values that are much better than in Figure 1. The result is both a qualitative and a numerical simulation.

______________________________________________________

A Unified Approach Benefits Qualitative Simulation

Consider the qualitative simulation of a dropped object shown in Figure 1. This simple system could be solved in closed form. However we will not do that, but rather use it as a relatively easily understood illustration of how the representation supports numerical inferences.

Given gravitational acceleration of [-33, -31] feet/sec2, and an initial height of [7.9, 8.1] feet, inferences about other variable values for this system are rather weak compared with other systems we have modeled, even though the interval inferencing technique described in [7] was augmented by a simple interval subdivision technique called Target Interval Splitting which I developed [13] (see e.g. [14] [15] for versions of the traditional interval subdivision technique). Auxiliary techniques for making inferences about intervals are useful in trimming the excess width which may occur in interval calculations.

Even the best techniques for dealing with explicitly represented knowledge may not be enough, however, when considerable information is only implicit, rather than explicit. For example, in Figure 1 there is no upper bound on how long it takes for the object to hit the ground. Yet in Figure 2, which explicitly (instead of implicitly as in Figure 1) represents the fact that time 0.45 occurs before time T1, there is an upper bound on how long the object takes to fall. The dropped object model has been chosen for this discussion because the weak bounds shown in Figure 1 motivated the research described here and because the dropped object model is a second-order system, which we have found more challenging than most first-order system models, even first-order models that at first glance may seem more complex.

In Figure 2, the numerically defined time point 0.45 was arbitrarily added between pre-existing qualitative time points T0 and T1. However, note that no new information or assumptions have been asserted, since the information that 0.45 is between T0=0 and T1>=0.488 is already implicit in Figure 1. Nevertheless, much narrower intervals could be inferred for the same variable values in Figure 2 than in Figure 1 because that new time point is now explicitly represented. Narrower intervals constitute better quantitative predictions about unknown variable values.

Let us take a closer look at how the improved inferences in Figure 2 are achieved.

Increasing the Power of Inference

There are two general approaches to achieving better inferences. One is extracting more from a representation. The aforementioned interval subdivision technique, Target Interval Splitting, is an example of this approach. The second way is by improving the representation so that an inferencing engine has more to work with. Next we use the second way as we look at how the computer can represent the information that was shown visually in Figures 1 and 2, and use it to achieve improved inferences.

The Knowledge Representation

Uncertain variable values are represented with intervals. Constraints among variable values are also represented. Most of them are defined by mathematical templates in the model definition which are instantiated perhaps several times in a particular qualitative behavior trajectory. For example, we might choose to model the momentum of a falling object by using as a template

(Eq. 1) momentum = mass * velocity

which is instantiated at different time points as constraints among variable values at those time points. For example, one of these constraints would relate the values final-mass, final-velocity, and final-momentum by the equation

(Eq. 2) final-momentum = final-mass * final-velocity.

While the model whose behavior is shown in Figure 1 does not happen to describe momentum, it does contain two derivative constraints. One of them is

velocity = d(height)/dt.

This constraint template is instantiated by the program for the variable values V23, H, and T1 of Figure 1. Instantiation is achieved using the mean value theorem (see any introductory calculus text). The form of the mean value theorem used here is

(Eq. 3) change-in-height = mean(velocity) * change-in-time

which is instantiated as H - 0 = [minimum(V23), 0] * (T1 - 0), or

(Eq. 4) H= [minimum(V23), 0] * T1

where mean(velocity) is in the interval [minimum(V23), 0]. This constraint among the qualitative values H, V23, and T1 can be used to try to narrow the intervals within which their values lie, for each of them in turn, using simple algebra and the arithmetic operations of interval arithmetic. Let us look at how this can be done.

----From Figure 1, T1 >= 0.488.

----Therefore time=0.45 occurs between the qualitatively significant time points T0 and T1.

----Quantitative time point 0.45 is explicitly added to the representation of the behavior that was originally inferred from the falling object model in Figure 1. This is shown in Figure 2.

----The velocity at time 0.45 is given the arbitrary name "V45" and the height "Y45".

----We now instantiate the general template of equation 3 twice:

(Eqs. 5) Y45 - H = [minimum(V45), 0] * (0.45 - 0)

0 - Y45 = [minimum(V23), maximum(V45)]

* (T1 - 0.45)

----As another example, we also get new instantiations of the model constraint

change-in-velocity = mean(gravity) * change-in-time.

One such instantiation is

(Eq. 6) V45 - 0 = [minimum(G), maximum(G)] * (0.45 - 0)

from which the inference

(Eq. 7) V45 is in [-14.9, -13.9]

can be calculated.

----In conjunction with other constraints extracted from the model, and ranges given for H and G (and T0), eqs. 5 enable inference of much narrower ranges for the values of T1 and V23. Compare the wide ranges inferred for T1 and V23 in Figure 1 to the much narrower ones found in Figure 2.

Note that insertion of other time points could also be done just as easily. This would allow additional instantiations of eq. 3 even more powerful than eqs. 5.

A Unified Approach Benefits Quantitative Simulation

Consider a system in which water flows into a tank with a partially clogged drain. This could result in an equilibrium water level at which the pressure at the drain is high enough to produce an outflow equal to the inflow. Or, it could result in overflow. These are two qualitatively distinct behaviors. Semi-quantitative simulation can automatically produce all qualitatively distinct behaviors that are consistent with the available quantitative information. Distinct numerical predictions will be made for each behavior. Numerical simulation alone cannot do this easily or automatically.

Furthermore, the intervals found by the combined simulation methodology are guaranteed to be safe [16], in that numerical predictions will be correct (assuming the model reflects the actual system correctly), although they may be weak, as in Figure 1. Numerical simulation usually does not provide such guarantees.

Finally, this technique is well suited to working with non-linear systems since the qualitative simulator makes no distinction between linear and non-linear systems.

Summary

This paper addresses simulation of continuous systems. I have described a unified representation and an inference methodology for semi-quantitative simulation, and some of its benefits.

Acknowledgements

The author would like to acknowledge the useful comments of one reviewer.

References

[1] J. De Kleer, Qualitative and Quantitative Knowledge in Classical Mechanics, AI-TR-352, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 1975.

[2] K. Forbus and B. Falkenhainer, Self-explanatory simulations: scaling up to large models, Proceedings of the National Conference on Artificial Intelligence (AAAI-92), San Jose, California, MIT Press, 1992.

[3] A. Bonarini and V. Maniezzo, Integrating qualitative and quantitative modeling, International Journal of Expert Systems, Vol. 4, No. 1, 1991, pp. 51-70.

[4] D. DeCoste, Dynamic across-time measurement interpretation, Artificial Intelligence, Vol. 51, No. 1-3, 1991, pp. 273-341.

[5] H. Kay and B. Kuipers, Numerical Behavior Envelopes for Qualitative Models, Proceedings of the National Conference on Artificial Intelligence (AAAI-93), MIT Press, 1993, pp. 606-613.

[6] Q. Shen and R. Leitch, Fuzzy qualitative simulation, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, 1993, pp. 1038-1061.

[7] B. Kuipers and D. Berleant, Using incomplete quantitative knowledge in qualitative reasoning, Proceedings of the National Conference on Artificial Intelligence (AAAI-88), St. Paul, Minnesota, MIT Press, 1988, pp. 324-329.

[8] D. Berleant and B. Kuipers, Qualitative-numeric simulation with Q3, in B. Faltings and P. Struss, eds., Recent Advances in Qualitative Physics, MIT Press, 1992, pp. 3-16.

[9] R. E. Moore, Methods and Applications of Interval Arithmetic, Society for Industrial and Applied Mathematics, Philadelphia, 1979.

[10] D. T. Dalle Molle and T. F. Edgar, Qualitative modeling of chemical reaction systems, in M. L. Mavrovouniotis, ed., Artificial Intelligence in Process Engineering, Academic Press, San Diego, 1991.

[11] A. Farquhar and G. Brajnik, A Semi-Quantitative Physics Compiler, 8th International Workshop on Qualitative Reasoning, June 1994.

[12] D. Dvorak, Monitoring and diagnosis of continuous dynamic systems using semiquantitative simulation, Ph.D. thesis, technical report AI92-170, Artificial Intelligence Laboratory, University of Texas, Austin, TX, 1992.

[13] R. Doyle, D. Berleant, L. Falcone, and U. Fayyad, Selective Simulation and Selective Sensor Interpretation in Monitoring, Proceedings of the AIAA Computers in Aerospace VII Conference and Exhibit, American Institute of Aeronautics and Astronautics, Washington, D. C., 1989, pp. 859-870.

[14] N. S. Asaithambi, S. Zuhe, and R. E. Moore, On computing the range of values, Computing, Vol. 28, 1982, pp. 225-237.

[15] E. Sacks, Hierarchical reasoning about inequalities, Proceedings of the National Conference on Artificial Intelligence (AAAI-87), Seattle, MIT Press, 1987, pp. 649-654.

[16] D. Berleant and B. Kuipers, Qualitative and Quantitative Simulation: Bridging the Gap, manuscript.