Comparative Analysis of STructurally Different Dynamical Systems

1 Introduction

Qualitative reasoning (QR) is concerned with predicting and explaining the qualitative behavior of dynamical sys­ tems. An important QR problem is the comparison of behaviors of two systems, that is, an assessment of the relative value of system variables at chosen time-points. More specifically, this comparative analysis (CA) task is directed at ( 1) predicting possible consequences of dif­ ferential antecedent conditions and (2) finding possible causes of differential responses of the two systems.

CA questions arise in a variety of contexts. Consider an engineer diagnosing an electrical circuit by comparing the observed faulty behavior with a reference behavior. Or scientists estimating the impact of a disturbing pro­ cess on a quantity measured in an experiment.

With few exceptions, QR methods for comparative analysis have focussed on the comparison of systems with the same structure: intra-model CA [Weld, 1990; Chiu and Kuipers, 1992; Neitzke and Neumann, 1994; de Jong et al., 1996] . The comparison of dynamical sys­ tems with a different structure, inter-model CA, is con­ sidered to be a "terribly difficult" problem in general [Weld, 1990] . The limitation to intra-model CA is a se­ rious shortcoming, since many interesting questions can be mapped onto inter-model CA problems, including the examples given above.

In this paper we introduce CEC*, an implemented method for comparative analysis which treats intra­ model CA and inter-model CA within a single frame­ work [de Jong, 1996]. The exposition starts with the definition of some basic concepts and a formulation of the method as a propagation process (sec. 2). The con­ straints employed in the propagation process form the topic of sec. 3. Sec. 4 shows how CEC* deals with an example of a predictive and a diagnostic CA question. The discussion in sec. 5 gives correctness guarantees and pays attention to the generality of the method. Brief notes on further research conclude the paper.

2 Basic concepts and outline of method

2.1 Pairs of comparison

In a comparative analysis a qualitative behavior of a first system is compared with a behavior of a second system. We assume that the qualitative behaviors have been gen­ erated by the QSIM algorithm [Kuipers, 1994], although the principles underlying our method do not depend on this choice.

Fig. 1 shows a system of two cascaded tanks. The (constant) input variables are the inflow i and the sizes ru., r1 of the orifices of the upper and lower tank. The amounts of water au, a1 in the tanks form the state variables. One of the qualitative behaviors produced by QSIM for the cascaded tanks is summarized in fig. 1(c). As can be seen, the upper tank reaches equilibrium before the lower tank. ·

Now suppose we compare this system with a second cascaded-tanks system that has a leaky upper tank. The leaky system is structurally different from the watertight one: the netflow into the upper tank is given by nu. = i­ ou.-oh, whereoh = h(au.), 8hf8au. > 0. 1 The qualitative behavior in which the upper tank reaches equilibrium first is also a behavior of the leaky system.

We will compare the watertight and leaky cascaded tanks when both exhibit the behavior of fig. 1(c). The behaviors of the two systems are topologically equal [Weld, 1990] with respect to the shared variables (a sit­ uation not obtaining in general, see sec. 4). The two behaviors are compared at so-called pairs of compari­ son. A pair of comparison pc is a pair of distinguished time-points (t, i) from the first and the second behavior, respectively.

1 Following [Weld, 1990], the hat accent : will be used to denote the variables of the second system.

Def. 1 (Meaningful pairs of comparison) Two be­ haviors are given with sequences of distinguished time­ points to, ... , tn and io, ... , im. The pair of comparison pe = (t, i) is a meaningful pair of comparison, if ·

1. t and i are the initial time-points t0 and i0 or the final time-points tn and im;
2. t and i are time-points at which variables p and p reach the same basic landmark value 0, oo, or -oo.

A particular pair of comparison could be singled out by both of the criteria in the definition. For the behaviors of the watertight vs. the leaky cascaded-tanks system we find three meaningful pairs of comparison: pe0 = (t0 , i0 ), pet= (tt, it), pe2 = (t2, i2) (see fig. 1(c)).

A partial ordering relation can be defined on the pairs of comparison which formalizes the intuitive notion that one pair of comparison occurs before another. For two pairs of comparison pet = (tt,it) and pe2 = (t2,i2) it holds that pet ~ pe2, iff t1 ::; t2 and it ::; i2. If pet and pe2 are different pairs of comparison and pe1 ~ pe2 , then pe1 is said to be a predecessor of pc2 (and pc2 a successor of pet). A set of pairs of comparison ordered according to the ~-relation will be called an ordered pairs of com­ parison (OPC) structure. This structure always has a top element, the first pair of comparison, and a bottom element, the last pair of comparison. In the example we have the simple OPC structure pco ~ PCt ~ pc2.

Two successive pairs of comparison in an OPC struc­ ture mark out what we will call a pair of behavior frag­ ments, one for each system. The behavior fragments de­ fined by the successive pairs of comparison pet = (it, it ) and pc2 = (t2, i2) are the closed intervals [tt, t2] and [i1, i2]. If the interval of a behavior fragment does not contain any distinguished time-points except for its boundaries, we will say it is a primitive behavior frag­ ment, otherwise a composite behavior fragment. Com­ bining the three pairs of comparison identified for the cascaded-tanks example with the qualitative behavior in fig. 1 (c), we directly see that all behavior fragments ([to , t1 J, [tt , t2J, [io, it], [it, t2]) are primitive.

2.2 Relative values

Pairs of comparison have been introduced to specify when the values of variables in the two systems can be meaningfully compared. In order to express how the val­ ues of a shared variable p in the first and second system relate at a pair of comparison, the notion of relative value (RV) is introduced.

De f. 2 (Relative value) Given a variable p and a pair of comparison pc = (t, t). The relative value (RV) at pc is defined as:

Often the RV of a variable at a pair of comparison pc is denoted by RV(p)pc, and RV(p)pc =11 is equivalent to p 'ftw Remark that a relative value is only defined for variables that are shared by the two systems. A spe­ cial kind of RV is the relative duration of the behavior fragments defined by two successive pairs of comparison. Written as RV (T)pc, -+pc,, this RV expresses whether the intervening behavior fragment of the second system has a longer, shorter, or equal duration compared to that of the first system.

A few basic (in)equality relations and algebraic oper­ ations for RVs can be introduced. This simple algebra is used in the definition and evaluation of propagation constraints for comparative analysis that are discussed below.

Def. 3 (Equality and inequality) For two relative values the equality RV(p) = RV(q) and inequality RV (p) < RV ( q) relations are defined as follows:

Similar definitions can be given for >, 2::, ::;, and ~·

De f. 4 (Basic algebraic operations) For two rela­ tive values the addition RV(p) + RV(q) and subtraction RV(p) - RV(q) operations are defined as follows:

By means of the concepts introduced above comparative analysis can be formalized as a propagation problem. The input of CEC* consists of a pair of qualitative be­ haviors, the QDEs giving rise to them, and a set of rela­ tive values at either the first or the last pair of compari­ son, that is, the top or the bottom of the OPC structure. The analysis proceeds by propagating the initial RVs through the OPC structure, from each pair of compari­ son to its successor(s) or predecessor(s) . When the direc­ tion of propagation is from top to bottom, the method is predicting the consequences of differential antecedent conditions. The reverse direction corresponds with the explanation or diagnosis of differential responses of the two systems.

For this propagation process to succeed we need prop­ agation or RV constraints. These constraints relate RV s at the same pair of comparison or at successive pairs of comparison.

3 Constraints on relative values

3.1 Variables at a pair of comparison

A direct way to infer the RV of a variable p at a pair of comparison pc = (t, i) is to examine the qualitative value of the continuously differentiable functions p and pat t and i. The qualitative value of a variable p(t) is either a landmark value lj or an open interval between two landmark values ]lj,lj+I[ in which p(t) falls. If we extend the applicability of>, =, and < to intervals, the following result is obtained: 2

Prop. 1 (Qualitative values) Let pv and fo; be qual­ itative values of p and p, respectively, at pair of compar­ ison pc = (t, i) . For the difference p(t)- p(t) we have: pv

Knowing the sign of the difference p(t)- p(t) immedi­ ately gives the relative value of p at pc, RV (p )vc . For ex­ ample, in fig. 1 (c) we see that at pc0 a,. = 0 and a,. = 0, so that RV(au)pc 0 =II ·

3.2 Functions at a pair of comparison

Suppose that a variable p shared by the two systems is a continuously differentiable function of a vector of variables r in the first system and 8 in the second system:

The problem is that p(t) and p(t) cannot be straightfor­ wardly compared, because in general the vectors r and s and the functions f and g will be different. To make the expressions for p and p comparable, define q as the vector of variables occurring both in r and in 8, and a as the vector of variables occurring either in r or in s, but not in both. We can now give a criterion for the comparability of p and p:

2 For proofs of the propositions, see [de Jong, 1996].

Def. 5 (Comparable functions) Suppose p and pare defined by continuously differentiable functions f and g, as in (1). The functions f and g are called comparable with respect to a continously differentiable function h and vectors a 0 and a 0 , if

The variable a? (a?} equals either a variable in r (8) or, if not occurring in r (8), has a comparison value c; (c;).

An example will clarify this definition. From the cascaded-tanks QDEs we take n,. = i - o,. and fi,. = i - o,. - oh. The vector q of shared variables is [i o,.]' and a = oh. Now let n,. = h([i o,.]', 0) = i- o,. and fi,. = h([i 8,.]', oh) = i- o,. - oh, then h makes f and g comparable. The comparison value 0 is chosen for the flow out of the leak in the first system, i.e. oh = 0.

With the generalized mean value theorem for differen­ tiation we find:

Prop. 2 (Functional relations) The variables p and pare defined by functions f and g. Iff and g are com­ parable with respect to a function h, then at pair of comparison pc = (t, i):

dq and da. are vectors with dq,i = 8~, h( '1/J, a 0 ) and da,i = 8 ~, h( 'ljJ, a 0 ). Each 'ljJ j lies between % ( t) and (]j( i), and each a~ between a~(t) and a~(i).

In the cascaded-tanks example we have at pc0

Since the tanks are filled from empty, oh(i0) = 0 and the last term disappears. The expression can be easily transformed into an RV constraint:

Suppose that the inflow and outflow are known to be equal in the two systems (illvco, o,.llvc 0 ), then we can readily infer with clefs. 3 and 4 that the net flow is also equal (n,.llvc 0 ).

Prop. 2 is equally applicable to intra-model and inter­ model CA problems. In the former case, the qualitative models of the two systems, and thus all corresponding functional relations, are identical. Consequently, a = 0 and p(i)- p(t) = dq(q(i)- q(t)).

3.3 State variables between pairs of comparison

The question to be addressed now is how the relative values of variables at a pair of comparison pc1 = (h, i1) relate to those at a predecessor pair of comparison pc0 = (t0 , i0 ). For this, we have to take into account how the variables of the two systems change during the respective behavior fragments between the pairs of comparison.

We will assume that the two behavior fragments start simultaneously, i.e. t0 = i0 · If this is not the case, the behavior fragments have to be synchronized first by a suitable time translation. T = t 1 - to and T = i 1 - io represent the durations of the two behavior fragments .

We can distinguish several cases in the comparison of two behavior fragments by considering how their dura­ tions relate. When comparing primitive behavior frag­ ments, we have T < T, T.= T, or T > T, and we can rewrite the difference in x at pc1 as follows :

Consider the case T < T. The difference x(il)- x(tl) is split up into x(ii)- x(h) and x(i1)- x(il). The sign of the former part directly follows from the qualitative be­ havior of x, whereas the latter part must be determined.

For the general problem of establishing the difference x(tb)- x(tb) in terms of the difference of variables at ta, we have to study the QDEs which define the dynamical behavior of the two systems. First, we introduce three classes of variables: shared state variables :z:, shared in­ put variables u , and auxiliary variables a. A variable v is (1) a shared state variable if it is shared and a state variable in at least one of the systems, (2) a shared input variable if it is shared and an input variable in at least one of the systems, or (3) an auxiliary variable if it is not shared. The QDEs of the two systems give rise to the state equations:

We can now define a comparison system and transform it into a familiar linear form:

Prop. 3 (Linear comparison system) Consider the comparison system obtained by subtracting the state equations (2). If the functions h and h are com­ parable through a function h, such that f1(x, u, a) = h(x, u, a 0 ) and f'J(z, u, a) = h(z, u , a 0 ), then we can write the state equation of the comparison system as:

A(t), B(t), and E(t) are time-varying matrices of continuous functions a;j(t)= 8 ~h;(e(t),v(t),a 0 (t)), J

b;k(t)= 8 ~k h;(e(t) , v(t), a 0 (t)) , and eil (t)= 8 ~, h;(e(t) , v(t) , a 0 (t)) . ~j(t) lies between x1(t ) and x1(t), vk(t) between uk(t) , and uk(t), and a?(t) be­ tween a?(t) and a?(t).

The proposition follows directly with the definition of comparable functions and the application of prop. 2 to each h;.

For the comparison of watertight and leaky cascaded tanks, the relevant vectors of variables are :z: = [a, az]', u = [i r, rc]', and a = oh. With the QDE in fig. 1 we determine the following matrices in state equation (3) :

where the matrix elements are given by the partial derivatives ah;/ax1, ah;/auk, and ah;/aaz. When con­ sidering the comparison system on an interval in which x,z,u,u,a 0 ,a 0 have signs as between pc0 and pelt we find that a;1 ,b;1 > 0.

Again, it is useful to point out how intra-model CA is treated as a special case of inter-model CA. When comparing two structurally identical systems, the term E(t)(a 0 (t)- a 0 (t)) drops out of (3) .

The formulation of a linear comparison system is a pivotal move in deriving RV constraints between succes­ sive pairs of comparison. An explicit solution to (3) is a basic result in linear system theory [Rugh, 1996] .

Prop. 4 (State variables) Suppose two primitive be­ havior fragments are compared. The difference between the shared state variables :z: at pc1 = (t1, t1) can be ex­ pressed in terms of differences at pc0 = (t0 , i 0 ) as:

where the 'function F is defined as follows:

The usefulness of prop. 4 hinges on the possibility to determine the transition matrix ~(tb, r) for all T on an interval [ta, tb]· Explicitly solving for~( tb, r) is generally a very difficult task, but for our purposes it suffices to determine the signs of the elements of ~(tb, r). A direct way to find such a qualitative transition matrix is to trace the zero-input solutions of (3) in the phase space for initial states consisting of the column vectors of the unit matrix I (see, e.g., [Rugh, 1996]). Here we restrict ourselves to stating the resulting transition matrix for the cascaded tanks between pco and pc1:

with </>;j (tb, T) > 0 for all Tin ]ta, tb]·

Armed with the vectors x, u, a 0 and matrices B , E, 4> determined above, we can use prop. 4 to express dif­ ferences at pc1 in terms of differences at pc0 . Evaluating (5) forT < T , we obtain for state variable a,:

and c 1 , . . . , C4 > 0. The constant factors are transi­ tion matrix elements (e.g. , c1 = </>n(t1, t0 )) or inte­ grals involving transition matrix elements (e.g., c3 = ft~ 1 </>n ( t1, T )b12 ( T )dT ). From the qualitative behavior in fig. 1 (c) we see that the amount of water in the up­ per tank is increasing between pc0 and pc1 , so a, (il)­ au( tl) < 0 (since t1 < t 1 ) .

Eq. (7) can be directly translated into a constraint:

The RV constraint implies, by contraposition, that from a,llpc 0 , aullpcp i llpc0 , rullpco we must conclude that the relative duration from pc0 to pc1 cannot be shorter.

3.4 Constants between pairs of comparison

Besides state variables, constants also have their differ­ ence propagated between pairs of comparison.

Prop. 5 (Constants) Suppose two behavior frag­ ments defined by pco = (to, t0 ) and pc1 = (t1 , t1 ) are compared. If the variable c has a constant value during the behavior fragments, then c( il)- c( tl) = c( io)- c( to).

The constancy of the inflow in the example leads to the constraint RV(i)pc 1 = RV(i)pco·

4 Results

The CEC* algorithm outlined in sec. 2 has been imple­ mented in Common Lisp, as a module interacting with the QSIM program. At each pair of comparison a con­ straint satisfaction problem is generated consisting of the variables shared by the two systems, domains { ,U., 1t, II} of their possible relative values, and constraints relating the RV s of variables at the current and at predecessor pairs of comparison. The RV constraints are instantiated from a database with templates derived from props. 1, 2, 4, 5. A consistent combination of RVs for the variables at a pair of comparison is called a comparative state. There may be several comparative states at a particular pair of comparison. The comparative states at a pair of comparison are linked to comparative states of predeces­ sor and successor pairs of comparison to form a compar­ ative envisionment [de Jong et al. , 1996]. Branching in the comparative envisionment is possible, because at the pairs of comparison an RV is either ,U. , II, or 1)-.

An example of a comparative envisionment produced by CEC* is shown in fig. 2(a) . The envisionment answers the predictive CA question: How does the equilibrium state of a cascaded-tanks system with a leaky upper tank differ from that with a watertight upper tank when the systems are considered under the same conditions? Each path from the first to the last comparative state in the envisionment forms a comparative behavior. Although ambiguities arise with respect to a1,nz at pel> the five possible comparative behaviors prediCt a single outcome: the leak tends to lower the amount of water in the tanks at equilibrium ( CS pc,,o ). No unambiguous conclusion can be drawn about the relative durations to reach the equilibrium state.

Fig. 2(b) illustrates a diagnostic CA question: When the relative amounts of water at pc1 and pc2 have been measured for watertight and leaky cascaded tanks filled from empty, and the orifices have the same size, which differences could account for the lower equilibrium wa­ ter amounts in the leaky system? CEC* finds three possible causes: (1) a leaky upper tank and lower in­ flow ( CS pco ,O ), (2) a leaky upper tank and higher inflow ( CS pc 0 ,2 ), and (3) a leaky upper tank only ( CS pco, l ). The leak, making the second system structurally differ­ ent from the first, tends to lower the equilibrium amounts at pc2 . An additional difference in initial conditions may strengthen ( i.U.pco ) or attenuate (ill' pco ) this effect .

The CEC* program· has been tested on a range of intra-model and inter-model CA questions concerning simple and more advanced QR systems, such as bath­ tubs, watertanks filled by a pump, masses on a spring, heat exchangers, sliding blocks, and tensile fracture tests. These examples generalize upon the cascaded­ tanks example by requiring CEC* to deal with topolog­ ically different qualitative behaviors, region transitions, and composite behavior fragments between pairs of com­ parison. We are currently embedding CEC* in a sys­ tem for the integration of measurements from a scientific knowledge base.

5 Discussion and related work

The CEC* algorithm has been proven sound and incom­ plete [de Jong, 1996]. Analogously to [Kuipers, 1994], soundness is taken to mean that for any two real behav­ iors of the systems that are in conformity with CEC*'s input, a comparative behavior describing their differ­ ences is included in the comparative envisionment. On the other hand, a comparative envisionment may con­ tain comparative behaviors that do not correspond to any two real behaviors in conformity with CEC* 's in­ put. CEC* then fails to derive a stronger conclusion and is consequently incomplete.

The proof of soundness is enabled by the mathematical foundation of the RV constraints. The propositions in sec. 3 also help in judging the generality of the method. In principle, the theorems apply to systems of arbitrary order and structure. A practical problem in evaluating (5) of prop. 4, however, is that it may be difficult to establish whether a transition matrix function </>ij ( tb, T) changes sign during [ta, tb], and hence to establish the sign of the elements of CI>(tb, ta) and ft~CI>(tb, T) . .. dT in F(tb , ta)· The formulation of the difficulty in terms of concepts from linear system theory has the advantage of making this problem well-defined and of suggesting possible solutions (see [de Jong, 1996]).

The computational complexity of CEC* is of the or­ der O(n3q), where q is the (maximum) number of shared variables and n the number of pairs of comparison in the OPC structure. In the examples we have studied, the average-case behavior turned out to be more agree­ able and could be improved by integrating additional RV constraints (e.g. , measurements of variables at a pair of comparison) during the analysis.

CEC* borrows ideas on the mathematical formulation and the propagation approach from existing CA meth­ ods, in particular DQ analysis [Weld, 1990] and CEC [de Jong et al., 1996]. A notable exception to the rule that existing CA methods are restricted to intra-model CA is the model sensitivity approach described in [Weld, 1992]. 3 In this approach, a behavior arising from a sim­ ple model is compared with a behavior from a more com­ plex model. The simple model must be a fitting approxi­ mation of the more complex model, that is, the complex model must have an independent variable, such that, when this parameter is taken to a certain approxima­ tion limit, the RVs of the shared variables become II· By constructing fitting approximations, the inter-model CA problem can be reduced to an intra-model CA problem.

The method's applicability thus depends on the op­ portunity to formulate a fitting approximation, which is not always possible (e.g., in the cascaded-tanks ex­ ample) . In addition, the implementation of the model sensitivity approach solves the resulting intra-model CA problem by DQ analysis. Unlike CEC*, DQ analysis ter­ minates when .confronted with ambiguities and can only reason in one direction through the OPC structure.

6 Conclusions

CEC* is an implemented method for predictive and di­ agnostic comparative analysis that is able to deal with intra-model and inter-model problems within a single framework. The constraints it uses in RV propagation have a solid mathematical foundation. This makes it possible to proof CEC*'s soundness and incompleteness.

3 RSIM+ [Neitzke and Neumann, 1994] allows for a modest inter-model CA feature, namely differences in the monotonic­ ity of functional relations.

Further work on CEC* concerns improvements upon the derivation of RV constraints from the models of the systems, especially those relating state variables across pairs of comparison. If the qualitative models and be­ haviors are extended to include quantitative information, a form of semi-quantitative comparative analysis could be considered as well.

Acknowledgments The authors would like to thank B. de Jong, N. Mars, P. van der Vet, and H. Zwart for their contributions.