An Assessment of Current Qualitative Simulation Techniques
Pierre Fouché, Benjamin J. Kuipers · University of Texas at Austin eBooks · 1993
QSIM is a powerful Qualitative Simulation algorithm, which now includes many features that have proven to be necessary in Qualitative Simulation. These features are : reasoning with Higher-Order Derivatives, having Multiple Levels of Abstraction, reasoning in the Phase Space representation, and reasoning about Energy. The aim of this paper is to provide a comprehensive view of all these techniques, by explaining their rationale, showing the problems they address and how they interact . Remaining problems in Qualitative Simulation are also discussed. Main Topic: Qualitative Simulation t This work has taken place in the Qualitative Reasoning Group at the Artificial Intelligence Laboratory, The University of Texas at Austin. Research of the Qualitative Reasoning Group is supported in part by NSF grants IRI-8602665, IRI-8905494, and IRI-8904454, by NASA grants NAG 2-507 and NAG 9-200, and by the Texas Advanced Research Program under grant no . 003658175. Pierre Fouch6 holds a grant from Rh6ne-Poulenc. Fouehd & Kuipers An Assessment ofCurrent Qualitative Simulation Techniques Introduction Qualitative Physics has experienced a rapid growth since its birth, generally dated to the special issue of the Artificial Intelligence Journal of December 1984 . Among all the formalisms that have been developed, QSIMI . originally designed by Kuipers [86] has been greatly improved by many researchers since. It now includes several features that have proven to be necessary in Qualitative Simulation, like reasoning with higher-order derivatives [de Kleer & Bobrow, 84; Kuipers & Chiu , 87], having multiple levels of description [Hobbs, 85 ; Kuipers & Chiu , 87], reasoning in the phase space representation [Sacks, 87; Struss, 88 ; Lee & Kuipers, 88; Doyle & Sacks, 89] and reasoning about energy [Fouch6 & Kuipers, 90a, 90b] . So far these techniques have been described separately and have not been compared to each other. Consequently it was not easy to decide, even for someone very familiar with Qualitative Simulation, which one to apply to solve a practical problem. This paper is an attempt to provide a comprehensive view of these techniques : for each of them we describe their rationale and intuitive appeal, and we compare their relative efficiency on two simple examples, widely used in the Qualitative Physics literature2 : a block-spring system with or without friction . The fast part of the paper presents the models and the result of their simulation with the QSIM kernel . It is shown that simulation is intractable, mainly because of a phenomenon known as Chatter . The second part is devoted to local reasoning techniques . Section 2.1 shows that reasoning with higher-order derivatives and introducing curvature constraints allows to eliminate this phenomenon, but that the real problem for the damped spring is that the level of description is not appropriate : the system is not constrained enough for QSIM to predict a total ordering of the relative occurrence of events, and behaviors keep proliferating . This phenomenon is referred to as Occurrence Branching . An alternate way to get rid of chattering, which turned out to solve in part the occurrence branching problem is to shift to a higher level of description by ignoring irrelevant distinctions . This is described in section 2.2 . All the preceding techniques still do not provide a good behavioral description of the damped-spring : QSIM still derives behaviors which are genuinely incompatible with any actual system that abstracts to the model. This problem of incompleteness mainly stems from a combination of the loss of quantitative precision with the local character of qualitative inferences . A way to get a global view of a system behavior is to use the Phase Space representation, as described in section 3.1 . This allows QSIM to derive that some properties of a system cannot change through time . The final step to get a correct behavioral description of the spring system is to introduce energy considerations, as shown in section 3.2 . A summary is provided in section 4. With the help of all these techniques, QSIM is now able to derive important properties of industrially significant systems [Fouch6 & Kuipers, 90a, 90b] . However some problems still remain : The way QSIM handle correspondences between qualitative values and creates new landmarks is not satisfactory ; QSIM provides no result about asymptotic behaviors; Finally QSIM cannot always determine whether a behavioral property is a system property. This is described in section 4. 1 . Basic Qualitative Simulation The Spring-Block system (figure 1 .1) consists of a block connected to a spring laying on a horizontal table . The block position is referenced by a variable X, the origin being the rest position . The frictionless system will often be referred to as the simple spring, and the other as the damped spring . Though extremely simple from a structural point of view, deriving their behaviors qualitatively has turned out to be challenging . We know that the IFor a detailed description of QSIM, see [Kuipers, 861; see [Kuipers, 89] for a tutorial view . 2For instance : [de Kleer & Brown, 84; FOrbus, 84; Kuipers, 86 ; Weld, 87; Trav6 & Dormoy, 88 ; Struss, 88 ; Lee & Kuipers, 88 ; Ishida, 89] Fouehes & Kuipers -An Assessment of Current Qualitative Simulation Techniques 2 Figure 1 .1 : The Spring-Block System 40 force FS exerted by the spring on the block is inversely proportional to its elongation X. While the relation between FS and X happens to be linear (Hook's law), we shall not make any linearity assumption, to demonstrate that Qualitative Simulation applies to non-linear systems . For the simple spring, we can directly model that the acceleration is inversely related to the position of the block . For the damped spring, the friction force FF is inversely proportional to the speed of the block and again we shall not assume that this relation is linear. Figure 1 .2 shows the models as they are given to QSIMI . (inf minf)))) ((MFS X) (minf inf) (0 0) (inf minf)) ((MFF V) (minf inf) (0 0) (inf minf)) ((add FS FF A)))) Figure 1 .2 : QSIM models of the simple and damped springs Simulation with the QSIM kernel: what we expect.. . We start the simulation with the spring stretched and the block immobile . The beginning of the expected behavior is the block moving towards its rest position . What it will do next depends on the friction force . If the motion is frictionless then the block will move across its rest position, reach another extreme and move back to its original position . One can describe this behavior as a stable oscillatory behavior . If friction occurs then it can move towards the rest position without crossing it, if the friction force is strong enough. This is an over-damped behavior. Otherwise, the system will exhibit decreasing oscillations . . . . and what we really get Figure 1 .3 shows the behavior tree2 of the simple and damped springs when behaviors are allowed to reach time point t8 and ra . Clearly this is not as simple as expected . I [Farquhar & Kuipers, 90; Throop et al., 90] describe in detail how to use the QSIM is implementation. 2 A filled circle represents a state at some time point, an empty circle a state at some time interval, a filled circle surrounded by a larger circle a quiescent state and an empty circle surrounded by a larger one a cyclic state, identical to a prior state in the same behavior. States followed by dashed lines are states whose successors have not been computed yet, due to a resource cut-off. Time increases from left to right. (define-QDE simple-spring (quantity-spaces (define-QDE damped-spring (quantity-spaces (X (minf 0 inf)) (X (minf 0 inf)) (V (minf 0 inf)) (V (minf 0 inf)) (A (minf 0 inf))) (A (minf 0 inf)) (constraints (FF (minf 0 inf)) ((d/dt X V)) (FS (minf 0 inf))) ((d/dt V A)) (constraints ((MX A) (minf inf) ((d/dt X V)) (0 0) ((d/dt V A))