The Logic of Occurrence

I. Introduction

A goal of qualitative physics is to predict the behavior of physical systems. One technique, envisioning, gener­ ates all possible behaviors of a system, relative to a par­ ticular set of background assumptions. Informally, any specific behavior of a system (a history) corresponds to a path through the system's envisionment, and vice versa. This correspondence is essential to using envisionments. For example, interpreting measurements can be viewed as constructing a correspondence between a (usually partial) history and an envisionment. However, the correspondence between histories and envisionments has never been ade­ quately formalized.

Formalizing this relationship has two benefits. First, it provides additional grounding for theories of measure­ ment interpretation and diagnosis (such as [7, 41) Second, we use the formalization to generalize existing domain­ specific algorithms for inferring the consequences of as­ sumptions about behavior. The problem is this: Any as­ sumptions we make about a system's behavior (or any ad­ ditional information we obtain concerning it) restricts its possible behavior in the future. For example, in engineer­ ing design we might assume that a boiler's rupture pressure is never reached or that the water level inside it never goes above a particular height. Alternately, if we are observ­ ing a moving object then we might be able to calculate its initial energy, and thus place bounds on its location. In

. each of these cases a particular subset of behavior is di- The following section describes the logic of occurrence, introducing registrations to represent the relationship .be­ tween envisionments and histories. The axioms for infer­ ring additional consequences of behavioral assumptions are also presented. These concepts are sufficiently general to apply to any system of qualitative physics. Next, we de­ scribe a form of Zeno's paradox which plagues qualitative physics, and propose transverse quantities as a general, domain-independent solution. Section IV. illustrates the utility of this logic by a rational reconstruction of FROB's algorithms. Section V. discusses further implications and plans for extensions.

II. Theory

We begin by introducing formal definitions for certain as­ pects of envisionments, qualitative states, and histories. Next, we describe the concept of a registration, a mapping between an envisionment and a history. We then describe the relationships between occurrences of states, including axioms which can be used to derive the consequences of assuming that some states must (or must not) occur.

A. Preliminaries

Definition 1 (Envisionment) An envisionment c rep­ resents all possible qualitative states a particular system may take on and all legal transitions between them. The function States : [ ---+ {states} maps from envisionments to the set of states it contains.

For generality we assume as little as possible about the nature of qualitative states. We assume that each quali­ tative state can be described by a finite amount of infor­ mation. Ergo, qualitative states may be tested for identity with finite computational effort 1 · Furthermore, we assume that all states in an envisionment are fully defined with re­ spect to whatever physics and domain model was used to generate them. In other words, the descriptions of states do not contain unbound variables. Aside from the ability to tell if two states are the same, for our present purposes the only properties we need to talk about are the transi­ tions between them.

Definition 2 (Transition functions) The functions Be/ores : s --+ {states}, Alters : s --+ {states} describe all transitions involving a state s. State s; E Befores(s) exactly when the envisionment contains a transition from s; to s . State s; E Afters(s) exactly when the envision­ ment contains a transition from s to s; .

Two special cases surface repeatedly when thinking about envisionments. The first are states whose Befores is empty, what in automata theory are sometimes called "Garden of Eden" states. The second are states whose Afters are empty, which represent states the system re­ mains in forever.

Definition 3 (Eden states) A state as Eden exactly when Befores(S;) = {} .

Definition 4 (Final states) A state S; is Final exactly when Afters(S;) = {}.

An envisionment compactly represents all possible his­ tories (up to some resolution) . If the envisionment is cor­ rect, every possible history of the system corresponds to some path through the envisionment and vice versa. Paths are defined to be a continuous chain of behaviors through the envisionment:

Definition 5 (Paths) A Path is a sequence of states St. ···, sn such that s;+1 E Afters(s;). Single states are also paths. The functions PathStates, PathStart, and Pa­ thEnd map from a path to the set of qualitative states which comprise it, the first state, and the final state, respectively. The term paths(c) denotes all the paths in the envision­ ment.

That is all we need to say about envisionments. For histories we assume the notational machinery in [8, 6]. Specifically, we assume a history )I is composed of episodes and events which are temporally extended and spatially bounded. Except for determining state identity, we will ignore durations and hence usually just speak of histories as being composed of episodes (we assume the function Episodes maps from a history to the set of episodes which comprise it) . Since our logic is designed to specify the reasoning of a finite agent, we assume that histories are generated, either by a physics or by observation, and are finite. The function FinalEpi sode maps from a history to the temporally last episode generated so far .

Unlike state descriptions in envisionments, we allow partial descriptions of episodes to model reasoning with Figure 1: An example of reasoning about occurrence Part (a) ahowa a typical FROB scenario. Given a. diagram, FROB com­ putes a qualitative descripUon of free space. A ball is placed as shown and given an initial velocity. Part (b) (left) shows FROB's initial en­ viaionment, baaed only on assuming that the ball is in SRO. Part (b) (right) ahowa the envisionment pruned to reflect the consequences of various additional assumptions. Each arrow and circle depicts a po­ tential qualitative state of the ball (see )5) for details) . The additional usumptiona are shown in FROB's answers below. The only quantita­ tive information used wu the initial position and velocity of the ball in using energy constraints to calculate the maximum height the ball could reach. All other conclusions are based solely on qualitative in­ formation. A query session with FROB has been hand-translated into an Engliah "dialog~ for clarity.

1 This rules out elements of !R as constituents of a. qualitative state.

• Q: Why can't the ball leave the diagram going to the right?
• A: Because you assumed the ball would pass through S31 going left and up.

Q: Why can't the ball leave the diagram out the top?

• A: Energy.
• Q: Why can't the ball reach 811?
• A: Becauae you assumed it could not pus through 841.

incomplete data. We need a way to say that an envision­ ment state (which is generic) is the description of a partic­ ular episode of a history. To maintain generality we must take the matching operation as a primitive, and introduce a primitive to express its results:

Definition 6 (ConsistentWith) ConsistentWith(e,s) is true -whenever ep1sode e describes behavior of the sys­ tem that is not inconsistent -with state s.

If in some application more information can be gathered about the physical system, then conclusions of ConsistentWith can be non-monotonic. We relegate these control issues to programming, where they belong. We further define the set of P /nterps, the possible interpre­ tation of an episode e, to be the set of states s such that ConsistentWith(e,s) is true. P/nterps are central to the ATMI theory of measurement interpretation; see [71 for details.

B. Registrations

Intuitively, a registration is a mapping which relates a his­ tory to an envisionment by identifying episodes in the his­ tory with corresponding states in the envisionment. The concept of a registration has been used informally in most work in qualitative physics ([3, 6, 9, 111, but has never been adequately formalized. To define registrations we must first be able to say that an episode represents the occurrence of a state:

Definition 7 {OccursAt) Given s E States(£), e E Episodes(JI), OccursAt(s, e) is true exactly -when the state s represents -what is happening during e.

Clearly OccursAt is stronger than ConsistentWith, since a partial specification of e will allow it to match sev­ eral states, even though only one state (or path of states, see below) is what actually occurs. The next axiom en­ forces this intuition:

Axiom 1 {OccursAt Consistency) Vs E States( C) VeE Episodes(JI) [OccursAt(s, e)~ ConsistentWith(e,s)l

Collections of OccursAt statements are the building blocks of registrations.

Definition 8 (Registration) A registration R of a his­ tory )I -with envisionment t consists of a set of OccursAt statements {denoted Occurrences(R)).

The next axioms ensure that registrations correspond to paths through the envisionment. Allowing partially specified episodes means that a path of qualitative states may occur within a given episode, since the properties which distinguish the individual states may not be appar­ ent from the history. Another complication arises if we allow the history to have temporal gaps. In the simplest case where two episodes meet, the accuracy condition is:

Axiom 2 (Neighbor accuracy)

V e1,e2 E Episodes(JI) [Meets(e1,e2) ~ j PI, P2 E paths( C) s. t. [\fs; E PathStates(pt) [OccursAt(s;,e t) E Occurrences(R) I 1\\f Sj E PathStates(p2) [OccursAt(.~j, e2 ) E Occurrences(R) I 1\V Sj EStates({) [OccursAt(sj,et) E Occurrences(R) ~ Sj E PathStates(pt) I 1\ V Sj E States(£) [OccursAt(sj, e2) E Occurrences(R) ~ Sj E PathStates(p2) ] 1\PathEnd(pt) E Befores(PathStart(p2))]

Accuracy across gaps simply means that there is some path through the envisionment that serves as a "bridge" between the (possibly singleton) paths which represent the episodes before and after the gap:

Axiom 3 {Gap accuracy) 1;1 et. e2 E Episodes(JI) [-.3e3 E Episodes(JI)s .t.Between(e3, e1 ,e2) ~ 3 Pt.P2 E paths(£) s. t . [Vs; E PathStates(pt) [OccursAt(s;,et) E Occurrences(R) I 1\ 1;1 Sj E PathStates(p2) [OccursAt(sj,e2) E Occurrences(R) I 1\V Sj EStates(£) [OccursAt(sj,et) E Occurrences(R) ~ Sj E PathStates(pt) I 1\ \f Sj E States(£) [ OccursAt( Sj, e2) E Occurrences( R) ~ Sj E PathStates(p2)1 /\[3 P3 E paths(£) [PathEnd(pt) = PathStart(p3) I\ PathStart(p2) = PathEnd(p3) IIJ

The concepts introduced up to this point suffice to provide the grounding for theories of measurement inter­ pretation and diagnosis which must relate histories to en­ visionments. Next we examine how to use registrations to generate expectations about the future.

C. Constraining the future

To an agent observing a system, a registration represents what has gone on so far. Knowing what has happened constrains the future. Other constraints on the future in­ clude quantitative information and assumptions, as men­ tioned above. Since the envisionment already contains all states and transitions possible without these assumptions, their only effect will be to exclude other states from occur­ ring. Essentially, the envisionment is "pruned" to reflect the fewer models possible with the additional information.

First we need a bridge from what we know about the history to the future. The function lnitialStates maps from registrations to the set of envisionment states which are the end of the known history.

Axiom 4 (Definition of InitialStates) 7 s EStates([) ~ s E /nitialStates(R) ~ OccursA.t(s, FinalEpisode(}l)) E Occurrences(R) J

We require at least one starting place, but allow more than one to allow reasoning with partial information:

Axiom 5 (InitialStates Existence)

InitialStates(R) I~ 1.

D. Expressing Occurrence assumptions

Now we must provide a vocabulary for expressing the con­ sequences of external constraints on states in a form that can be used to constrain envisionments. Several forms of external constraints have already been explored in qual­ itative physics, including explicit user assumptions, con­ sequences of additional data (e. g. numerical simulations, energy constraints in [5]), and measurements [7]).

No matter what the source of data, a few simple dis­ tinctions suffice for our purposes:

Axiom 6 (Status of states) Consider a registration R involving envisionment t. For every state s EStates(£), exactly one of the following is true:

Intuitively, Possible(s, R) means that s represents a be­ havior which the system may undergo during some episode of the history. Excluded(s, R) means that the behav­ ior represented by s will never occur in the history, and Required(s, R) means that the behavior represented by s must occur. 2 We now add to each registration a (possibly empty) set of Excluded and Required statements, called its ConstraintSet. All that remains is to specify the conse­ quences of these occurrence assumptions.

E. Consequences of Occurrence assumptions

A central fact of occurrence is that to be in some state, you either have to start there or get there. We need to refine the notion of paths to include the notion of a legal path:

Axiom 1 (Path legality) A path p is legal w. r. t. R when no state on it is excluded, i. e. ,

One state is attainable from another when there is a legal path of non-excluded states between them.

2 1t is easy to extend this logic to include &qwred and Euludtd for transitions as well.

~ow we can express the intuition we were aiming at:

Axiom 9 (Reachability)

'<Is E states(t) [[ ·3si E lnitialStates(R)s. t. AttainableFrom(s, si) J => Excluded(s, R) ] ·

This axiom expresses what we mean, but a local ver­ sion is often useful in algorithms. A trivial consequence of this axiom is that a non-Eden state is excluded unless at least one of its Befores is not excluded (otherwise, it cannot participate in any legal non-singleton path, much less one from an initial state).

Importantly, if there are cycles in the envisionment - and there usually are - then the local version is incom­ plete (see Section 4).

Attainability is a fairly natural concept. Just as im­ portant, but less intuitive, is the idea that behaviors must have consistent continuations into the future. The slip­ periness of this idea comes from two sources. First, while all histories have an initial state (or states) by declaration, some behaviors can potentially go on forever (such as oscil­ lations). This means we cannot simply use attainability of final states as a means of pruning, for we would be ruling out legitimate behaviors. Second, we must be careful to rule out qualitative versions of Zeno's Paradox. This issue will be detailed in the next section. Here we focus on the principle of good continuation.

Good continuation means that , unless the state is a final state, the behavior it describes will end at some time. When it does, one of the behaviors in its Afters must represent the behavior which occurs next (since e is as­ sumed to be complete) . If every state in Afters is already excluded, then that state cannot occur. The next axiom captures this intuition that, if further episodes are possible, then one of those possibilities must occur.

Axiom 11 (NoFuture law) Unless .s is a final state,

Consider an agent reasoning about a history }I being observed in real time. An agent with finite capabilities will only know a finite portion of the object's history. If the agent had a total envisionment describing the possible behaviors (or constructed the relevant parts on demand).

using the ATMI theory to construct a registration will pro­ vide an explanation of the history. Furthermore, any states which have been excluded from the envisionment (or frag­ ment thereof) by the axioms above cannot ever appear in any extension of the current history. This gives the agent a set of expectations: If any excluded behavior shows up in future observations, then either the constraints imposed on the behavior, the observations, the domain model, or some combination of these, are wrong.

Consider the projection € Jl of € to be the subset of states and transitions of € which are not excluded under Jl, (i.e. , a transition is inclqded only when the states before and after are not excluded). Clearly I e Nl ~I e I' since as Jl grows there are more constraints on €. The possibility of equality arises because some of the constraints may be redundant.

III. The Qualitative Zeno's Paradox

A problem lurks in the concept of continuation introduced above. The NoFuture law, like Axiom 10, is local. It turns out that local laws laws are insufficient to capture our intu­ itions about good continuation of action. Essentially, pro­ grams using the logic described so far fall prey to a form of Zeno's Paradox. Consider the situation in Figure 2a. A ball is bouncing up and down, heading left. We assume the ball never reaches the wall, and that the ball is per­ fectly elastic so that it doesn't stop. Any reasoning engine based on the logic of occurrence presented so far will think this kind of behavior is ·perfectly reasonable, even though it violates common sense. The problem is not peculiar to motion: Consider now Figure 2b. Suppose there is friction between the block and the table. Then the amount of energy each cycle will be less, and eventually it will stop 3 . But if we exclude the possiblity of the block stopping from the envisionment, the NoFuture law will not detect a prob­ lem because each state in the cycle has another element of the cycle in its Afters! Some oscillations can last forever (at least ideally), so we cannot. simply define the problem away. A non-local. technique must be used to avoid the Qualitative Zeno's Paradox (hereafter QZP).

To express the pruning conditions we must introduce an abstraction that will cover both the leftward motion of the ball and . the energy of the mass-spring combination:

De fin it ion 9 (Transverse quantities) A transverse quantity T with respect to a cycle C in € is a property of the envisioned physical system such that:

1. T exists for every state in C.
2. T has a constant upper (alternately: lower) bound.

3 See ~61 for how this can be proven in QP theory. Advocates of clusical continuity in qualitative physics (e. g. (2, lll will claim that the block indeed never atopa. We prefer here to model the common intuition, aince cluaical continuity leada directly to Zeno'a paradox .

Figure 2: The Qualitative Zeno's Paradox Reasoning about occurrences is subject to a form of Zeno's paradox. Consider these scenarios:

• (a) A perfectly elastic ball is bouncing up and down on a horizontal surface, heading towards the wall on the left. Assume it cannot reach the wall.
• (b) Friction is acting between the sliding block and the table. Assume that the combination never stops.

In both cases the assumption at the end makes the behav­ ior intuitively implausible. Yet the logic presented so far will not see these as problematic.

(a)

1. T is increasing {alternately: decreasing) over the cy­ cle.

If a T can be identified for some cycle C, then we can avoid Zeno's paradox by forbidding C whenever all states corresponding to leaving the cycle (some of which will represent T reaching its limit point) are excluded. Let Exits( C) be the set of exit states (i.e., the union of the A.fters for all s E C minus the cycle states themselves).

Axiom 12 ( Zeno) For all cycles C with a transverse quantity,

Careful application of this law avoids QZP. The next section illustrates.

IV. Reconstructing FROB

Here we show how FROB's ability to reason about occur­ rences, illustrated in Figure 1, can be understood in terms of these ideas. Given the history ){ known so far and a set of constraints concerning a ball's possible histories, FROB finds what possibilities are ruled out by these assumptions. In FROB's domain there are four types of behavioral con­ straints:

Requirements: The user can assume certain states must occur, or a ball must be in particular places, sometime in its future. As ){evolves the set of requirements may shrink, since some new episode may satisfy a required state.

Exclusions: The user can assume that certain states must not occur, or that a ball cannot ever be in particular places. Excluding a place causes all states including that location to be excluded.

·Elasticity: If a ball is assumed perfectly elastic then states corresponding to the ball stopping are excluded. If the ball is assumed perfectly inelastic then states corresponding to the ball flying away from a surface after a bounce are excluded.

Energy: Given a quantitative position and velocity, FROB calculates the maximum height it could reach. If a place is completely above this height, then all states including that location are excluded.

Figure 3 outlines the algorithm. In FROB's domain envisioning is cheap, so a new envisionment is computed which just contains those states attainable from the end of the current II. Initially all states are assumed possi­ ble (step 2). The direct consequences of the behavioral constraints are added. and then pruning algorithms are applied repeatedly until no more states are excluded.

The algorithms used in pruning are much like those Jsed for "garbage collection~ in computer languages which Figure 3: FROB's algorithm for reasoning about occurrences

1. Generate new attainable envisionment c from FinalEpisode(){).
2. For all states s, mark Possible.
3. For each s directly-excluded by constraints, mark Excluded.
4. Until no further states are pruned,
5. Use local pruning rules (Figure 4).
6. Prune unreachable states (Figure 5) .
7. Prune QZP cycles.
8. If initial state is excluded, signal error.

Figure 4: Using local laws to prune states This algorithm uses the NoFuture and NoPast laws to prune states without good continuations and those which cannot be reached from the initial state(s). Cycles are handled seperately.

1. Let Q ={states(£)}.
2. Until Q empty,

2.1 s = Pop(Q)

2.2 If Excluded(s, R) V Final(s), ignore.

Otherwise, if every s; E Afters(s) is Excluded,

1. Marks as Excluded.
2. For every s; E Befores(s), If s; E Q V Excluded(s;, R) then ignore. Otherwise, Push(s;, Q).

2.3 If Excluded(s, R) V s E lnitiaiStates(R), ignore.

Otherwise, if every s; E Befores(s) is Excluded,

1. Mark s Excluded.
2. For every s; E Afters(s), If s; E Q V Excluded(s;, R) then ignore. Otherwise, Push(s;,Q) .

allow dynamic allocation of memory. Step 4. 1 provides lo­ cal pruning via the NoFuture and NoPast laws to quickly get rid of states which are obviously ruled out (see Figure 4). This lltep is essentially a "reference. count" garbage collector, using the number of possible bef ores and afters to determine whether a state is to be excluded. Just as reference count algorithms fail to work with circular stor­ age structures, this step will fail to detect cycles which are excluded. Step 4. 2 applies reachability (axiom 9) to remove these cycles (see Figure 5). This algorithm also keeps track of what required states are accessible through each state, so that states which do not allow all required states to occur can be ruled out. Step 4. 4. enforces axiom :;.

To apply the Zeno axiom, FROB identifies places where such oscillations might occur along with the correspond­ ing transverse quantity. If the oscillation is UP/DOWN the transver~e quantity is motion in the LEFT or RIGHT direc- Figure 5: Finding unreachable states and imposing re­ quirements This algorithm is complicated by the need to exclude those r,"' states which do not allow every required states to be reached. Call the set of required states R. Each state s will have an associated set R,, representing the required states found before or after it on some path, and a bit mark to indicate whether or not the state was reached on the search (in case R = {}).

1. For each s E InitialStates(R), MarkRequired(s, {}, {}).
2. For each s Estates(!), 2.1 If mark(s) = 0 marks Excluded. 2.2 If R, ~ R, mark Excluded, with reason being R- R,.

Procedure MarkRequired(s,path, so far)

1. If s Excluded, ignore.
2. mark(s) +- 1
3. If s E R, 3.1 For every s; E path, R,, +- s u R,, 3.2 so far+- s U so far.
4. R. +- sofar U R,
5. For every s; E Afters(s), MarkRequired(s;,s U path,sofar)

tion, and if the oscillation is LEFT/RIGHT the transverse quantity is motion in the UP or DOWN direction. The cycle in each place involving a transverse quantity 4 is examined in step 4. 3 to see if either (a) the ball may stop, (b) it can leave the place, or (c) if the transverse quantity can reverse direction (i.e. bouncing around inside a sealed box. If any of these are possible the cycle is okay, and otherwise it is pruned to avoid QZP.

V. Discussion

This paper has .Presented a formal logic of occurrence, to capture the relationship between histories and envision­ ments and to provide the ability to reason about the con­ sequences of behavioral assumptions. It should be appli­ cable to any system of qualitative physics, since it makes very few assumptions about the details of the underlying physics.

While the specific algorithms described above require the ability to explicitly construct envisionments, these ideas can be used without explicit envisionments. One possibility is to generate a subset of the possible behaviors, using these laws to guide backward chaining. · Another is to prove general statements about classes of physical behavior, in the style of argument used in classical thermo­ dynamics. We are exploring both styles of reasoning.

4 :-lot every cycle is subject to QZP - a perfectly elastic ball bounc­ ing straight up and down on a horizontal surface will bounce forever.

We are also applying these algorithms to envision­ ments involving Qualitative Process theory. The imple­ mentation is taking the form of a post-processor to QPE, our new QP implementation which generates total envi­ sionments. The major unsolved problem is automatically detecting transverse quantities. One avenue is to simply declare them - energy, after all, is the typical choice. An­ other possibility is to extend Weld's aggregation technique [10J to extract transverse quantities as a side-effect of the cycle summarization procedure.

VI. Acknowledgements

This work benefitted from conversations with Dedre Gen­ tner, Dennis DeCoste, and Brian Falkenhainer. This re­ search is sponsored by the Office of Naval Research, Con­ tract No. N00014-85-K-0225.