Change, Change, Change: Three Approaches

1 The Frame Problem

Reasoning about change is central to much of common sense reasoning. To reason about change we clearly need to represent what changes after an action is completed. What is not so immediately obvious is that we also need to allow the reasoner to infer what does not change after an action. The simplest way to specify what changes and what does not would be to write each set down. However this seems wasteful , and worse, seems likely to introduce inconsistencies. It seems clear that just specifying what changes is sufficient- everything else doesn't change. We can generate the properties that do not change from the list of properties that do change. If we do this we are guaranteed that our lists will be consistent. Moreover, usually fewer things change than don't change, and thus we will have much less to specify.

The idea that we need specify just the positive in­ stances of change has given rise to a problem: How do we generate all the instances of properties that stay the same? This is how I formulate the frame problem.

Since its inception the frame problem has mutated. Some people view it as the problem of correctly deter­ mining the consequences of a set of sentences describing some changing domain. This might include concurrent, nondeterministic, under-specified or continuous actions. We do not deal with this extended notion here.

We do keep in mind one modification to the origi­ nal statement of the frame problem. We do not just want to encode the things that change and don't change compactly, we also want to be able to add new changes by adding new sentences. This requirement forces us to use some non-monotonic reasoning. This require­ ment is called elaboration tolerance[Costello , 1997a] by McCarthy[1992] .

1.1 The Situation Calculus

To look at the frame problem we need a logical language to represent time, events, and the properties that hold in the world. We propose to use the situation calculus, a formalism for reasoning about events in the world. The paper that introduced situations [McCarthy and Hayes, 1969] defined them as follows , "A situation s is the com­ plete state of the universe at an instant of time". The basic mechanism used in the calculus to define a new situation is the result function,

In this formula s is a situation, and e is an event, and s' is a new situation that results when e occurs. A function or predicate of a situation is called a fluent.

1.2 Frame Axioms

As we mentioned earlier, a certain problem arises when we formalize domains in this language. Assume there is an axiom that states what happens to the location of a block when an action move is performed.

Sentences of this form are called effect axioms. If an­ other property, colour, is added, the axiom which de­ scribed what effect the action had on the location does not give us any information on what happens to the new fluent colour. The usual intent is that the new fluent remains unchanged by the action, but this is not always the case. To specify that the colour of the block does not change we must write:

To express all the fluents that do not change, an axiom would be needed for each action/fluent pair. These ax­ ioms stating that fluents do not change are called frame axioms. Having to specify all this lack of change seems extravagant, and more importantly it seems unnecessary to have to write these out individually. It seems that it should be possible to generate these frame axioms auto­ matically. The frame problem is the problem of charac­ terizing these frame axioms.

1.3 Plan of Paper

We first define the situation calculus and circumscrip­ tion, the language and non-monotonic framework we consider. A fuller exposition of these can be found in [McCarthy and Hayes, 1969] and [McCarthy, 1986]. We then consider the projection problem. We give the pref­ erence on models that it suggests, and show that it is not naturally captured by circumscription. We show it is captured by a IT} formula, (that is a formula all of whose second order quantifiers. are universal) which is not in the form of circumscription.

Next we consider the causality assumption, that ac­ tions have as few effects as possible. We show that this cannot be captured by any circumscription policy.

We consider the "frame" assumption, that there are as many frame axioms as possible. We show that this can be captured by a form of circumscription that allows free predicate variables.

We then consider the various other proposals for cap­ turing these defaults that have been suggested. We show that causal reasoning, as proposed by Gelfond and Lifschitz[1993] corresponds to the causality assumption. We show that for a restricted class of theories, chronolog­ ical minimization corresponds to projection, and present a new counter-example, a simple theory, with only facts about the initial situation and disjunction of effects ax­ ioms , where chronological minimization does not give the correct results.

We show that for the restricted class where chronolog­ ical minimization applies, an explanation closure axiom is validated. This allows a deduction theorem which we can state as follows. Let Fproj give the consequences of the projection assumption, and Fcau·, the consequences of the causality assumption, that is minimal entailment under 5:proj and '5:cau· ' and let r be a theory axioma­ tized by effects axioms, t , t 1 , ... , t; be constant situation terms, F, ft, . . . , fn be fluent constants, for n E w,

This justifies the approaches of Sandewall, Lifschitz and others that have solved causal reasoning problems by dividing a theory in two , and applying projection type reasoning to a part, and re-conjoining the reserved sen­ tences.

2 The Situation Calculus

The situation calculus of order n, L,;t, is a language of nth order logic with equality, with three disjoint sorts: fluent names , actions, and situations 1 . It contains ex­ actly one predicate constant, holds, in addition to equal­ ity, one function constant result( a, s) which returns a situation, a function sit(g) from predicates of fluents to situations, and one situation constant SO, plus a set of fluent constants f, and a set of action constants a. When we wish to specify the action and fluent constants we write L,;t(f, a). We shall sometimes add a predicate ab(a, f, s).

3 Circumscription

Non-monotonic logics are logics where the consequences of a set of sentences are not necessarily consequences of supersets of that set of sentences.

This paper uses circumscription as its non-monotonic machinery. Circumscription is a form of non-monotonic logic introduced by McCarthy [1986]. It expresses the non-monotonic consequences of a finitely axiomatizable theory A in a language L, under a certain circumscrip­ tive policy, as a sentence of second order logic. A cir­ cumscriptive policy is a choice of a finite set of formulas of L to minimize

4 The Projection Problem

The projection assumption is the default th~t there are as few changes from one situation to the next as possible. The critical change between this assumption, and the naive approaches that fall victim to the Yale Shooting Problem, is that situations that differ on what fluents hold, before the action we consider, are not compared.

When we consider the set of changes that happen when an action occurs, it would not make sense if the two situ­ ations from which we measure have different properties.

1 We use s with primes and indices to range over situations, and a and f to range over actions and fluent names, and g to range over unary predicates of fluents.

Definition: 1

The ordering on models that models the assumption of the projection problem ~ defined as follows. Let 2t, 'B be two models of L,;1 (a, f) . We say 2t ~proj 'B, if for all situations s and R(a, s) = 2t(result(a, s)] and R'(a, s) = 'B(result(a, s)], where a E a, then

A possible criticism of this approach is that it does not count the extra changes that might be implied by domain constraints. This criticism is invalid, as for each other change that is implied by a domain constraint, there is another effect axiom that can be derived. Because we have stayed in the language of the situation calculus, we have avoided the problems with domain constraints that plague approaches that introduce new predicates.

Theorem: 1

The assumption of the projection problem is expressible in the IIi fragment of second order logic.

Proof: The following sentence is the required IIi sen­ tence.

There is no circumscription policy that captures the projection assumption in this language. This is shown in (Costello, 1997b], by showing that the filters of the partial order ~proj are not finitely first order axiomati­ zable.

However, if we extend our definition of circumscription to allow arbitrary sentences to describe the preference on models, then we can easily describe this preference. Lif­ schitz [1984] suggests the name general circumscription for minimal 611tailment where the preference on models is described by a first order formula.

Giunchiglia

Giunchiglia [1996] suggests a second order sentence, that is logically equivalent (modulo translation into a variant of the situation calculus) to the projection assumption we consider. He considers the same ordering on mod­ els, only comparing situations that agree on all fluents. This ordering on models has been considered by Lin and Reiter[1994]. They do not characterize it in second or­ der logic, rather they use a two stage translation with predicate completion .

5 The Causality Problem

Rather than minimize changes from one situation to the next , another approach is to minimize the effect~ that ac­ tions have. That is, we assume that all change IS caused, and then minimize the effects that each action causes.

To state that an action causes a change, we write an effect axiom, that is a sentence of the form,

for some particular P and N .

This states that if the fluents P hold, and the fluents N do not then the action a causes f to not hold. This can be w~itten in other ways, [Gelfond and Lifschitz, 1993] for instance, a causes ·f if {!'If E P}, {·!"If E , N}, or cancels( a, f, P, N). The meaning of these is intuitively the same as the effect axiom.

To state that all changes are caused we write an ex­ planation closure axiom.

We note that this is equivalent to,

That is, in this case it states that if a change occurs in a situation then it occurs in every situation where the same fluents hold. We shall later show that this axiom is naturally satisfied if there are no "observations".

Definition: 2

The ordering on models that models the assumption of the causality problem is defined as follows. We prefer models where actions have fewer effects. We can measure the effects of an action by the set of formulas of the forms:

Let ¢ range over formulas of these forms. Let 2t, 'B be two models of L·it· We say 2t ~catu 'B, if

We note that these models are assumed to obey the rule of explanation closure above.

Theorem: 2

The assumption of the causality problem is not express­ ible in circumscription.

Proof:

Circumscription does not compare models of differing cardinality, but to minimize universals it is sometimes necessary to enlarge the domain, adding a new object that witnesses the existential.

Consider the theory in L sit ( {A}, { F}), axiomatized by holds(F, SO) The non-monotonic consequences of this should include

However, in· any model where all situations are denoted by closed terms, the following will be satisfied,

Thus, to deny this effect axiom, we need to add a situ­ ation not denoted by any closed term. I

6 The "Frame" Problem

We now consider another assumption, one which to our knowledge has not been previously considered. We prefer models where there are more frame axioms true. This seems like a very natural approach. We first consider how to represent this assumption.

Definition: 3

The ordering on models that models the assumption of the frame problem is defined as follows. We prefer mod­ els where there are more frame axioms true. Frame for­ mulas are of the form, where N and P are sets of fluent constants:

Let ¢> range over formulas of these forms. Let 2t, ~ be two models of L,;t. We say ~ SJrame 2t, if

Theorem: 3

The assumption of the frame problem is not expressible in circumscription.

Proof: No finite set of first order sentences describes the same order on models as the infinite set of formulas described above.l

Theorem: 4

The assumption of the frame problem is expressible in circumscription, if we allow the minimized formulas to contain second order variables.

Proof: If we allow a unary predicate variable for fluents g the class of formulas above can be parameterized by g, as:

The circumscription formula is then,

I

To the best of the author's knowledge this approach, of preferring models where there are more frame axioms has not been previously considered.

7 Examples

We show, via examples, that each approach is distinct.

Example: 1

The first example concerns reasoning forwards in time. For simplicity we consider a language with only one ac­ tion A, and one fluent-name F. ·

We consider that a conclusion that should be drawn from this theory, if we assume the causality assumption lS,

In contrast the "frame" assumption will not entail this, as this does not add a new frame axiom. The only (non­ trivial) possible frame axioms are,

Thus the frame assumption will add exactly these two sentences, which do not entail the negation of the effect axioms above.

We mention for completeness that the standard exam­ ple for the distinction between projection and causality is the Stanford murder mystery, where both the causal­ ity and frame assumption give that the gun was loaded initially, while the projection assumption does not.

Example: 2

The first example concerns reasoning backwards in time. For simplicity we consider a language with only one ac­ tion A, and two fluent-names F1, F2. We are told that F1 holds at the second situation, result(A, SO). We are also told that F1 does not hold at the first situation. Finally we are told that A causes F1 is F2 holds.

The result of the projection assumption adds,

and 'v's.holds(F2 , s) holds(F2 , result(A, s)), while the frame and causality assumptions both gtve, holds(F2 , SO) in addition.

The causality assumption also gives the negation of the other effect axiom.

The causality problem has been addressed by Lin and Reiter[1994], Kartha and Lifschitz[1995] and Sandewall[1994] among others. We consider their ap­ proaches, and show how they attempt to avoid the result of the previous theorems.

8 Nested Abnormality and Filter entailment

Lifschitz and Sandewall suggest extensions to circum­ scription, or non-monotonic systems that are based around minimal entailment. Sandewall's systems [1994] are based on filter preferential entailment . Kartha and Lifschitz [1995] bases their system on nested abnormal­ ity theories[Lifschitz, 1995]. Both these formalisms have the property that they necessarily divide the theory they are non-monotonically completing into subsets, based on some syntactic property. In particular they divide obser­ vations from causal rules or effect axioms. However, if a causal rule is disjoined with and effect axiom this cannot be achieved. They then solve the projection problem, and conjoin observations to solve the causality problem.

Preferential Entailment

Sandewall uses the term filter preferential entailment to denote a type of semantic entailment. He imagines a case where we have a theory divided into two parts, f and fa. He divides the theory into two sets of sentences, so he can apply a selection function to one set, and then conjoin the other set to get the final theory. If ( is a selection function, that is it maps a set of models to a subset of those models, then the non-monotonic consequences of f and fa are f u ((fa) .

The primary intuition behind Sandewall's preference on models is similar in spirit to chronological minimiza­ tion. Changes occur preferentially later in time. We now show that our projection assumption can sometimes give the same results as chronological minimization.

In the case of temporal projection, when we do not have facts about the initial situation, and where we have only effect axioms and domain constraints, the same re­ sults can be achieved by not comparing situations that differ, as we earlier propose. Not comparing situations that differ on what is the case seems obvious. Apples should not be compared with oranges.

A domain constraint is a sentence in L,;t whose only situation terms are universally quantified variables. A binary domain constraint is a formula of the form, 'v's.(..,)holds(f,s) -t (..,)holds(f',s), for fluent constants f and f'.

Theorem: 5

Given a theory T in L,it , axiomatized by binary do­ main constraints and effect axioms, which do not entail any domain constraint not equivalent to a conjunction of binary domain constraints, then the result of the pro­ jection assumption is equivalent to putting off change as long as possible (chronological minimization).

Proof: We first note that the axiom of explanation clo­ sure is validated under both assumptions.

Secondly we see that for a given model 9J1 and a situ­ ation s, by explanation closure, we can determine what holds in the following situations by looking that the ini­ tial situation, in some model 9J1', where the fluents that initially hold in 9Jl' are the same as hold at situation s in 9Jl. As we have only effect axioms and binary domain constraints, there will always exist such a model.

Thus it suffices to look at only one step of projection. However, when we just do one step, we minimize change in both cases. I

Nested Abnormality Theories

Lifschitz in [1995] suggest a very similar idea to Sande­ wall's. Rather than describing the idea in semantic terms, Lifschitz uses the notation of circumscription.

He divides his theory into several parts. To each part he applies a circumscription. He does this uniformly by defining the predicate ab, of an appropriate arity to be predicate to be minimized. All predicates are varied by default .

"Deduction Theorems"

To a large extent both of these approaches attempt to solve the problem of causality by solving the projection problem, and then adding back certain facts. This is why they need to be able to syntactically divide theories into two sub-theories.

We now prove a theorem showing that solving the pro­ jection problem for theories without observations, and adding observations is equivalent, for closed situation terms, to solving the causality problem. A similar theo­ rem can be established for the frame assumption.

Theorem: 6

Let T be a theory in L,;t, that is axiomatized by ef­ fect axioms and binary domain constraints, where every domain constraint in T is equivalent to a conjunction of binary constraints. Then, if t is a constant situation term, and t1, ... ,tn, F,ft, ... ,Fn, nEw are constant situation terms and fluents,

T Fproj 1\i<n holds(ft, t;) -t holds(!, t) if and only If T, {holds(!;, t;) li En} FcatH holds(!, t)

Proof

All consistent theories T axiomatized by effect axioms and binary domain constraints are consistent with the statement of explanation closure, subject to the above proviso. As minimal entailment is cumulative, thus we may add explanation closure to the left hand side.

We then prove the above claim by induction on the size of the t 's. If they are all SO, then the implication its true only if it is an instantiation of a binary domain constraint , and thus the equivalence holds.

But , then we see that (Vf.holds(f, t) = g(f)) 1\ ·holds(F, t) --+ holds(F, result( a, t)), is equivalent to Vs.(Vf.holds(f, s) = g(f)) 1\ ·holds(F, s) --+ holds(F, result( a, s)), explanation closure. This gives us the induction step to prove the above claim. I

Thus the approaches of Kartha and Lifschitz, and Sandewall, which claim to do causal reasoning, are in fact doing temporal projection. They simulate causal reasoning because for the class of problems they con­ sider, the above theorem applies.

8.1 Lin and Shoham's Approach

This approach quantifies over circumscription. They take the consequences of a theory to be the intersection of the consequences of a set of circumscriptions. Lin and Shoham [Lin and Shoham, 1995] suggest a solution that again returned to minimizing the total amount of change, but they suggested that this should be minimized one sit­ uation at a time. For every situation, and possible set of ftuents that could hold at that situation, they calcu­ late what the minimal amount of change between that situation and its successors could be. They then add the conditional that if those ftuents held at the situation, then the successors will be exactly those that have mini­ mal differences. The major drawback with this approach is that it can become inconsistent when given disjunctive information. However, Lin and Shoham show that it be­ haves correctly for a limited class of theories, essentially those where what holds in the·initial situation uniquely determines what is holds in all later situations.

9 Conclusion

We considered three distinct defaults about temporal reasoning. The first, projection has been considered be­ fore by Lin and Reiter, and Giunchiglia. The ~econd, minimizing the effect axioms that hold, corresponds to causal reasoning. This has been considered semantically by many researchers. We show for the first time that this cannot be captured by circumscription, as it compare models with different cardinalities. The third method, maximizing the set offrame axioms is novel, but perhaps is the most natural.

We established deduction type relationships between these approaches, explaining why current approaches that divide theories into parts behave as they do. We gave conditions for when applying projection reasoning, then adding observations, is equivalent to causality rea­ soning.

A more comprehensive survey is given in [Costello, 1997b]. However, to the best of the author's knowledge, all previous approaches either attempted to minimize change (chronologically), or minimize causality.

10 Acknowledgments

This research is supported in part by ARPA/Rome Lab­ oratory planning initiative under grant (ONR) N0001494-1-0775. I am grateful to John McCarthy and Anna Patterson who gave useful criticism on earlier drafts .