Order of magnitude reasoning in qualitative differential equations

Computer Science Department TECHNICAL REPORT Order of Magnitude Reasoning in Qualitative Differential Equations Ernest Davisf Technical Report #31 2 August 1987 o o Qj r-( l-i 0) H- fD Qj < l-h f" fD Ml cn l-( O (T> 3 ' O o i-h n ^ f-( en 3 O (tiQ M 3 D (D tfl n- iQ C C 0) (-■(D H- rt n- r+ 1-3 wl I u>| O 3 cn < to O NEW YORK UNIVERSITY -eparfment of Computer Science Courant Institute of Mathematical Sciences 251 MERCER STREET, NEW YORK, N. Y. 10012 Order of Magnitude Reasoning in Qualitative Differential Equations Ernest Da\/isf Technical Report #312 August 1987 tThis research was supported by NSF grant DCR-8603758. Order of Magnitude Reasoning in Qualitative Differential Equations Ernest Davis ABSTRACT We present a theory that combines order of magnitude reasoning with envisionment of qualitative differential equations. Such a theory can be used to reason qualitatively about dynamical systems containing parameters of widely varying magnitudes. We present an a mathematical analysis of envi- sionment over orders of magnitude, including a complete categorization of adjacent pairs of qualitative states. We show how this theory can be applied to simple problems, we give an algorithm for generating a complete envision- ment graph, and we discuss the implementation of this algorithm in a running program. Order of Magnitude Reasoning in Qualitative Differential Equations Ernest Davis 1. Introduction Two mathematical techniques that have been found particularly useful in recent work on qualitative physical reasoning are the solution of qualitative differential equations through envisionment and order of magnitude reasoning. The object of this paper is to combine these two theories mathematically. Envisionment and qualitative differential equations are used to analyze the behavior of dynamical systems. If the physical structure of a dynamic system can be characterized in terms of relations between a finite set of state variables and their derivatives, then the envi- sionment process can determine at least partially the behavior over time of these variables and derivatives. The strength of the envisionment procedure is that it can use a partial categorization of the physical relations among the variables to derive a useful partial informa- tion about the behavior. For example, consider a block attached to a spring, moving in a straight line without friction. Given the weak constraint that the spring always exerts a force on the block pointed toward its rest point, the envisionment process can predict that the block will oscillate around the rest point. Envisionment has been applied in numerous physical domains, including electronics, mechanics, hydraulics, and heat transfer ([de Kleer and Brown, 85], [Forbus, 85], [Williams, 85]). The clearest exposition of the mathematics of the theory is [Kuipers, 85]. Envisionment suffers from a number of limitations: it is sometimes too weak mathematically to yield important inferences ([Kuipers, 85], [Struss, 87]), and its focus on differential behavior sometimes forces much complex but useless information to be generated ([Davis, 86]). Nonetheless, for many types of physical inference, it is a simple and effective mode of analysis. Order of magnitude reasoning is concerned with the analysis of physical systems in which one quantity is much greater than another, or in the comparison of two systems of the same structure, but which have corresponding quantities of very different magnitudes. For example, if a very massive block hits a very light one, order of magnitude reasoning can be used to infer that the massive block continues on its way unaffected, while the light block bounces off away from the massive one. The idea of order of magnitude reasoning is to approximate a very great ratio as an infinite ratio, and then to analyze the system in terms of an algebra of infinite and infinitesimal quantities. Such an algebra has been worked out in [Raiman, 86] and extended in [Dague, Raiman, and Deves, 87]. The natural next step is to combine these two modes of inference so that we may reason about the dynamical behavior of systems with quantities of widely varying magnitudes. For example, we would like to be able to reason that a very heavy block on a spring will have a much longer period of oscillation than a much lighter block on the same spring. This paper presents a theory combining order of magnitude reasoning with envisionment of qualitative differential equations, which supports such inferences. The theory introduces two technical innovations. First, each state of the system is labelled with its duration and with the net The problem addressed here was first brought to my attention by Dan Weld. I thank Dan Weld, Olivier Raiman, Asher Meth, Ben Kuipers, Leo Joskowicz, and Yumi Iwasaki for helpful discussions, and for their criticisms of an preliminary draft of this paper. This research was supported by NSF grant DCR-8603758. change to each parameter during the state. Second, we formulate a number of rules govern- ing the behavior of functions over orders of magnitudes. In other respects, each of our com- ponent subtheories is weaker than standard theories in the literature. Our theory of envision- ment allows only the fixed quantity spaces of sign and order of magnitude, not arbitrary discretizations of quantity spaces as in [Kuipers, 85]. Our order of magnitude algebra uses only three fixed ranges of orders of magnitudes, SMALL, MEDIUM, and LARGE, not arbi- trarily many as in [Raiman, 86] and [Dague, Raiman, and Deves, 87]. ([Weld, 87] presents an alternative method for making this inference, which does not assume that the ratio between the blocks is infinite, but rather does a careful analysis of the relation between changes in in parameters and their derivatives. This theory is stronger than ours, in that it requires weaker assumptions in the input, but it seems to be less generally applicable. ) The paper is organized as follows: Section 2 presents fundamental definitions and rules that govern the behavior of a solution to a set of qualitative differential equations. The basis of the definitions and the justifications of the rules lie in the theory of non-standard analysis with infinitesimals. Section 3 shows how these rules may be applied in the "heavy block on the spring" example and other examples. Section 4 presents an algorithm for constructing an envisionment graph from a set of qualitative differential equations. Section 5 discusses the CHEPACHET program, which implements this algorithm. Section 6 makes suggestions for further work. We assume that the reader is familiar with standard theories of envisionment, as in [Kuipers, 85] and [de Kleer and Brown, 85], and with non-standard analysis, as in [Robinson, 66] and [Davis and Hersch, 72]. 2. Theory We follow [Kuipers, 85] in structuring our theory. Quantities, derivatives, and time may take values from within the non-standard real line R*. We divide this line into seven disjoint intervals: (We use notation from [Dague, Raiman, and Deves]. ) ZERO = {0} SMALL = { X|X>0 and A'«l } (infinitesimals) MEDIUM = { X|X>0 and X~l } (standard reals) LARGE = { X |X>0 and 1«X } (infinitely large reals) - SMALL = { X I -X € SMALL } -MEDIUM = {X|-X€MEDIUM } -LARGE = {X|-X€LARGE } These sets and their unions are the qualitative sets. Note that SMALL and LARGE span many orders of magnitude while MEDIUM spans only one order of magnitude. Note also that there is no landmark value separating SMALL from MEDIUM or MEDIUM from LARGE; in non-standard analysis, there is no largest infinitesimal or smallest positive stan- dard real. Our theory can easily be extended to incorporate any finite number of orders of magnitude; we might, for example, have five positive orders VERY_SMALL, SMALL, MEDIUM, LARGE, VERY_LARGE. It is not clear how to extend the theory to infinitely many different orders, as in [Dague, Raiman, and Deves, 87]. Table 1 shows the basic arithmetic operations on the qualitative values. These follow directly from the axioms presented in [Raiman, 86]. Following the notation of [de Kleer and Brown, 85] and [Kuipers, 85] we define [X] to be the qualitative set containing the value X; for example [-1] = -MEDIUM, [0] = ZERO. If P (r) is a function of T, then we will use the notation dP for the qualitative value of the derivative; that is, dP(T)=[P(T)]. + -LARGE -yjEDiL'y: -SMAXL ' ZERO SMALL M^DILfM LARGE -LARGE -LARGE -LARGE, -L^. RGE -U^RGE -LARGE -LARGE [-L, L] -MEDIL^I -LARGE -MEDILT^I -MEDILTVl -MED I I'M [-M, M] 1 LARGE -S. VALL -LARGE -YiEDIL'Mi -SMALL -SMALL [-s, s] MEDIUM i U^RGE ZERO : -LARGE '-yiEDIUMJ -SMALL ZERO SMALL Imodium | LARGE SMALL i -LARGE , -MEDILM ; [-s, s] SMiALL SMiALL LARGE ! MEDILT^. : -LARGE 1 [-M, . M] I MiEDIO M-EDIL:M :4EDILiM M-EDIUM 1 LARGE LARGE : [-L, L] LARGE i LARGE LA. RGE LARGE LARGE j LARGE : X i -LARGE -MEDIL-M -SMALL 1 ZERO ! SMALL 1 mj:dli3'. -LARGE LARGE LARGE [S, L] ZERO 1 [-S, -L] 1 -LARGE -LARGE -MiEDIL^ LARGE MEDILT^i 3^ALL ZERO I -SMALL -MEDIUM -LARGE -SM-ALL , [S, L] SMALL i SMALL i ZERO i -Sx'^ALL -Si'-ALL [-L, -s] : i ZERO ZERO 1 ZERO 1 ZERO i ZERO ! ZERO ZERO SMALL ![-L, -S] -SMiALL t -SMALL i ZERO i SMALL SMALL [S, L] I MEDIUM I -LARGE -MEDIUM i -SMALL i ZERO i SMALL MEDIUM LARGE i LARGE -LARGE 1 [-L, -S] i ZERO 1 [S, L] LARGE LARGE ! Bracketed pairs, above, desiqnate intervals. For example [-M, M] is the set {-M. EDILIM, -SMALL, ' ZERO, S:4ALL, MEDIUM}. [-L, -S] is the set [-LARGE, -MEDIUM, -SMALL }. Table 1: Addition and Multiplication of Qualitative Sets, An interval of R* is a set of points / such that, for all X. YC/, if X<Z<Y then Z€/. An interval / is clos

Source: http://www.onread.org/files/order-of-magnitude-reasoning-in-qualitative-differential-equations-ernest-davis-64483.pdf