‹ -*- text -*- .so ben;r init .sr right_heading Causal Reasoning .fi ‹ 1TUFTS UNIVERSITY0 ‹ 1WORKING PAPERS IN COGNITIVE SCIENCE0 ‹ ‹TUWPICS No. nn date .sp 1.5i  1Commonsense Reasoning About Causality:*  1Deriving Behavior From Structure*  1Benjamin Kuipers0 .foot Department of Mathematics, Tufts University, Medford, Massachusetts 02155. .br This research was supported in part by NIH Grant LM 03603 from the National Library of Medicine. .efoot .sp 1i 1Abstract* This paper presents a qualitative reasoning method for predicting the behavior of mechanisms characterized by continuous, time-varying parameters. The structure of a mechanism is described in terms of a set of parameters and the constraints that hold among them: essentially a "qualitative differential equation." The qualitative behavior description consists of a discrete set of time-points, at which the values of the parameters are described in terms of ordinal relations and directions of change. The behavioral description, or envisionment, is derived by two sets of rules: propagation rules which elaborate the description of the current time-point, and prediction rules which determine what is known about the next qualitatively distinct state of the mechanism. A detailed example shows how the envisionment method can detect a previously unsuspected landmark point at which the system is in stable equilibrium. .sp 1i  Running head: Causal Reasoning .sp 1i  To appear in 3Artificial Intelligence*. .bp .ls 2 1Section 1: Introduction0 People have a fundamental desire to understand how things work, and an equally fundamental desire to explain their understanding to others. In this paper, I describe a class of knowledge structures to support prediction, explanation and question answering using causal descriptions of physical systems. Within the following framework for causal reasoning (inspired by de Kleer [6,7]), I address the problem of how a qualitative description of the behavior of a system is derived from a qualitative description of its structure. .diag .fs 2 Structural -----> Behavioral -----> Functional description description description .fs 0 .ediag The 3structural description* consists of the individual variables that characterize the system and their interactions; it is derived from the components of the physical device and their physical connections. The 3behavioral description* (or 3envisionment*) describes the potential behaviors of the system as a network of the possible qualitatively distinct states of the system. I reserve the term 3functional description* for a description that reveals the purpose of a structural component or connection in producing the behavior of a system. Thus, the 3function* of a steam release valve in a boiler is to prevent an explosion; the 3behavior* of the system is simply that the pressure remains below a certain limit. The existing literature frequently obscures this distinction by using the term "function" to refer to behavior. The goal of this research is to develop a knowledge representation capable of describing human commonsense reasoning and explanation about physical causality. 3Commonsense* causal reasoning is qualitative reasoning about the behavior of a mechanism which can be done without external memory or calculation aids, although it may draw on concepts learned from the advanced study of a particular domain, e.g. automobile mechanics, computer architecture, or medical physiology. In order to be useful for modeling human commonsense knowledge, the computational primitives of our representation must not require excessive memory or processing resources. Simulation of the behavior of a mechanism is useful, for example in medical diagnosis, for determining the consequences of a hypothesized primary change, for predicting the expected course of the patient's disease, and for investigating the effects of hypothetical therapies. 3Qualitative* simulation is important because the physician typically lacks precise numerical values for many parameters characterizing the patient's state, and some parameters may be difficult or impossible to measure. In spite of this, the physician is clearly capable of making useful predictions. The knowledge representation described here was inspired by the attempt to capture the knowledge revealed by a physician explaining a case of kidney disease with an unusual presentation. A detailed analysis of the physician's behavior is presented elsewhere [20]. In this paper, I propose a simple but very general descriptive language for structural descriptions, and a qualitative simulation process for producing the behavioral description. The representation described here begins with a description of the structure of a mechanism that is similar to, but weaker than, a differential equation. The qualitative simulation produces a description of its behavior that corresponds to, but is weaker than, the continuous function that is a solution to the differential equation. Thus, the representation is intended to produce a useful qualitative description of behavior, starting with a qualitative description of structure that would be too weak to support more traditional reasoning methods. .bp .diag .fs 2 numerical or analytic solution Differential ----------------------------------------> f: AR* -> AR* Equation | | | | | | | | | | | | | | | | | | | V V Structural ----------------------------------------> Behavioral Description qualitative simulation Description .fi .fs 0 1Figure 1.0 The qualitative structural description is capable of capturing a less complete state of knowledge than a differential equation, and the qualitative simulation produces a partial description of the mechanism's behavior. Because the qualitative simulation uses heuristics, the two paths through the above diagram do not always yield the same result. .ediag Within the structural description, a mechanism is described as a collection of 3constraints* holding among time-varying, real-valued 3parameters*. The behavioral description consists of a finite set of 3time-points* representing the qualitatively distinct states of the system, and 3values* for each parameter at each time-point. A 3value* is a description of the real number corresponding to a parameter at a particular time-point. This description consists of the 3ordinal relations* holding among the different values in the behavioral description, and the 3IQ value* (the sign of the time derivative) of the parameter at that time. The envisionment proceeds first by 3propagating* the implications of initial facts through the constraints to complete a description of the system's state at the current time-point, and second by 3predicting* the characteristics of the next distinct qualitative state description. After reviewing related work, a simple example demonstrates the basic properties of the representation and the envisionment process. Then a more elaborate example shows how, without external information, the simulation process deduces the existence of a previously-unsuspected landmark value, and shows that the mechanism moves to a stable equilibrium about that value. The envisionment process has been implemented in Maclisp, as a program called ENV [10], which has run all the examples included here. The figures presenting the results of the envisionment have been laid out by hand for publication and are not in the actual output format. Appendices provide more formal specifications of the representation and the envisionment process, as well as an additional example addressing related issues. .bp 1Section 2: Related Research* Answering a question about the behavior of a physical system involves two quite different operations. Problem 3formulation* includes selecting which of several ways the physical situation should be described to allow a deeper examination. Problem 3solving*, in the narrow sense, starts with a formal description of a well-structured problem and derives an acceptable solution. The different approaches to problem formulation taken by experts and novices have been examined by psychologists such as Chi, Feltovich, and Glaser [3] and Larkin, McDermott, Simon, and Simon [22]. In particular, when solving problems in physics Chi, et al, show that experts describe the given situation in terms appropriate to the underlying physical principle (e.g. conservation of momentum) required for a solution, while novices describe the same situation in terms of the physical objects in the surface statement of the problem. Naturally, the expert is then able to proceed directly to the solution, while the novice must search a larger space of alternate solutions. The work described here is a method of solving problems previously formulated, applicable at either level of expertise. Artificial intelligence methods for qualitative reasoning about mechanisms were first developed by Rieger and Grinberg [25], whose knowledge representation consists of 3events*, 3tendencies*, 3states*, and 3statechanges*, related by several different types of 3causal links*. Their system produces realistic qualitative simulations of the behavior of mechanisms. However, their representation lacks a strong distinction between the structure and behavior of a mechanism, which we feel is critical to causal reasoning. More generally, their representation is ambiguous about whether its elements refer to the structure, potential behavior, or actual behavior of the mechanism being described. The CASNET program of Weiss, et al, [27] uses causal links to propagate confirmation scores among pathophysiological states describing the progression of glaucoma. However, the program has no knowledge of the relationship between physiological mechanisms and pathophysiological states, and so expresses causal relationships known to its authors, rather than doing causal reasoning itself. McDermott [24] has proposed an ambitious temporal logic for reasoning about events, actions, and plans as well as processes involving continuously varying parameters. In a sense, he has taken Rieger and Grinberg's representation based on states and events, and created a much extended representation on a better logical foundation, that is capable of addressing a larger set of issues. His logic, however, is oriented toward expressing the behavioral description as actions and events of various kinds, so the structural description is stated as conditionalized events, not as a separate type of description. Since McDermott's goal is to establish a logical framework for temporal reasoning, he demonstrates his logic by expressing many small example sentences rather than larger inference scenarios. Thus, he does not present a detailed set of rules and axioms for inferring behavior from structure. The aim of the present paper is to specify such a set of rules for causal inference, and to use only those features of a logic needed to express the rules. The 3envisionment* approach to reasoning about mechanisms based on the relationship between structure and behavior, rather than between actions and events, has been developed by researchers such as de Kleer [6,7] and Forbus [11,12]. When the qualitative description of a system's state is not strong enough to specify which of several futures it will actually follow, the envisionment becomes non-deterministic and the behavioral description contains a branch. Much of the research on envisionment processes has studied the use of external sources of information (e.g. quantitative [6] or teleological [7]) to resolve non-determinism in the envisionment. There is little agreement on the exact role or expressive power of the 3functional description*, which shows how the structure and components of the system contribute to its ability to perform its overall function [8,19]. The functional description of a system should make explicit not only what behaviors are possible for a system, but why. Thus, a functional description must includes terms that refer implicitly to changes past the final state of the system (e.g. 3stable equilibrium*), or even to states that do not occur in the envisionment (e.g. 3the steam release valve prevents explosions.*). The 3function* of the steam release valve, for example, must include a teleological relationship with the design process, in which the valve was added to the structure in order to prevent a certain behavior. There is significant disagreement, as well, about the exact nature of the envisionment process. The main issue is the means for describing continuously variable parameters. DeKleer [6,7] describes changing parameters according to the sign of the derivative (the 3IQ value*, standing for 3Incremental Qualitative value*), and an algebra for propagating IQ values across addition constraints. Forbus [11] observes that IQ values alone are inadequate for more than incremental perturbation analysis, and expands the description to include the signs and magnitudes of both the amount and the derivative of a parameter. In practice, his system uses only the ordinal relations among quantities belonging to partially ordered 3quantity spaces*, rather than performing arithmetic operations on numerical magnitudes. Hayes [16,17] initially proposed the concept of a quantity space, but his efforts were directed toward developing an adequate ontology for causality involving liquids, and he did not use the quantity space in a significant way in his examples, remaining agnostic about its properties. Thus, there is a recognized need for a qualitative method for reasoning about quantities without losing the fine distinctions needed in particular applications. Another important issue, not fully addressed by previous proposals, is the ability of the envisionment to detect previously unsuspected points at which qualitatively significant changes take place. Forbus [11] and Hayes [16] both assume that landmark values indicating qualitatively significant changes are provided as part of the initial description of the situation. De Kleer's "roller coaster" envisionment [6] usually makes the same assumption, although it is able to posit a change taking place within an interval if the roller coaster's behavior is different at the two ends. However, the point at which the change takes place is not then introduced into the envisionment for further qualitative reasoning. Determining where that point is, and what its properties are, is passed off to the quantitative reasoning component. As we shall see in section 5 below, the envisionment process proposed here is able to detect a previously unsuspected point at which qualitatively significant changes occur and determine many of its properties, without going beyond qualitative reasoning. A number of researchers are developing methods for deriving behavior from structure in digital electronics, for the purpose of circuit verification (Barrow [1]) or fault diagnosis (Davis [4,5], Genesereth [14]). Because of the discrete nature of the parameter values, digital electronics is a significantly different domain from physical systems characterized by continuous, analog parameters. In particular, although the simulation of the device may be symbolic [1], the precise values of the parameters can be described and used, so the simulation is not, strictly speaking, qualitative. Furthermore, current work has studied the propagation of information to establish a coherent state for the circuit at a single instant in time. These reasoning techniques do not address (yet) the 3evolution* of the state of a circuit over time. Finally, as we shall see below, there is a relatively small set of possible constraints that may hold among parameters in an analog system, and relatively few ways that a set of changing parameters can change over time. In digital electronics, on the other hand, the constraints that can hold among parameters, and the way future states can depend on the past, are limited only by the set of available or constructible component types. Thus, many of the important issues in deriving behavior from structure will be different in the two domains. .bp 1Section 3: Two Other Ways To Reason About Physical Systems* We can develop certain aspects of our qualitative reasoning method by comparison with other formal reasoning methods using differential equations. Physical scientists reason about physical systems by describing the structure of a system with a differential equation, then determining its behavior by solving the equation, either analytically or by numerical simulation. The solution can then be analyzed to detect previously-unsuspected landmark values of the system's parameters where its behavior changes qualitatively: zero-crossings, maximum or minimum values, and inflection points. Perturbation analysis of the system in the neighborhood of such a point can reveal the existence of (e.g.) a stable equilibrium. There are two costs to using such a reasoning method: the computational resources to perform its primitive operations, and an interpretation process to construct a meaningful description from its output. Consider an example of a simple physical system (figure 2) consisting of a closed container of gas (at temperature 2T*) receiving heat from a source (at 2Ts*). .diag .sp 3i .fi 1Figure 20: A container of gas (at temperature 2T*) receiving heat from a source (at a constant temperature 2Ts*). There is no heat loss. The rate of flow of heat into the gas (2inflow*) is a function of the difference (2A2*T = Ts - T*) between the two temperatures, with 2A2*T = 0* corresponding to 2inflow = 0*. .ediag A commonsense description of the behavior of this system is 3"The temperature of the gas increases until it is equal to the temperature of the source."* Our goal is a causal reasoner which can produce a description of this form from a description of the causally-relevant structure of the system. A numerical simulation [13] of this system requires a complete description, in that the value of each parameter at each point in time must be given as a real number. The relationship between A22T0 and 2inflow* must also be specified precisely, so we assume strict proportionality with a numerically specified constant. The simulation algorithm is conceptually simple, computing the values of all parameters at a time-point from their values in the previous time-point. It does, however, require arithmetic operations on real numbers, which are more than we might be willing to assume as primitive operations in the human. Figure 3 below gives the structural and behavioral description of the simple heat-flow system, as appropriate for numerical simulation. .bp .diag The structural description:  A2*T = Ts - T  inflow = div(A2*T 10)  div(d dt)T = inflow The behavioral description produced by numerical simulation: .fs 2 t 1 2 3 4 T 300 370 433 490 Ts 1000 1000 1000 1000 etc. A2*T 700 630 567 510 inflow 70 63 57 51 .fi .fs 0 1Figure 30: The structural and behavioral description of the simple heat-flow system for numerical simulation. The behavior of the system is described in terms of a discrete set of time-points, each of which specifies the numerical values for the system's parameters. .ediag The output of the numerical simulation requires substantial further interpretation to recognize and classify important events in the behavior of the system. There is no information about the nature of the dependencies between the different parameters, or how the outcome might vary for different values of the numerical parameters. The fundamental problem is that the numerical description required for this type of simulation has very few states of partial knowledge: either the value of a parameter is known or it is not. The simulation process cannot run without complete knowledge, and its output can only be matched to a numerically identical system. The analytic solution of a differential equation provides a substantially different description of the system. In order to describe the causal structure of the simple heat-flow system (figure 2) as a differential equation we must specify the relationship between 2inflow* and A22T0 explicitly, in this case as a strict proportionality, but with a symbolic constant k. It can then be solved analytically as follows. .bp .diag  div(d dt) T = inflow = k A2*T = k(Ts - T)  CS*div("dT" "Ts - T") = CS*k dt  ln(Ts - T) = -kt + C  Ts - T = C'e-kt  T = Ts - C'e-kt .fi 1Figure 40: The first equation is the structural description of the simple heat-flow system (figure 2), and the final equation is its behavioral description, created by solving the differential equation analytically. .ediag The language of differential equations provides very useful states of partial knowledge about the system, in that quantities may be represented symbolically instead of as real values. There is also a very rich symbolic vocabulary of relationships that may be asserted between quantities in formulating the problem or describing the solution: the arithmetic operators, the trigonometric functions, logarithm, exponentiation, and many others. While these properties make differential equations the fundamental descriptive tool of the physical sciences, they cannot be solved analytically by humans without external memory resources. In spite of this descriptive power, the analytic solution of differential equations requires global and knowledge-intensive operations such as indefinite integration. We have seen two quite distinct treatments of continuously-varying parameters in these two representations. One treats quantities as real numbers, revealing their changes in the course of incremental simulation, but requires a sophisticated interpretation to derive an understanding of the behavior of the mechanism given the simulation. The other representation treats parameters as real-valued continuous functions, and yields an easily interpretable solution, but requires a sophisticated mathematical inference method which often fails to produce a closed-form solution. Qualitative reasoning about physical systems must be able to handle states of incomplete knowledge such as weakly specified functional relationships, and non-numerical initial parameter values. As a form of human commonsense reasoning, it must also require only modest computational facilities [18], but must still be able to handle systems without closed-form solutions, and must be able to recognize unexpected points of qualitative change. .bp 1Section 4: Qualitative Simulation With Ordinal Quantities0 The qualitative simulation, like the other formal models, begins with a structural description which consists of a set of constraints holding among time-varying, real-valued parameters. The three principal types of constraints are: .inset 1Arithmetic*: (2X = Y + Z*.) The values of the parameters must have the indicated relationship at each point in time. 1Functional*: (2Y = M+(X)*.) Y is a strictly increasing function of X (decreasing if 2M-*). 2Msubsup(z +)* and 2Msubsup(z -)* pass through the origin as well. 1Derivative*: (2Y = div(d dt) X*.) At each time-point, Y is the rate of change of X. .outset The functional relationship, in particular, provides a weaker level of description than is possible with numerical or analytic solutions of differential equations. The relationship 2inflow = Msubsup(z +)(A2*T)* in figure 5 states only that the relationship is strictly monotonically increasing, and that 2inflow = 0* corresponds to 2A2*T@=@0*. Figure 5 gives the qualitative structure description for the simple heat flow system in figure 2. .diag .in 42 .fs 2 (defnet heat-flow (unit (temp t-in t-s delta-t) (heat inflow)) (constant (t-s (*range* 0 nil))) (constraint (adder add A t-in B delta-t C t-s) (m0+ foo X delta-t Y inflow) (d//dt deriv RATE inflow X t-in)) (initialize (lt t-in t-s))) .in 4 .fs 0 .fi 1Figure 5*. The qualitative causal structure description for the simple heat-flow system (figure 2). Note that the 2Msubsup(z +)* constraint is a strictly weaker description of the functional relationship than was required for numerical simulation or analytic solution. The 2defnet* form on the right is the actual internal form of the structure description. .ediag The problem we observed in the last section with numerical simulation and analytic solutions of differential equations lies in the restricted states of partial knowledge and in the excessively powerful computational machinery required. In order for qualitative reasoning about physical causality to have more states of partial knowledge with a weaker set of primitive relations, it must operate, not on real numbers, but on symbolic 3descriptions* of real numbers and the relations among them. The behavioral description consists of a finite set of 3time-points* representing the qualitatively distinct states of the system, and 3values* for each parameter at each time-point. A 3value* is a description of the real number corresponding to a parameter at a particular time-point. This description consists of the 3ordinal relations* (i.e. 2>*, 2<*, and 2=*) holding among the different values in the behavioral description, and the 3IQ value* (stated as 3increasing*, 3steady*, or 3decreasing*) of the parameter at that time. Certain values are distinguished or 3landmark* values which play a special role in the qualitative simulation. Table 1 summarizes the terminology of this model of qualitative causal reasoning. .bp .diag .fi .fs 0 The representation for causal knowledge consists of the following objects. They are described here in terms of the real values and real-valued functions for which they provide a partial description. 1Parameter:* a term corresponding to a continuous real-valued function of time. 1Switch:* a term corresponding to a boolean-valued function of time. 1Value:* a term corresponding to a real number, the value of a Parameter at a particular point in time. A 1Landmark Value* is a specially designated value. 1Boolean:* a term corresponding to the boolean value of a Switch at a particular point in time. 1Time-Point:* a Value of the special Parameter, 1Time*. 1IQ Value:* a term corresponding to the sign of the derivative of a Parameter at a particular point in time. It may have one of three values: increasing (3inc*), steady (3std*), or decreasing (3dec*). 1Assertion:* one of the predicates describing the relation between two Values, or between a Value and the IQ Value at the same time. The reasoning system acquires knowledge about the magnitudes of quantities by inferring new assertions. 1Ordinal*: ( ); ::= gt | eql | lt 1IQ*: (IQ ); ::= inc | std | dec 1Constant*: (constant ) 1Value Space:* the set of values, partially ordered by the transitive closure of the ordinal assertions. Its primary use is to retrieve the next landmark value in a given direction from a given value. 1Correspondence:* an alist of (parameter landmark-value) pairs consisting of all the parameters at a particular time-point whose values are equal to landmark values. 1Constraint:* one of five types of predicate describing the relationship between several Parameters and Switches. A set of Parameters, Switches, and Constraints constitutes the structural description of a mechanism, whose behavioral description is determined by examining the Assertions generated through qualitative simulation. 1Arithmetic:* ( ) [+ *] 1Functional:* ( ) [M+ M- Msubsup(z +) Msubsup(z -)] 1Derivative:* ( ) [div(d dt)] 1Inequality:* ( ) [= <> < > <= >=] 1Conditional:* ( ) 1Table 1.* The objects and relations in the qualitative causal reasoning representation. Appendix A provides a more formal definition. Appendix B contains the rules by which individual constraints propagate ordinal and IQ value assertions. .ediag .bp Beginning with a set of assertions about the initial state of the system, the envisionment process takes place through the 3propagation/prediction cycle*. .inset 1Propagation*. The consequences of information known about the state of the mechanism at the current time-point are propagated through the constraints to create a more complete qualitative description. The current time-point is complete when the direction of change for each value is known. Appendix B provides the detailed specification of the propagation rules. 1Prediction*. The configuration of changing values is examined to determine what can be inferred about the next qualitatively distinct state of the mechanism. A new time-point is defined (or three in case of a branch) and those conclusions asserted within its context. Appendix C provides the detailed specificiation of the prediction rules. .outset The prediction rules for determining the next qualitatively-distinct state are elaborations on the following three types of qualitative changes, which depend on the ordinal relationship between the current value of a parameter and nearby landmark values. .inset 1Move From Landmark Value*: If the current value of a changing parameter is equal to a landmark value, then let the next value be perturbed in the direction of change, closer to the starting point than any other landmark value. 1Move To Limit*: If the current value of a changing parameter is not equal to a landmark value, and there is a landmark value in the direction of change, let the value of that parameter in the next time-point be equal to the next landmark value. 1Collision*: If there are two changing values moving toward each other, not equal to landmark values nor separated by a landmark value, let their next values be equal, and make that new value a landmark. .outset Figure 6 demonstrates these rules graphically. .bp .diag .fs 2 -+-> ----------------0---------------0---------------- results in + ----------------0---------------0---------------- Move-To-Limit -+-> ----------------0---------------0---------------- results in + ----------------0---------------0---------------- Move-From-Landmark-Value -+-> <-+- ----------------0---------------0---------------- results in + ----------------0---------------0---------------- Collision .fs 0 .fi 1Figure 6*. A graphical illustration of three of the simple prediction rules. The actual set of rules is considerably more complex because there are frequently more than one or two changing values. .ediag When the description of the system's current state is not sufficiently complete to determine the next state uniquely, the envisionment branches on the possible states of a particular IQ value or ordinal relation. An additional set of recognition rules (Appendix C) detect properties of the behavioral description, such as cycles, case joins, and quiescence. Figure 7 demonstrates that the result of the qualitative simulation is a two-state envisionment that corresponds closely with the commonsense description of the simple heat-flow system: "3The temperature of the gas increases until it is equal to the temperature of the source*." The qualitative structural and behavioral descriptions offer simplicity of mechanism, in that the qualitative simulation process depends on the ability to create and match simple assertions, rather than on arithmetic operations or symbolic integration. They also offer the ability to represent partial knowledge, in that both values and functional relationships are only constrained to lie in qualitatively defined classes. Both simplicity of mechanism and states of partial knowledge are valuable properties of a commonsense knowledge representation. .diag .fs 2 constant(Ts) ================================ (1) T < Ts A2*T > 0 inflow > 0 increasing(T) decreasing(A2*T) decreasing(inflow) ================================ (2) T = Ts A2*T = 0 inflow = 0 steady(T) steady(A2*T) steady(inflow) ================================ .fi .fs 0 1Figure 70: The envisionment produced by qualitative simulation. * Initial conditions are 2constant(Ts)* and 2T < Ts*. * In time-point (1), the addition constraint propagates 2T < Ts* => 2A2*T > 0*. * The functional constraint propagates 2A2*T > 0* => 2inflow > 0*. * The derivative constraint yields 2inflow > 0* => 2increasing(T)*. * The IQ values propagate similarly to complete the description of time-point (1). * A version of the Move-To-Limit rule determines that 2T*, 2A2*T*, and 2inflow* are all changing toward landmark values, and that they must reach their limits simultaneously. * Time-point (2) is created with the initial assertions 2T = Ts*, 2A2*T = 0*, and 2inflow = 0*. * The constraints propagate ordinal assertions and IQ values until the description of time-point (2) is complete. * Since all IQ values are 2steady*, the system is quiescent. * "3The temperature of the gas increases until it is equal to the temperature of the source*." .ediag The next example shows that the qualitative simulation can also provide an essential property of a description of physical causality: the ability to detect previously unsuspected values at which qualitatively significant changes take place. .bp 1Section 5: Detecting and Establishing a Stable Equilibrium0 We have seen that the qualitative simulation process can handle a simple heat-flow problem like the one above, where the system reaches an equilibrium at a previously-known landmark value. However, one important product of causal reasoning about a physical system is the existence of previously unsuspected values at which qualitatively significant changes take place. We can explore this issue in the context of a more realistic heat-flow problem, where there are flows of heat both into the gas from the source, and away from the gas into the surrounding cooler air. The causal structure description of the double heat-flow system (figure 8) is constructed by merging two descriptions of simple heat-flows. The problem is to deduce the existence of an equilibrium temperature (2Te*) between the temperatures of the heat source (2Ts*) and the air (2Ta*), and to show that the system moves to a stable equilibrium about that temperature. .diag .sp 3.5i .fi 1Figure 80: The causal structure description of the container of gas with two heat-flows. .ediag .bp This description is a qualitative version of the differential equation  div(d dt)T = k(Ts - T) - k'(T - Ta) .br whose solution is  T = div("kTs + k'Ta" "k+k'") - C'e-(k+k')t. .br A commonsense description of the behavior of this system is "3The temperature of the gas moves to a temperature between the temperature of the air and that of the source, and remains steady*." The envisionment process attempts to produce a complete description of the system's behavior through time. As we shall see, it first propagates newly discovered information through the constraints to complete the description of the system at a given time-point. Once that description is sufficiently complete, the envisionment process examines the set of currently changing values to determine the next qualitatively distinct state. If the description of the current state is not sufficiently well specified to determine the next state uniquely, the behavioral description branches according to the three possible states of an unspecified IQ value or ordinal relation. If the alternating cycle of sprouting a new time-point and propagating information among its values should become bogged down in intractible branching, the causal structure description may be summarized and simplified (cf. Figure 10 and Appendix D). The new description is less constrained, hence weaker than the old one, but by being simpler it may avoid branching and allow the envisionment process to continue. The envisionment process continues to simulate the system until some terminating condition is detected: quiescence, a cycle, a contradiction, or intractible branching. The set of values in the behavioral description, partially ordered by the ordinal assertions that are currently known, is called the 3value space*. The prediction rules that determine the next state of the system give special status to landmark values. The prediction rules consider only the subset of the value space consisting of the current values plus the landmark values. Initially, zero is the only landmark value; the current value of a parameter becomes a landmark when that value has an IQ value of 2steady*. Figures 9, 10 and 11 show the stages of the qualitative simulation .foot The envisionment diagrams (figures 9 and 11) are read from top to bottom, each line following from those above. Each cell contains assertions relevant to a single time-point. Time progresses from top to bottom, and alternate branches are side by side. .efoot as it creates the envisionment. Figure 9 shows how the envisionment of the double-flow system branches in order to derive missing IQ values, how a new landmark point is discovered on one of the branches, and how a set of corresponding values is recorded when several parameters take on landmark values simultaneously. Figure 10 shows how the structural description is summarized when the first envisionment bogs down at an intractible branch, creating a much more manageable structural description which, though containing much less information, is still a valid description of the system. Figure 11 shows how the summarized structural description, and the newly-discovered correspondence, allow the successor time-points on the remaining two branches to be determined uniquely so the envisionment can be completed. Diagnosis of a stable equilibrium takes place using the final envisionment structure, by showing that a perturbation from the final quiescent state places the system into one of the previously described states from which there is a restoring change. .bp .fs 2 .diag .ta 28 52 constant(Ta) constant(Ts) ===================================================================== (1) Ta < T < Ts A2*Ta > 0 A2*Ts > 0 outflow > 0 inflow > 0 net flow = unknown --------------------------------------------------------------------- Case Split: relation(net flow, 0) --------------------------------------------------------------------- (1G) |(1L) |(1E) net flow > 0 | net flow < 0 | net flow = 0 inflow > outflow > 0 | 0 < inflow < outflow | inflow = outflow > 0 Ta < T < Ts | Ta < T < Ts | Ta < T < Ts A2*Ta, A2*Ts > 0 | A2*Ta, A2*Ts > 0 | A2*Ta, A2*Ts > 0 increasing(T) | decreasing(T) | steady(T) increasing(A2*Ta) | decreasing(A2*Ta) | steady(A2*Ta) increasing(outflow) | increasing(outflow) | steady(outflow) decreasing(A2*Ts) | increasing(A2*Ts) | steady(A2*Ts) decreasing(inflow) | increasing(inflow) | steady(inflow) decreasing(net flow) | increasing(net flow) | steady(net flow) | | ========================|=======================|==================== | | .fi .fs 0 1Figure 90. Envisionment of the double heat-flow system. * In time-point 2(1)*, starting with the condition that 2Ta < T < Ts*, ordinal assertions propagate through the network, producing the succeeding facts, but failing to provide information about 2net flow*. * In order to allow the derivative constraint to derive IQ values, the envisionment is split into cases according to the sign of 2net flow*. In the branches, with 2net flow* specified, IQ values propagate through the network to complete the description. * Time-point 2(1E)* is quiescent, with all IQ values 2steady*, so new landmark values are created, and the correspondence between parameters taking on landmark values is recorded. 2(net flow: 0) <=> (inflow: flow*) <=> (outflow: flow*) <=> (A2*Ta: A2*Ta*) <=> (A2*Ts: A2*Ts*) <=> (T: Te)* * Time-points 2(1G)* and 2(1L)* each contain 3six* changing values. However, not enough is known to show that they arrive at their limits simultaneously, making the required case split intractibly large, so the envisionment halts. .ediag .ta 8 16 24 32 40 48 56 64 72 80 88 96 104 112 120 .bp .diag .sp 6.5i .fi 1Figure 100: The arithmetic and functional parts of the causal structure description are simplified in three steps, applying the following simplification rules. (See Appendix D.) The rules are applied repeatedly until the structural description can not be simplified further. .fs 4 x + y = z & constant(y) => z = M+(x) x + y = z & constant(z) => y = M-(x) y = M+(M+(x)) => y = M+(x) y = M-(M+(x)) => y = M-(x) y = M-(x) - M+(x) => y = M-(x) .ediag .bp .diag .fs 2 (T: Te) <=> (net flow: 0) ===================================================================== (1) Ta < Te < Ts Ta < T < Ts net flow = unknown --------------------------------------------------------------------- Case Split: relation(net flow, 0) --------------------------------------------------------------------- (1G) |(1L) |(1E) net flow > 0 | net flow < 0 | net flow = 0 Ta < T < Te | Te < T < Ts | T = Te increasing(T) | decreasing(T) | steady(T) decreasing(net flow) | increasing(net flow) | steady(net flow) | | ========================|=======================|==================== (2G) |(2L) |(2E) T = Te | T = Te | T = Te net flow = 0 | net flow = 0 | net flow = 0 steady(T) | steady(T) | steady(T) steady(net flow) | steady(net flow) | steady(net flow) | | ========================|=======================|==================== --------------------------------------------------------------------- Case join: identical outcomes on all branches --------------------------------------------------------------------- (2) net flow = 0 T = Te steady(T) steady(net flow) ===================================================================== .fi .fs 0 1Figure 110. Envisionment of the summarized double heat-flow description. * In time-point 2(1)*, ordinal assertions propagate as before, and the need for IQ values prompts a case split. * Time-point 2(1E)* is quiescent as before. * The previously-determined correspondence makes it possible to infer the relation between 2T* and 2Te* in time-points 2(1G)* and 2(1L)*. * Since time-points 2(1G)* and 2(1L)* each contain only two changing parameters and their limits are known to correspond, their subsequent states, 2(2G)* and 2(2L)*, are easily and unambiguously determined by the Move-To-Limit rule. * Since the three branches of the split have identical end states, they are joined to create state 2(2)*. The quiescent state 2(1E)* is copied to an identical but temporally later state 2(2E)* so that the temporal relation between states 2(1)* and 2(2)* is well defined. .ediag .bp The envisionment structure, or behavioral description, is now complete, since each state with changing values has a well-defined successor. The overall structure of the envisionment is shown below. Since the envisionment structure has only eight states, it is feasible to examine it for global properties such as the nature of its equilibrium. .diag .fs 2 \ weaker ---------(1) (2)---------- | description /|\ /|\ / / | \ / | \ / | \ / | \ / | (1E)--(2E) | \ \ / | | \ | stronger / (1L)------------(2L) \ | descriptions / \ | (1G)--------------------------(2G) / .fi .fs 0 1Figure 120. The qualitative description of behavior is sufficiently compact that it can be examined for global properties such as stable equilibrium. .ediag Since the system ends in a quiescent state, a set of recognition rules are applied to determine whether the quiescence can be diagnosed as some type of equilibrium. Perturbations from state 2(2)* put the system into states 2(1G)* or 2(1L)*, from which they return to 2(2)*, so the system is in stable equilibrium. It is worth noting that almost the same conclusion would have been reached if the double heat-flow structure (figure 8) had been simplified immediately, without the initial envisionment. The reader may find it instructive to work through the envisionment in figure 11 without the correspondence given ahead of time. The more complete description is required, however, to show that 2Ta < Te < Ts*, if it is not initially assumed. Furthermore, there is no reason, before doing the initial simulation, for the envisionment process to transform a stronger description into a weaker (though simpler) one. .bp 1Section 6: On the Qualitative Description of Time* A mechanism changes continuously with time. Thus, there is no "next" instant after the current one. The qualitative simulation we use here, however, consists of a discrete set of time-points, and we frequently speak of the prediction phase as predicting the "next qualitatively distinct state" of the system. Consider the example of a ball thrown into the air with velocity 2v0 > 0* at time 2t = 0*. The ball passes through a continuum of states during its journey up, then down again. However, these states are mapped into five distinct qualitative state descriptions. .diag The quantitative structure description: 2div(d dt)y = v, div(d dt)v = a = -32 ft/sec2.* The quantitative behavior description: 2v(0) = 32 ft/sec => y(t) = -16t2 + 32t ft.* 2y(0) = 0 ft* The qualitative structure description: 2div(d dt)y = v, div(d dt)v = a < 0.* The qualitative behavior description: .fs 2 .ta .75i 1.5i 2.75i 4i 5.25i (0) (1) (2) (3) (4) Y Y0 = 0 0 < Y1 < YMAX Y2 = YMAX 0 < Y3 < YMAX Y4 = 0 V V0 > 0 0 < V1 < V0 V2 = 0 V3 < 0 V4 < V3 < 0 A A0 < 0 A1 < 0 A2 < 0 A3 < 0 A4 < 0 .fi .fs 0 .ta 8 16 24 32 40 48 56 64 72 80 88 96 104 1Figure 13*. The structural and functional descriptions of the ball system, described both quantitatively and qualitatively. For all 2t* in the open interval 20 < t < 1*, the quantitative descriptions are mapped into the same qualitative description (State 2(1)*). Thus state 2(1)* is the next qualitatively distinct state description after state 2(0)*, even though there is clearly no "next" value of 2t* after 2t = 0*. .ediag Each time-point in the sequence produced by the qualitative simulation corresponds to either a point or an open interval in physical time. In the open-interval case, the physical system clearly continues to change, but within the scope of the same qualitative state description. .bp 1Section 7: Individual Variation.* Individual variation is an important characteristic of commonsense knowledge (cf. McCloskey, Carramazza, and Green [23]). An individual might have the structural description shown below (figure 14) for the single heat-flow system. The qualitative simulation is similar to that in figure 7, in that it matches the commonsense description, "3The temperature of the gas increases until it is equal to the temperature of the source*." The structural description is correct, but is at the wrong level of detail to support productive causal reasoning because it does not include the fact that the difference between the temperatures of the gas and the source controls the rate of heat increase. This structural description could not be generalized to produce a reasonable envisionment of the double heat-flow example. .diag .in 3.5i .fs 2 rate > 0 ================================ (1) T < Ts Q = true IQ(T) = inc ================================ (2) T = Ts Q = false IQ(T) = std ================================ .fs 0 .in 4 .fi 1Figure 14*: An alternate causal structure description of the single heat-flow, and the corresponding behavioral description. Although the behavioral description is effectively the same as that in figure 7, the structure description does not generalize to handle the double heat-flow situation. .ediag We may speculate that some physics students learn models of physical phenomena such as the above which are accurately predictive for a certain class of simple mechanisms, but lead to intractible or incoherent structural descriptions when generalized. The Repair Theory approach of Brown and Van Lehn [2], applied to the composition of simple mechanism descriptions to produce more complex ones, may illuminate the misconceptions of naive physics students [15]. .bp 1Section 8: Conclusion* This paper is concerned with the qualitative simulation of physical systems whose descriptions are stated in terms of continuously varying parameters. These continuous systems are interesting because they pose unsolved problems in the representation of knowledge, and because they appear fundamental to commonsense knowledge of causality in the physical world. There appears to be a "cluster" of knowledge of manageable size about the possible interactions among continuously changing parameters which we can hope to capture and represent [16]. The examples presented above demonstrate a representation for qualitative reasoning about causality in physical mechanisms. The system as described in this paper has been completely implemented in Maclisp. The structural description is essentially a qualitative form of a differential equation, specifying a set of parameters which characterize the state of the mechanism and a set of constraints holding among the parameters. Qualitative simulation produces a behavioral description which specifies the ordinal relationships and directions of change of the parameter values at each point in time. Just as differential equations do not provide a theory of physics, but rather a language for stating theories of physics, the work presented here is a "qualitative mathematics" intended as a language for stating theories of qualitative reasoning about particular mechanisms [9]. The preceding discussion of individual variation illustrates this point. Qualitative simulation of behavior from structure is a key element in a complete theory of "naive physics." Other critical elements include specifying 3which* knowledge to represent to capture the properties of particular domains [17,21], and specifying how the right structural descriptions can be evoked to handle particular physical situations [11,12]. Future directions for research on these "qualitative differential equations" include a mathematical exploration of their properties and the correctness of the qualitative simulation algorithm (cf. figure 1), a reformulation of the prediction rules (appendix C), and an extension to the formalism to allow time to be treated as a structural, as well as a behavioral, parameter. .bp  1Acknowledgements* .ls 1 Christopher Eliot is responsible for the implementation of this system, and has made substantial contributions to its design. Ken Church, Ken Forbus, Ramesh Patil, and Peter Szolovits have also provided helpful comments. 1References0 [1] H. Barrow. 1983. Proving the correctness of digital hardware designs. In 3Proceedings of the National Conference on Artificial Intelligence (AAAI-83)*. [2] J. S. Brown and K. Van Lehn. 1980. Repair theory: a generative theory of bugs in procedural skills. 3Cognitive Science 4(4)*. [3] M. T. H. Chi, P. J. Feltovich, and R. Glaser. 1982. Categorization and representation of physics problems by experts and novices. 3Cognitive Science 5*: 121-152. [4] R. Davis, H. Shrobe, W. Hamscher, K. Wieckert, M. Shirley, and S. Polit. 1982. Diagnosis based on description of structure and function. In 3Proceedings of the National Conference on Artificial Intelligence (AAAI-82)*. [5] R. Davis. 1983. Diagnosis via causal reasoning: paths of interaction and the locality principle. In 3Proceedings of the National Conference on Artificial Intelligence (AAAI-83)*. [6] J. de Kleer. 1977. Multiple representations of knowledge in a mechanics problem-solver. 3Proceedings of the Fifth International Joint Conference on Artificial Intelligence*. Cambridge, Mass. [7] J. de Kleer. 1979. The origin and resolution of ambiguities in causal arguments. 3Proceedings of the Sixth International Joint Conference on Artificial Intelligence*. Tokyo, Japan. [8] J. de Kleer and J. S. Brown. 1981. Mental Models of Physical Mechanisms and their Acquisition. In J. R. Anderson (Ed.), 3Cognitive Skills and Their Acquisition0, Hillsdale, NJ: Erlbaum. [9] J. De Kleer and J. S. Brown. 1983. The origin, form and logic of qualitative physical laws. In 3Proceedings of the Eighth International Joint Conference on Artificial Intelligence (IJCAI-83)*. [10] C. Eliot and B. Kuipers. 3ENV Manual*. In preparation. [11] K. D. Forbus. 1981. Qualitative reasoning about physical processes. 3Proceedings of the Seventh International Joint Conference on Artificial Intelligence*. Vancouver, B.C. [12] K. D. Forbus. 1982. Qualitative Process Theory. Cambridge, MA: MIT Artificial Intelligence Laboratory Memo 664. [13] J. Forrester. 1969. 3Urban Dynamics*. Cambridge, MA: MIT Press. [14] M. R. Genesereth. 1982. Diagnosis using hierarchical design models. In 3Proceedings of the National Conference on Artificial Intelligence (AAAI-82)*. [15] D. Gentner and A. Stevens (Eds.). 1983. 3Mental Models*. Hillsdale, NJ: Erlbaum. [16] P. J. Hayes. 1979. The Naive Physics Manifesto. In D. Michie (Ed.), 3Expert Systems in the Micro Electronic Age*. Edinburgh: Edinburgh University Press, 1979. [17] P. J. Hayes. 1978. Naive physics I: Ontology for liquids. Department of Computer Science, University of Essex. [18] B. Kuipers. 1979. On representing commonsense knowledge. In N. V. Findler (Ed.), 3Associative networks: The representation and use of knowledge by computers.0 New York: Academic Press, 1979. [19] B. Kuipers. 1981. De Kleer and Brown's "Mental Models": A Critique. Tufts University Working Papers in Cognitive Science, No. 17. Medford, MA. [20] B. Kuipers and J. P. Kassirer. Causal reasoning in medicine: Analysis of a protocol. To appear in 3Cognitive Science*. [21] B. J. Kuipers. 1983. Programs that understand how the body works. To appear in the 3Proceedings of the Second IEEE Computer Society International Conference and 1983 Stocker Symposium on Medical Computer Science and Computational Medicine (MEDCOMP '83)*. Athens County, Ohio, September 1983. [22] J. Larkin, J. McDermott, D. P. Simon, H. A. Simon. 1980. Expert and novice performance in solving physics problems. 3Science 2080: 1335-1342. [23] M. McCloskey, A. Caramazza, & B. Green. 1980. Curvilinear motion in the absence of external forces: naive beliefs about the motion of objects. 3Science 2100: 1139-1141. [24] D. McDermott. 1982. A temporal logic for reasoning about processes and plans. 3Cognitive Science 6*: 101-155. [25] C. Rieger and M. Grinberg. 1977. The declarative representation and procedural simulation of causality in physical mechanisms. 3Proceedings of the Fifth International Joint Conference on Artificial Intelligence*, Cambridge, MA. [26] G. L. Steele, Jr. 1980. The definition and implementation of a computer programming language based on constraints. Cambridge, MA: MIT Artificial Intelligence Laboratory TR-595. [27] S. M. Weiss, C. A. Kulikowski, S. Amarel, and A. Safir. 1978. A model-based method for computer-aided medical decision-making. 3Artificial Intelligence 110: 145-172. .bp .fi .fs 4 ‹ Gacha8 .ls 1 1Appendix A: A Formal Definition of the Causal Representation.* 5Def.* A 5parameter* is a symbol denoting a continuously differentiable real-valued function of time. (pi: AR* --> AR*) 5Def.* A 5constraint* is a pair consisting of: (1) a set P of parameters, (2) a set A of axioms stating relationships between the values and IQ-values of the parameters in P. (See Appendix B.) 5Def.* A 5structural description* is a 4-tuple consisting of: (1) a set P of parameters, (2) a set U of subsets of P, called 5units*, partitioning P into mutually exclusive subsets; (3) a set C of constraints, holding among the parameters in P. (4) a set A of axioms stating additional, situation-specific relationships between the values and IQ-values of the parameters in P. (e.g. constant(p) => (for-all (t) (IQ-value(p,t) = steady))) 5Def.* A 5time-point* is a symbol denoting a real number in the domain of some parameter. 5Def.* A 5value* is a symbol denoting a real number in the range of some parameter. 5Def.* An 5IQ-value* is one of the three symbols {increasing, steady, decreasing}, denoting the sign of the derivative of a parameter at a particular time-point. 5Def.* Two landmark values di and dj are 5corresponding values* if there is some time-point t and two parameters pi and pj related by a monotonic function constraint, such that val(pi,t)=di and val(pj,t)=dj. 5Def.* An 5envisionment* is a 7-tuple consisting of: (1) a structural description SD; (2) a set T of time-points, with a subset T* designated as 5active* time-points, (3) a set V of values, with a mapping val: P x T --> V which is a 1-1 correspondence, (4) a subset D of V called the 5landmark values*; (5) an order relation R on the elements of V which is a total order when restricted to the landmark values D in a given unit Ui plus any other value corresponding to a parameter in Ui; (6) a partial mapping IQ: P x T --> {increasing, steady, decreasing}, which assigns to each parameter at each time the sign of the derivative of its parameter at that time. (7) a set Corr of subsets of D denoting corresponding values. 5Def.* An 5envisionment process* is a sequence E0 . . . En of envisionments, where (1) E0 consists of a structural description SD but the sets T, V, D, R, IQ, and Corr are empty; (2) Ek+1 is derived from Ek by selecting an active time-point from Ek, and applying the rules in appendix C below to that time-point to determine 1 (or 3 in the case of a branch) successor time-points which are added to T, along with a corresponding set of values to V, and possibly additional information to D, R, IQ-value, and Corr. (3) None of the rules below apply to the final state En. .bp 1Appendix B: Definition of the Constraints.* 0Constraints are relationships among parameters, but assert ordinal relations and IQ values among the values associated with those parameters at a given time, and also among the values associated with a single parameter at different times. The rules by which these assertions are created are given below. The constraint propagation mechanism is inspired by the scheme developed by Steele [26], modified to propagate ordinal and IQ value assertions rather than integers.* .nf The 5addition constraint*: A ------|---\ | + |------ C B ------|---/ .fi Ordinal relations can propagate among the values of the adder pins at any given time: A = 0 <=> B = C B = 0 <=> A = C A > 0 <=> B < C A < 0 <=> B > C B > 0 <=> A < C B < 0 <=> A > C The sign of the derivative of A, B, and C at a given time can propagate through the adder. .nf C = A + B B = C - A + IQ(A) inc std dec - IQ(C) inc std dec IQ(B) IQ(A) inc inc inc ? inc ? inc inc std inc std dec std dec std inc dec ? dec dec dec dec dec ? .fi When an inequality is derived between two values taken on by one adder pin at different times, that inequality can be propagated through the adder as well. A1 = A2 & B1 = B2 => C1 = C2 A1 = A2 & B1 > B2 => C1 > C2 A1 = A2 & B1 < B2 => C1 < C2 A1 > A2 & B1 = B2 => C1 > C2 A1 > A2 & B1 > B2 => C1 > C2 A1 < A2 & B1 = B2 => C1 < C2 A1 < A2 & B1 < B2 => C1 < C2 A1 = A2 & C1 = C2 => B1 = B2 A1 = A2 & C1 > C2 => B1 > B2 A1 = A2 & C1 < C2 => B1 < B2 A1 > A2 & C1 = C2 => B1 < B2 A1 > A2 & C1 < C2 => B1 < B2 A1 < A2 & C1 = C2 => B1 > B2 A1 < A2 & C1 > C2 => B1 > B2 .bp .nf The 5multiplication constraint*: |-\ A ------| \ | * >------ C B ------| / |-/ .fi Ordinal relations can propagate among the values of the multiplier pins at any given time: A = 0 => C = 0 B = 0 => C = 0 A > 0 & B > 0 => C > 0 A < 0 & B < 0 => C > 0 A > 0 & B < 0 => C < 0 A < 0 & B > 0 => C < 0 A > 0 & C > 0 => B > 0 A < 0 & C < 0 => B > 0 A > 0 & C < 0 => B < 0 A < 0 & C > 0 => B < 0 [The following rules are only valid assuming A,B,C > 0. However, the only examples of multiplication so far are the calculations of concentration and pressure, which all involve physically positive values.] The sign of the derivative of A, B, and C at a given time can propagate through the multiplier. .nf C = A * B B = C / A * IQ(A) inc std dec / IQ(C) inc std dec IQ(B) IQ(A) inc inc inc ? inc ? inc inc std inc std dec std dec std inc dec ? dec dec dec dec dec ? .fi When an inequality is derived between two values taken on by one multiplier pin at different times, that inequality can be propagated through the multiplier as well. A1 = A2 & B1 = B2 => C1 = C2 A1 = A2 & B1 > B2 => C1 > C2 A1 = A2 & B1 < B2 => C1 < C2 A1 > A2 & B1 = B2 => C1 > C2 A1 > A2 & B1 > B2 => C1 > C2 A1 < A2 & B1 = B2 => C1 < C2 A1 < A2 & B1 < B2 => C1 < C2 A1 = A2 & C1 = C2 => B1 = B2 A1 = A2 & C1 > C2 => B1 > B2 A1 = A2 & C1 < C2 => B1 < B2 A1 > A2 & C1 = C2 => B1 < B2 A1 > A2 & C1 < C2 => B1 < B2 A1 < A2 & C1 = C2 => B1 > B2 A1 < A2 & C1 > C2 => B1 > B2 .bp The 5functional relationship constraints* state that the two parameters so linked have a functional relationship which is either monotonically increasing (M+) or monotonically decreasing (M-), and possibly in which zero corresponds to zero (subscript z). .nf Y is a 5strictly monotonically increasing function* of X: ------ | + | X ----->| M |-----> Y | z | ------ .fi Information about values of X and Y at a given time can only be propagated if the function passes through the origin (subscript z) X > 0 <=> Y > 0 X = 0 <=> Y = 0 X < 0 <=> Y < 0 The sign of the derivative at a given time can also be propagated. IQ(X) = inc <=> IQ(Y) = inc IQ(X) = std <=> IQ(Y) = std IQ(X) = dec <=> IQ(Y) = dec An inequality between values of one of the pins at two different times can be propagated to the other pin. X1 > X2 <=> Y1 > Y2 X1 = X2 <=> Y1 = Y2 X1 < X2 <=> Y1 < Y2 .nf Y is a 5strictly monotonically decreasing function* of X: ------ | - | X ----->| M |-----> Y | | ------ .fi The sign of the derivative at a given time can also be propagated. IQ(X) = inc <=> IQ(Y) = dec IQ(X) = std <=> IQ(Y) = std IQ(X) = dec <=> IQ(Y) = inc An inequality between values of one of the pins at two different times can be propagated to the other pin. X1 > X2 <=> Y1 < Y2 X1 = X2 <=> Y1 = Y2 X1 < X2 <=> Y1 > Y2 .bp The 5derivative constraint* holds between a parameter and a rate. .nf X | | | ------ | d | | -- |<------- R | dt | ------ .fi At any given time, the sign of the rate can be propagated to the sign of the derivative of X. R > 0 <=> IQ(X) = inc R = 0 <=> IQ(X) = std R < 0 <=> IQ(X) = dec 0There are two versions of these rules, named after the classical theories of motion they resemble [23]. The Aristotelian rule has the benefit of simplicity, while the Newtonian rules are more correct. Appendix E presents an example that illustrates the differences in the behavioral description produced.* Aristotelian IQ(X1) = std => X2 = X1 Newtonian IQ(X1) = std & IQ(X2) = std => X2 = X1 IQ(X1) = std & IQ(X2) = inc => X2 > X1 IQ(X1) = std & IQ(X2) = dec => X2 < X1 .bp The 5inequality constraint* holds between two parameters and a switch, so that the switch holds the boolean value corresponding to the truth of the given relationship between the values of the parameters at that time. .nf ------- A -------| | | > |------- cond B -------| | ------- .fi A > B => cond = true A = B => cond = false A < B => cond = false cond = true => A > B The 5conditional constraint* (gate) holds among three parameters, A, B, and C, and a boolean switch, implementing the relationship 6if cond = true then C = A else C = B*. cond | | | -------- A -------| | | GATE |------- C B -------| | -------- cond = true => C = A cond = false => C = B C = A => cond = true C = B & C <> A => cond = false .bp 1Appendix C: The Envisionment Rules* 0The 1Envisionment*, or qualitative simulation of the behavior of a device, proceeds using three types of rules. - 1propagation rules* propagate information across constraints about the values of parameters at a given time-point. - 1prediction rules* determine the nature of the next distinct qualitative state description from what is known about the current state. - 1recognition rules* detect global properties of the envisionment such as cycles, case-joins, and quiescence.* 01Propagation rules* propagate information about the values of parameters at the current time-point according to the relationships among the parameters and constraints describing the structure of the mechanism.* 5Rule P1.* Propagate information (i.e. create a new assertion) for a constraint if enough of its arguments holds new information. (Rules given in Appendix B.) 5Rule P2.* (Make landmark value) If a value's IQ value = steady, make that value a landmark value. 5Rule P3.* (Correspondences) If more than one of the values at the current time-point are landmark values, create a 6correspondence*: an alist of (parameter landmark-value) pairs consisting of all the parameters whose current values are landmarks, and which are linked directly or indirectly by monotonic function constraints. 5Rule P4.* (Contradiction) If propagation derives a contradiction refute the branch containing the value which received the assertion causing the contradiction. If this is the main branch, the entire structural description is at fault. 5Rule P5.* (Branch on undetermined rate) If the IQ value of a parameter is unknown at the current time-point, and if it is the "X" argument of a derivative relation, then branch the envisionment according to the assumptions: IQ(X)=inc; IQ(X)=std; IQ(X)=dec. 0Landmark values are only acquired by being built into the structural description (e.g. the speed limit is 55 mph), or being detected as critical points of functions (Rule P2).* .bp 1Prediction Rules* 0The configuration of changing values (the parameters whose current IQ value is not 2steady*) can be analyzed to select the state or states that immediately succeed the current state. The decision tree below can be seen by inspection to exhaust all cases. The notation specifies only the values of those parameters which are changing; all others are assumed steady. The current value of a parameter is given by a capital letter, followed by its IQ value (direction of change) in parentheses: 4A(inc)* or 4B(dec)*. The value of the same parameter in the time-point created by the envisionment rule is 4A'* or 4B'* respectively. Landmark values are starred; sharing the same letter (4A* and 4A**) simply signifies that 4A** is a landmark value which does or will have some important relationship with 4A*. If the result of an envisionment rule is a branch, the rule is written with multiple arrows ("4=>*") and consequents.* .nf 0. No changing values => no next state. 1. One changing value (A) 1.1 equal to a landmark value: (move from landmark value) [A(inc) = A*] => [A* < A'] 1.2 moving toward a landmark value: (move to limit) [A(inc) < A*] => [A* = A'] 1.3 not moving toward a landmark value: [A(inc)] => [A < A'] (next state will have same description as current state) 2. Two changing values (A and B) 2.1 both equal to landmark values: [A(inc) = A*; B(inc) = B*] => [A* < A'; B* < B'] 2.2 one equal to landmark value: [A(inc) = A*; B(inc)] => [A* < A; B < B'] 2.3 neither equal to landmark values: 2.3.1 A and B in different units: not comparable. 2.3.1.1 neither approaching a limit: [A(inc); B(inc)] => [A < A'; B < B'] 2.3.1.2 one approaching a limit: [A(inc) < A*; B(inc)] => [A* = A'; B < B'] 2.3.1.3 both approaching limits: (non-deterministic move-to-limit) [A(inc) < A*; B(inc) < B*] => [A* = A'; B* = B'] => [A* = A'; B < B' < B*] => [A < A' < A*; B* = B'] 2.3.2 A < B 2.3.2.1 both moving the same way: A(inc) < B(inc) (a) no limits: [A(inc) < B(inc)] => [A' = B'] => [A' < B'] (b) one limit for both values: [A(inc) < B(inc) < L*] => [A' = B' = L*] => [A' < B' = L*] => [B < A' = B' < L*] (c) one limit point between A and B: (= case 2.3.1.2) [A(inc) < A* < B(inc)] => [A' = A* < B < B'] (d) two separate limit points: (= case 2.3.1.3) [A(inc) < A* < B(inc) < B*] => [A* = A' < B* = B'] => [A* = A' < B < B' < B*] => [A < A' < A* < B* = B'] 2.3.2.2 moving toward each other: A(inc) < B(dec) (a) no limits between them: [A(inc) < B(dec)] => [A' = B'] (b) one limit point between them: (= case 2.3.1.3) [A(inc) < L* < B(dec)] => [A' = L* = B'] => [A' = L* < B'] => [A' < L* = B'] (c) two limit points between them: (= case 2.3.1.3) [A(inc) < A* < B* < B(dec)] => [A' = A* < B* = B'] => [A' = A* < B* < B'] => [A' < A* < B* = B'] 2.3.2.3 moving away from each other: A(dec) < B(inc) (a) no limits on either side: [A(dec) < B(inc)] => [A' < A < B < B'] (b) one limit point: (= case 2.3.1.2) [A* < A(dec) < B(inc)] => [A* = A' < B'] (c) a limit point on each side: (= case 2.3.1.3) [A* < A(dec) < B(inc) < B*] => [A* = A' < B' = B*] => [A* = A' < B' < B*] => [A* < A' < B' = B*] 2.3.3 A = B 2.3.3.1 moving same way: [A(inc) = B(inc)] => [A' = B'] => [A' < B'] => [A' > B'] 2.3.3.2 moving opposite ways: [A(dec) = B(inc)] => [A' < B'] 2.3.4 comparable but unknown relationship: (branch on relation; then use cases 2.3.2 and 2.3.3) 3. More than two changing values 3.1 If any changing value is equal to a landmark value or moving in a direction with no limit point, then perturb each value in the direction of motion (see cases 1.1 and 1.3). 3.2 If no changing values are equal to landmark values and some changing values are moving toward limit points and a correspondence exists among all those limit points, then the next values of those changing parameters are equal to their limit points and any changing parameters without limits are perturbed in their direction of change. 3.3 If no changing values are equal to landmark values and some changing values are moving toward limit points and the limit points can be divided into exactly two sets of corresponding values, then branch according to the non-deterministic move-to-limit rule (case 2.3.1.3) and any changing parameters without limits are perturbed in their direction of change. 3.4 Otherwise the current state is declared "Intractible." .fi 0We are currently experimenting with alternate formulations of the prediction rules which may enable us to handle certain cases difficult to express in the decision tree format. Thus the definition of "Intractible" for the envisionment system is likely to change.* .bp .fi 01Recognition rules* recognize global configurations in the envisionment that allow the set of time-points to be simplified.* 5Rule R1*. If all IQ values are steady, then recognize a quiescent system. Remove the current time-point from the set of active time-points. If there are no more active time-points, stop. 5Rule R2*. If all values at the current time-point are equal to landmark values, and all values were equal to the same landmark values at a previous time-point, and all IQ values match in the two time-points, then recognize a cycle. Replace the current time-point with a pointer to the previous, identical, time-point, and remove the current time-point from the set of active time-points, since its successors are now known. 5Rule R3*. If all values at the current time-point are equal to landmark values, and there is a time-point on an alternate branch all of whose values are equal to the same landmark values, and all of the IQ values match, then recognize a case join. Replace both time-points with pointers to a special case-join descriptor. In case the case-join captures all the surviving branches of a case-split, map the join into a new time-point related to the one at which the case-split occurred. (See figure 4 in the text.) .bp .fi 1Appendix D: Summarizing the Structural Description.* 0The syntactic transformation rules for summarizing the causal structure description are the following (in mathematical notation, rather than graph diagrams). They are applied repeatedly until the structural description cannot be simplified further. The transformation is implemented by installing the new constraint, linked with the existing parameters. The existing constraints are left in place but "turned out," so their rules are no longer activated in response to newly asserted values.* 1. Arithmetic constraint with one constant. x + y = z & constant(y) => z = M+(x) x + y = z & constant(z) => y = M-(x) x * y = z & y > 0 & constant(y) => z = M+z(x) x * y = z & z > 0 & constant(z) => y = M-(x) 2. Composition of functional constraints. y = M+(M+(x)) => y = M+(x) y = M+(M-(x)) => y = M-(x) y = M-(M+(x)) => y = M-(x) y = M-(M-(x)) => y = M+(x) y = M+z(M+z(x)) => y = M+z(x) y = M+z(M-z(x)) => y = M-z(x) y = M-z(M+z(x)) => y = M-z(x) y = M-z(M-z(x)) => y = M+z(x) 3. Sum of functional constraints with same net effect. y = M+(x) + M+(x) => y = M+(x) y = M-(x) + M-(x) => y = M-(x) y = M+(x) - M-(x) => y = M+(x) y = M-(x) - M+(x) => y = M-(x) y = M+z(x) + M+z(x) => y = M+z(x) y = M-z(x) + M-z(x) => y = M-z(x) y = M+z(x) - M-z(x) => y = M+z(x) y = M-z(x) - M+z(x) => y = M-z(x) .bp 1Appendix E: Momentum and Cyclic Behavior.* 0In examining the envisionment of the double heat-flow system, people occasionally ask about momentum: 6"What if the value keeps on going rather than stopping at its limit?"* Naturally, this can only occur if the system is sufficiently complex to support that behavior, and if that complexity is reflected in the causal structure description. The example of the oscillating spring demonstrates both momentum and the creation of important new landmark values. This system is governed by the differential equation:  div("d2" "dt2")X = Msubsup(z -)(X), or, more precisely, by the system of equations:  div(d dt)X = V, div(d dt)V = A, A = Msubsup(z -)(X). .diag .sp 3.0i 1Figure 15*: Causal structure description: oscillating spring without energy dissipation. .ediag .ls 1 .fs 4 0In addition to demonstrating cyclic behavior, the oscillating spring demonstrates the use of the Aristotelian and Newtonian motion rules associated with the derivative constraint (see Appendix B). In particular, the chart below uses the Aristotelian rule applied to the variable 4V*, in the transition from (3) to (4). This has the curious effect that the IQ value of 4V* changes from 4steady* to 4increasing* while 4V* remains equal to 4VMIN*. Only in the transition from (4) to (5) does the change to the IQ value propagate to cause 4V > VMIN*. Thus, when comparing the behavioral description with the physical world, state (4) is not actually distinct from states (3) and (5), but is a computationally required transitional pseudo-state. The more complex Newtonian motion rule makes the correct transition from (3) directly to (5). It produces the same behavioral description as shown below, omitting states (4), (7), (10), and (14). One may speculate that the obvious differences in rule complexity is one reason for the observed differences in theories of motion, both across history and in naive subjects [23]. .bp The following chart gives the ordinal assertions and the IQ value assertion for the value of 4x*, 4v*, and 4a*, respectively, at each time-point. The last column gives the rules, other than simple propagation, used to generate each value (Appendix C). The terms that are underlined in each row are the initial information with which that time-point was created from its predecessor.* .nf (1) x > 0 std v = 0 dec a < 0 std given (2) x > 0 dec v < 0 dec a < 0 inc Rule 1.1 (3) x = 0 dec v < 0 std a = 0 inc Rule 3.2 vmin = v3 Rule P2 (v) (4) x < 0 dec v = vmin < 0 inc a > 0 inc Rule 2.1 (5) x < 0 dec vmin < v < 0 inc a > 0 inc Rule 3.1 (6) x < 0 std v = 0 inc a > 0 std Rule 3.2 xmin = x6 amax = a6 Rule P2 (x,a) (7) x = xmin < 0 inc v > 0 inc a = amax > 0 dec Rule 1.1 (8) xmin < x < 0 inc v > 0 inc 0 < a < amax dec Rule 3.1 (9) x = 0 inc v > 0 std a = 0 dec Rule 3.2 vmax = v9 Rule P2 (v) (10) x > 0 inc v = vmax > 0 dec a < 0 dec Rule 2.1 (11) x > 0 inc 0 < v < vmax dec a < 0 dec Rule 3.1 (12) x > 0 std v = 0 dec a < 0 std Rule 3.2 xmax = x12 amin = a12 Rule P2 (x,a) (13) x = xmax dec vmin < v < 0 dec a = amin inc Rule 1.1 (14) 0 < x < xmax dec vmin < v < 0 dec amin < a < 0 inc Rule 3.1 (15) x = 0 dec v = vmin std a = 0 inc Rule 3.2 MATCH detected with state (3). Rule R2 Summarized cycle (landmark values only): (3) x = 0 dec v = vmin std a = 0 inc (6) x = xmin std v = 0 inc a = amax std (9) x = 0 inc v = vmax std a = 0 dec (12) x = xmax std v = 0 dec a = amin std (3) x = 0 dec v = vmin std a = 0 inc .fi