Taming Intractible Branching in Qualitative Simulation

1 Introduction

Qualitative simulation is a promising method for reasoning about the behavior of physical systems, starting from incomplete knowl­ edge of the structure and initial state [Kuipers, 84, 86; de Kleer and Brown, 84; de Kleer and Bobrow, 84; Forbus, 84; Williams 84a, 86]. Incompletely known values may be described quali­ tatively in terms of their relations with a discrete set of land­ mark values. Incompletely known functional relations may be described qualitatively as monotonically increasing or decreas­ ing, and passing through certain corresponding landmark values. Methods of qualitative simulation have demonstrated promis­ ing results on a variety of small and moderate-sized examples [Kuipers, 84, 85, 86, 87; Forbus 84, 86; de Kleer, 84; de Kleer and Brown, 84; Williams, 84a, 86].

In attempting to extend these techniques to simulate the con­ tinuous behavior of larger and more tightly interacting systems, however, certain problems have been encountered, resulting in a proliferation of predicted behaviors. Under the different repre­ sentations for qualitative behavior, this proliferation is manifest in different ways.

• (a) A tree of behaviors for the cascaded tank system pro­ duced by QSIM.
• (b) A transition graph for damped spring system from [de Kleer and Brown, 1984].

Figure 1: Intractible branching in tree and transition graph rep­ resentations.

'This research w._. supported in part by the N a tiona! Science Foundation through grants MCS-8303640, DCR-8417934, and DCR-8512779.

• QSIM (Kuipers, 85, 86] produces a tree of possible behav­ iors, where each path down the tree is a sequence of qual­ itative states. Proliferation is manifest as an intractibly branching behavior tree. (Figure 1a)
• Representations that do not create new landmark values (de Kleer and Brown, 84; de Kleer and Bobrow, 84; Forbus, 84; Williams, 84a, 86] are able to enumerate all possible quali­ tative stat€s in advance, and thus produce a total envision­ ment, or transition graph on the qualitative states. Prolif- · eration is exhibited in the transition graph as branches and loops, making an infinite set of possible paths through the graph. (Figure 1 b)

An important class of proliferation problems arises with cou­ pled systems such as two tank problems (Figure 2). (These prob­ lems represent general classes of important applications problems (e.g. (Sachs, et al., 1986], etc.).)

The underlying problem, illustrated here in terms of QSIM behaviors, is that when two distinct processes produce qualita­ tive parameters that are changing in the same direction, their difference is unconstrained, except by continuity. Figure 3 shows one such behavior, representing a qualitative phenomenon we call "chatter". Here the parameter netflowB chatters, while the other parameters move without changing direction. Figure 4a shows the transition graph representation of a single uncon­ strained parameter. For the examples shown here, the chattering behaviors consist of unconstrained wandering among the quali­ tative states (+,inc}, (+,std}, and (+,dec}.l The problem is that, with no information about the actual shapes of functior.al relationships such as outflowA = M+(pressureA), all of the predicted behaviors are real possibilities. But an exponentially growing set of behaviors so obscures the actual qualitative prop­ erties of the system as to eliminate the value of qualitative sim­ ulation.

We have developed two distinct methods for solving this prob­ lem. One method applies to the general problem, and produces a slightly weaker qualitative description that collapses unimpor­ tantly distinct branches into a single history. The other method takes advantage of additional knowledge or assumptions about the system, and produces a correspondingly stronger result.

Figure 3: One "chattering" behavior of the Cascaded Tanks

• (a) The Cascaded Tank system.
• (b) The Coupled Tank system.

2 Ignoring Irrelevant Distinctions

Consider the general case of the two cascaded tanks (Figure 2a). If we are filling the system from an initially empty state by pro­ viding a fixed input to the up-stream tank, the flow from tank A to tank B will increase monotonically with time. However, since the relation outflowA = M+(amountA) is incompletely known, outflowA can "wiggle" considerably while increasing. Depend­ ing o:h how this interacts with the behavior of outflowB, which is monotonically related to amountB, the variable netflowB(t) chatters, rising and falling arbitrarily until finally returning to zero. This gives a large set of behaviors, distinguished only by the behaviors of netflowB(t).

Suppose, for a particular application, we are not concerned about the detailed behavior of netflowB(t), but only its sign. We would like to modify the QSIM algorithm to simulate the mechanism using only the qualitative magnitude of netflowB, and ignoring its direction of change. We can do this by adding a new term, ign, as a possible description of a direction of change. We then create a new set of qualitative state transitions, cor­ responding to the transitions in Figure 4b. The effect of these transitions is that all the behaviors wandering among the quali­ tative states (+,inc), (+,std}, and (+,dec), are collapsed into a single behavior with the qualitative state (+, ign). Its eventual transition to (0, ign) brings the system to quiescence and ends the behavior.

• (a) The full qualitative transition graph is adequate to cap­ ture continuity constraints, but permits "chattering" be­ haviors.
• (b) The collapsed transition graph, ignoring direction of change, eliminates chatter, but fails to detect discontinuous change.

Figure 4: Transition graphs for a single unconstrained qualitative parameter.

Unfortunately, this is not sufficient. The transitions in Figure 4b fail to capture the constraint that the derivative of a changing parameter must change continuously. For example, the transition

should be excluded in case the only possible complete value for the second state is (0, inc). Therefore, we apply a global satisfi­ ability filter after each step of the prediction when an ign value is used. The satisfiability filter checks:

1. Whether a consistent state exists with all ign values re­ placed by one of {inc, std, dec}. This is accomplished by treating ign as unknown, and propagating to determine whether there is one or more complete states, consistent with the other known values.
2. If so, whether there is a consistent successor of the previ­ ous state. This is done by checking, for each parameter, whether its pair of qualitative values is consistent with a transition.

The result of qualitative simulation of the cascaded tanks, ignoring direction of change for netflowB, is two distinct behav­ iors (Figure 5). In one case both tanks reach equilibrium at the same time, while in the other, tank A reaches equilibrium before tank B. 2 Naturally, since direction of change is ignored, QSIM does not detect critical points or create new landmark values for netflowB, though it still does so for the other parameters.

This method eliminates intractible branching by changing the level of qualitative description of behavior, collapsing the descrip­ tions of the different real possibilities. However, this multitude of real possibilities only arises in case of pathological interactions between the "wiggles" of different partially known M+ relations. If we know that the relations are reasonably well-behaved, we would like to be able to take advantage of this knowledge to eliminate the chattering behaviors as impossible, and produce a stronger description of the real possible behaviors. Our second method gives us this power.

2 Strictly speaking, there is only one real behavior, with both tanks reach­ ing equilibrium at t = oo. QSIM normally treats exponential approach to a limit like any other move-to-limit, and considers the possibility of reaching the limit in finite time, which corresponds to the physical perception of such a process. QSIM can be restricted to produce only the single mathematically correct prediction.

• (a) The two tanks reach equilibrium at the same time.
• (b) Tank A reaches equilibrium before tank B.

Figure 5: Two IGN behaviors of the Cascaded Tanks.

3 Applying Higher-Order Derivatives

By examining the detailed structure of a branch point in the ar­ bitrarily chattering behavior of the parameter net flowB, we can obtain a clearer picture of the nature of the proliferation prob­ lem. The typical branch is a three-way branch from a point where netflowB has a critical point, i.e. its derivative is zero. The standard QSIM transition table [Kuipers, 1986] provides three possibilities after such a point: the parameter can increase, re­ main steady, or decrease. (Figure 6a)

In a system sufficiently well-understood and well-behaved to be described by a linear ordinary differential equation, the unique behavior is determined at a critical point by the first non-zero higher-order derivative at that point. For these coupled tank sys­ tems, this is the second derivative, or curvature, of the parameter in question (Figure 6b ). The usual qualitative value for a param­ eter consists of a qualitative description of its magnitude and its direction of change. Its curvature is not made explicit, so the spurious possibilities cannot be filtered out and a proliferation of behaviors results.

The value of higher-order derivative information has been rec­ ognized previously. Williams [1984a, 1984b] showed that higher­ order derivative information could disambiguate certain branch­ ing behaviors. De Kleer and Bobrow [1984] then presented meth­ ods for explicitly deriving qualitative descriptions of higher-order derivatives from the original confluences for a mechanism. Our approach starts from these correct observations, but overcomes two limitations of the methods presented in previous papers. 3

• The paper (de Kleer and Bobrow, 1984] gives very little guidance on when to apply higher-order derivative infor­ mation, and how to derive it for a general constraint model when it is needed.
• The straight-forward approach extends the constraint model to include terms for the higher-order derivatives and con­ straints linking them to the previous terms. Unfortunately, this simply pushes the problem into the higher-order terms, while adding parameters whose distinctions may cause new qualitative branches in the behavior tree.
• (a) netflowB(t) has a three-way branch from a critical point where netflowB'(t) = 0.
• (b) In case we know that netflowB"(t) < 0, we get only one branch where netflowB'(t) = 0.

Figure 6: Three-way and one-way branch

3 De Kleer a.nd Bobrow have independently identified and corrected certain errors in their paper [J. de Kleer, personal communication].

3.1 Our Approach

Our approach permits automatic identification of the problem, and automatic derivation of the appropriate constraints, which we call curvature constraints. 4 We focus our attention on the parameter describing the Highest Order Derivative (HOD) in the system. As we shall see, it is possible for a system to have more than one HOD.

In outline, the algorithm consists of two steps:

1. Identify the highest-order derivative(s), HOD or HODs, in the system.
2. This method is necessary and applicable in case there is intractible branching from points where H 0 D' = 0.
3. For each HOD, algebraically derive an expression, valid where HOD'= 0, for HOD" in terms of the other param­ eters of the system.
4. Use this expression to determine the sign of H 0 D" at critical points, and generate only transitions con­ sistent with this curvature.

3.2 Identifying the HOD

We can identify all the HODs in a general constraint model by · viewing constraints as paths linking parameters. We are looking for the maximal points on chains of derivative and other two­ argument constraints. We use the QSIM notation [Kuipers 1984, 1986] for constraint models, though our techniques apply gener­ ally.

• The derivative constraint leads upward from a parameter to its derivative.
• The two-argument constraints, M+, M-, and minus, con­ nect parameters horizontally.
• The three-argument constraints, ADD and MU LT, termi­ nate a chain and block passage. In order to avoid unneces­ sary blockage, it may be necessary to apply algebraic sim­ plification rules such as those in [Kuipers, 1984, Appendix D), e.g.

• Starting from each derivative constraint, move upward or horizontally until no further progress is possible. The max­ imal derivatives are the HODs.
• If the chain forms a closed loop (e.g. the frictionless spring) the analysis is unnecessary and may be terminated, since the loop already encodes the desired curvature constraint.

Since this process may yield several maximum points, there may be multiple HODs, possibly of different orders. Both the Cascaded Tanks and the Coupled Tanks have two distinct HODs: netflowA and netflowB. However, in the Coupled Tanks both HODs exhibit chatter, while in the Cascaded Tanks system only netflowB does.

·There can certainly be cues where both HOD' and HOD" vani8h, and the constraint must be stated in terms of even higher-order derivatives. How­ ever, for many models, including the damped-spring case discussed in (de Kleer and Bobrow, 1984), applying the second derivative i8 sufficient, so we confine our attention to that case. Extension to the higher-order case ia straight-forward.

3.3 Deriving the Curvature Expression

3.3.1 The Smoothness Assumption

In order to derive an expression for the sign of the curvature, HOD", while still using incompletely known and possibly non­ linear monotonic function constraints, we need to assume that the system is reasonably well-behaved in any local neighborhood.

Suppose Y = M+(X). This means that there is a monotoni­ cally increasing function M such that for all t, Y(t) = M(X(t)). The relationship between the first derivatives of X and Y is

where M' is the derivative of the monotonic function M . This tells us only that Y'(t) and X'(t) must have the same sign, since all we know about M' is that it is positive. Since M" is un­ constrained, the relationship between second derivatives is even weaker:

The Smoothness Assumption says that in any local neighborhood, M(X) is approximately a linear function. In practice, as we evaluate the curvature constraints, we assume that the M" term is sufficiently small that we may regard Y"(t) and X"(t) as having the same sign.

3.3.2 Rules for Curvature

We can derive a set of rules for reasoning about the sign of the curvature of a particular parameter after applying the Smooth­ ness Approximation. By treating arithmetic relations as quali­ tative relations on signs and allowing multiple solutions, we may write sign(x + y) = sign(x) + sign(y).

For brevity of notation, we define:

For a parameter X , sd(X) is just its direction of change, and so is explicitly represented by QSIM at each time-point. sd2(X) is its curvature, so the curvature expression solves for curvature in terms of explicitly available information.

The rules for deriving the explicit curvature expression are the following:

1. Start with the expression sd2(HOD).
2. Apply the following rules for qualitative curvature in depth­ first order wherever they are applicable, to propagate sd2 terms through all possible constraints.

The first rule depends on the Smoothness Assumption. The others are straight-forward consequences of the theorems of differential calculus. This process terminates when ev­ ery explicit parameter is either an exogenous variable, or explicitly linked to its derivative.

1. Apply the final transformations:

and simplify the result.

The result is an expression for sd2(HOD) in terms of explic­ itly available information. It is used as a constraint, applied only at critical points of the HOD, to select among branches such as that in Figure 6.

3.4 The Coupled Tanks example

Let us follow the derivation of the curvature expression on the Coupled Tanks (Figure 2b ).

The parameters netflowA and netflowB are both HODs in this system, and both exhibit the chattering behavior. We will explicitly derive an expression for the sign of the curvature of netflowB, sd2(netflowB), valid at critical points, i.e. where sd(netflowB) = 0.

sd2(netflowB) = sd2(crossflowAB)- sd2(outflowB) sd2(crossflowAB) = sd2(pressureDif f) = sd2(pressureA)- sd2(pressureB) = sd2(amountA)- sd2(amountB) = sd( netflowA)- sd( netflowB) = sd(netflowA) sd2(outflowB) = sd2(pressureB) = sd2(amountB) = sd(netflowB) = 0.

The resulting constraint, sd2(netflowB) = sd(netflowA), tells us that the sign of the curvature of netflowB at a critical point is the same as the sign of the slope of netflowA at the same point in time. A similar derivation gives us the constraint sd2(netflowA) = sd(netflowB), applying at critical points of netflowA. Applying these two constraints, we get the following single behavior for the scenario of filling the Coupled Tank system from empty (Figure 7).

We predict an unambiguous behavior: amount A and amountB increase monotonically from zero to their equilibrium values; netflowA decreases monotonically to zero; and netflowB in­ creases monotonically from zero to some maximum value, then decreases back to zero. This description is stronger than that produced by our first method, in that all parameters now have complete qualitative descriptions. In the method of ignoring ir­ relevant distinctions the HODs, and certain other closely related parameters exhibiting chatter, would be described in terms of magnitude only.

4 Conclusions

Although the class of qualitative simulation problems we treat here has considerable importance in its own right, the methods we have developed have a more general significance. A fundamental decision in the modeling of a system is selection of the level of detail for the model. Both methods explicitly manipulate that level of description.

• The method of ignoring irrelevant distinctions, by ignor­ ing direction of change for certain parameters, represents a change in the level of detail of the model. In its current form, it is a knowledge engineering method, to be applied explicitly as a model is being developed and debugged. We expect that, using techniques similar to our second method, it can be extended to recognize "chattering" situations au­ tomatically, and decide when to ignore which distinctions.
• The higher-order derivative method, by applying the smooth ness assumption and a more powerful inference about the algebraic structure of the constraint model, allows the sim­ ulation to produce a complete qualitative description of all the parameters, including the highest-order derivatives. It also preserves QSIM's ability to create new landmark val­ ues.

Chiu and Kuipers [1987] present the details of our methods for automatically deriving and applying the curvature constraint. While these methods handle important cases of coupled systems, there are additional cases of intractible branching in the more general second-order system. Lee, Chiu, and Kuipers [1987] ex­ tend this work by applying the curvature method and two ad­ ditional constraints to handle an important case of the damped spring system.

NETFLOWA

NETFLOWB

Figure 7: Single HOD behavior of the Coupled Tanks.

Thus, our two methods are able to solve the "chattering" problem for coupled systems, in the most general case by ignoring certain distinctions, and, when more knowledge is available, by applying more powerful inferences to produce a stronger result. These methods provide important mathematical and computa­ tional tools for qualitative simulation, and move us toward our goal of reasoning qualitatively about complex physical systems.

5 References

1. C. Chiu and B. Kuipers. 1987. The curvature constraint algorithm and a complete simulation of a two tank system. University of Texas Computer Science TR-xx, forthcoming.
2. J. de Kleer and D. G. Bobrow. 1984. Qualitative rea­ soning with higher-order derivatives. In Proceedings of the National Conference on Artificial Intelligence (AAAI-84). Los Altos, CA: Morgan-Kaufman Publishers.
3. J. de Kleer and J. S. Brown. A qualitative physics based on confluences. Artificial Intelligence 24: 7- 83, (1984).
4. J. de Kleer. How circuits work. Artificial Intelligence 24: 205 - 280, (1984).
5. K. D. Forbus. Qualitative process theory. Artificial Intel­ ligence 24: 85 - 168, (1984).
6. B. J. Kuipers. 1984. Commonsense reasoning about causal­ ity: deriving behavior from structure. Artificial Intelligence 24: 169 - 204.
7. B. J. Kuipers. 1985. The limits of qualitative simulation. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-85}. William Kaufman, Los Altos, CA.
8. B. J. Kuipers. 1986. Qualitative simulation. Artificial Intelligence 29: 289 - 338.
9. B. Kuipers. 1987. Qualitative Simulation as Causal Expla­ nation. To appear in IEEE Transactions on Systems, Man, and Cybernetics 17, No. 3, 1987; special issue on Causal and Strategic Aspects of Diagnostic Reasoning.
10. W. W. Lee, C. Chiu, and B. Kuipers . 1987. Steps toward constraining qualitative simulation. University of Texas Computer Science TR-87-44.
11. P. A. Sachs, A. M. Paterson, and M. H. M Turner. 1986. Escort - an expert system for complex operations in real time. Expert Systems v. 3, n. 1, pp. 22-29.
12. B. Williams. 1984. Qualitative analysis of MOS circuits. Artificial Intelligence 24: 281 - 346. (a)
13. B. Williams. 1984. The use of continuity in a qualitative physics. In Proceedings of the National Conference on Ar­ tificial Intelligence (AAAI-84}, 350- 354. (b)
14. Brian Williams. 1986. Doing time: putting qualitative reasoning on firmer ground. In Proceedings of the Fifth National Conference on Artificial Intelligence (AAAI-86}. Los Altos, CA: Morgan Kaufman Publishers, pp. 105-112.