Dependent Fluents

1 Introduction

This paper is about the ramification problem in the the­ ory of commonsense reasoning, that is, about the prob­ lem of determining the indirect effects of an action. More specifically, we are interested in what Myers and Smith [1988] called the persistence of derived information- in deciding whether the indirect effects of an action should be presumed to persist, or, in other words, whether they are subject to the commonsense law of inertia.

Compare two examples:

Example 1 [Crawford, 1994]. If you are in the lake then you are wet. Jumping in the lake has an indirect effect-getting wet.

Example 2 [Myers and Smith, 1988]. If an object is on the table then it is not dangerous for the baby crawling on the floor. Putting an object on the table has an indirect effect- making it safe.

The examples look similar. Consider, however, what happens in each case if the action under consideration is followed by an action with the opposite effect. After you get out of the lake, you are still wet; this conclusion can be justified by the commonsense law of inertia. After an object is removed from the table, there is no guarantee

Vladimir Lifschitz

Department of Computer Sciences

University of Texas, Austin, TX 78712, USA Email: vl@cs.utexas.edu

that it is still safe from baby. Moreover, if we know that originally the object was not safe, and that now it is returned to the old location, then common sense tells us that it is definitely not safe. Somehow, the law of inertia does not apply.

The ramifications similar to Example 1 are by now well understood. Formal accounts of this case of the ramification problem, in various contexts, were given in [Ginsberg and Smith, 1988], [Winslett, 1988], [Baker and Ginsberg, 1989], [Baker, 1991], [Lifschitz, 1991], [Lin and Shoham, 1991], [Kartha and Lifschitz, 1994]. In the more difficult case of "noninertial ramifications," illustrated by Example 2, little progress has been made. Myers and Smith [1988] identified the problem, gave a few in­ structive examples and sketched an approach based on default logic. But their paper does not contain an actual formalization of any of the examples.

In Section 2, we present a new informal analysis of noninertial ramifications. This discussion leads us, in Section 3, to a high-level syntax, similar to the one used in [Gelfand and Lifschitz, 1993] and [Kartha and Lifs­ chitz, 1994], that distinguishes between the two kinds of ramifications, and then, in Section 4, to. an action language that allows us to formalize both Example 1 and Example 2. The new language extends the ac­ tion language AR from [Giunchiglia et al., 1994] and is called ARD- for Actions, Ramifications and Depen­ dencies. The properties of ARD are investigated in Sec­ tion 5.

2 Dependencies

There is nothing peculiar about the fact that some flu­ ents are "inertial" and others are not. For example, the law of inertia is often restricted to "primitive fluents" and is not applied to their propositional combinations in [Myers and Smith, 1988] and [Baker, 1991]. Several examples when fluents change "by themselves" are given in [Lifschitz and Rabinov, 1989]. In [Lifschitz, 1990], a subset of fluents is designated as a "frame," and a fluent is assumed to be inertial only if it belongs to the frame.

But if we simply declare the fluent Safe(x) noninertial, then any action will be able to affect its value, even the trivial action Wait. Common sense tells us that this fluent can be affected by an action if that action affects the location of x, but not otherwise.

It appears that Safe(x) is similar in its behavior to the noninertial fluents that have an explicit definition in terms of the location of x, except that we do not know what this definition is. If the top of the table is one of n possible locations of x then we are free to assume about any of the other n -!locations that, being there, x would or would not be safe. There are 2n-l possible "functional dependencies" between Safe(x) and Location(x), and we seem to implicitly assume that one of them holds, without specifying which one.

In connection with a similar example, Crawford [1994] writes:

If we want derived consequences not to persist then we probably have to rethink our approach to developing semantics. The problem is that the persistence of fluents now seems to depend on their history-how they came to have the value they now have. As far as I know no cur­ rent approaches allow this.

Indeed, traditional approaches to the semantics of ac­ tions have a "Markov property" 1 which can be infor­ mally described as follows: If the current values of all fluents mentioned in the problem are completely speci­ fied then no additional information about the values of these fluents in the past will allow us to make additional predictions about their future values. (This concept will be made precise in Section 6.) In Example 2, assume that all objects under consideration are currently on the table, and consequently safe. Then we know the current values of all fluents Location(x) and Safe(x). There is no way to decide on the basis of this information whether HeavyHammer will be safe after we put it on the floor. But if we assume, in addition, that at some point in the past HeavyHammer was on the floor and was not safe, then we can predict that the fluent Safe(HeavyHammer) is going to change its value. We see that a formalism with the Markov property would not allow us to represent the Safe example.

The idea of a (possibly unknown) dependency out­ lined above seems promising because it can give rise to "non-Markovian" formalisms. From this perspective, the state vector of an action domain includes both "ex­ plicit'' components-the values of the fluents available in the language-and an "implicit" part, the dependencies that characterize the dependent fluents. This implicit part of the state vector does not change as the actions are performed, but it can affect the values of the tran­ sition function of the system. Additional information about the past can be used to learn the values of the implicit components, and consequently to arrive at new predictions.

3 Formalization of the Examples

Example 1 can be easily represented in the language AR [Giunchiglia et al., 1994], or even in its dialect ARo from [Kartha and Lifschitz, 1994]. An ARo language is char­ acterized by a set of "action names," such as Jumpln and JumpOut, and a set of "fluent names," such as InLake and Wet. Some fluent names are designated as "inertial" (or forming a "frame"); in this example, both InLake and Wet are inertial.

1 This terminology is suggested by a vague analogy with Markov chains in the theory of probability.

The condition if you are in the lake then you are wet and the effects of the actions can be represented by the following "domain description":

The first line of (1) is a "constraint"; the other two lines are "effect propositions."

According to the semantics of AR0 , description (1) represents a certain transition system. The input sym­ bols of the system are the action names Jumpln and Jump Out. The states of the system are the valuations­ functions from fluent names to truth values-that satisfy the formula InLake ::J Wet. If we agree to represent a valuation by the set of fluents to which it assigns the value True then the set of states can be written as

The transition diagram of this system is depicted in Fig­ urel.

Besides constraints and effect propositions, AR0 has also "value propositions" that represent conditions on the values of fluents in specific situations, such as

For instance, the second value proposition expresses that performing the sequence of actions Jumpln; Jump Out in the initial state will bring the system to a state which satisfies -,JnLake 1\ Wet. Both value propositions shown above are "entailed" by domain description (1).

In order to formalize Example 2, the language AR0 needs to be extended. We will introduce, besides iner­ tial fluent names, a second special category, "dependent" fluent names. Thus, in the extended language, a fluent name can be designated as inertial or dependent, but not both. The language AR0 corresponds to the special case when there are no dependent fluent names.

For simplicity, we drop the argument in Safe(x) and consider only two locations- the top of the table and the rest of the world. The action names are PutOnTable and RemoveFromTable. The fluent names are OnTable and Safe; On Table is inertial and Safe is dependent. The domain description consists of the following propositions:

Safe depends on OnTable, always OnTable ::J Safe, PutOnTable causes OnTable, RemoveFromTable causes -,QnTable. (4)

The first line of (4) is a proposition of a new kind, a "dependency proposition." 2 The fact that the domain description includes this proposition and no other de­ pendency propositions beginning with Safe tells us that the value of this fluent in any situation is determined by the value of the fluent OnTable. This assumption is nonmonotonic, in the sense that it can be defeated by adding other dependency propositions to ( 4).

In the extended language, a "state" is a pair. Its "explicit" component is what is considered a state in An0- a valuation that satisfies the constraints of the given domain description. The "implicit" component is a "dependency," i.e. a set of valuations which are con­ sidered to be possible. For instance, the valuations that satisfy OnTable :J Safe are

According to the semantics of the extended language de­ scribed below, two dependencies can be used in this case as the implicit components of states. The dependency { v1 , v2 } represents the case of a doll, which is safe no matter where it is located. The dependency { v1, V3} rep­ resents a hammer, which is safe only when it is on the table. We will see that domain description (4) has the following states:

The difference between a1 and a3 is the difference be­ tween a doll and a hammer that are out of reach of the baby. The explicit components of these states are the same, but their dependencies are different.

The transition diagram of this system is depicted in Figure 2. Note that the system is deterministic: Exe­ cuting any action in any state leads to a uniquely deter­ mined state. However, the values of the fluents On Table and Safe do not determine the state uniquely, and con­ sequently do not predetermine the values of the fluents in the next state.

2 Dependency propositions are somewhat similar to the formulas INESSENTIAL(p, q) used in [Myers and Smith, 1988] . The authors' intention was to express "that fluent q is inessential in any justification of fluent p."

4 The Action Language AR'D

In this section, we assume that the reader is familiar with the description of the language A no in [Kartha and Lifs­ chitz, 1994]. About the language An [Giunchiglia et al., 1994] it suffices to know that it differs from Ano in two ways. First, fluents in An do not have to be proposi­ tional; their values can come from any domains. Second, "release" propositions are replaced in An by "indeter­ minate effect propositions" whose syntax is similar, but the semantics is somewhat different and is better suited for the task of formalizing nondeterministic actions.

4.1 Syntax

An AnV language is characterized by

• a nonempty set of symbols, that are called fluent names,
• a function, associating with every fluent name F a nonempty set Domp of symbols, that is called the domain ofF,
• two disjoint subsets of -fluent names; the elements of one are called inertial, and the elements of the other dependent,
• a nonempty set of symbols, that are called action names.

An independent fluent name is any fluent name that is not dependent; in particular, all inertial fluent names are independent.

An atomic formula is an expression of the form

where F is a fluent name and V E Domp. A formula is a propositional combination of atomic formulas.

There are five types of propositions in ARV- value propositions, constraints, determinate and indetermi­ nate effect propositions, and dependency propositions. A value proposition is an expression of the form

where C is a formula, and A is a string of action names. A constraint is an expression of the form

where C is a formula. A determinate effect proposition is an expression of the form

where A is an action, and C and P are formulas . An indeterminate effect proposition is an expression of the form

where A is an action name, F an inertial fluent name, and P a formula. Finally, a dependency proposition is an expression of form

where F is a dependent fluent name, F 1 any fluent name, and P a formula.

A domain description is a set of propositions.

The following abbreviations will be used. In formu­ las, some parentheses will be omitted, as customary in propositional logic. If A in a value proposition (6) is empty, we will write this proposition as

initially C.

Otherwise, the members of A will be separated by semi­ colons. In effect propositions (8), (9) and in dependency propositions (10), the part if P will be dropped if Pis the propositional formula True. A fluent F is propositional if Domp = {False, True}; for a propositional fluent F, we will abbreviate the atomic formula

F is True

by F .

With these notational conventions, (1) and (4) become domain descriptions in the language ARV. The follow­ ing enhanced formalization of Example 2 illustrates the use of nonpropositional fluents. Let £1, ... , Ln (n > 1) be distinct symbols. Replace the propositional fluent OnTable in the language of (4) by the fluent Location, whose domain is { L 1, ... , Ln}; On Table will be treated as an alternative notation for L1. The new domain de­ scription is

If n = 2 then (11) is essentially the same as (4).

Here is a further enhancement, illustrating the use of P in dependency propositions (10). We would like to express that the closet is a safe location if its door is closed. Specifically, if the object is in the closet, then its safety depends on whether or not the door is closed; if it is then the object is definitely safe. This can be done by extending (11) as follows . We add to the language the inertial propositional fluent name DoorClosed and the action names CloseDoor, OpenDoor. The following propositions are added to (11):

Safe depends on DoorClosed if (Location is InCloset), always (Location is InCloset) 1\ DoorClosed ::::> Safe,

CloseDoor causes DoorClosed,

OpenDoor causes --.DoorClosed

(InCloset stands for £2). In this new domain descrip­ tion, Safe depends on Location and DoorClosed if the object is in the closet, and only on Location otherwise. Opening the door may affect the safety of the object only if it is in the closet.

4.2 Semantics: Dependencies and States

A valuation is a function v defined on the set of fluent names such that, for every fluent name F , v(F) E Domp. Any valuation v can be extended to atomic formulas as follows:

It can be further extended to arbitrary formulas accord­ ing to the truth tables of propositional logic. A valuation v satisfies a constraint (7) if v( C) = True.

Consider a domain description D. A fluent P is an F-argument for a valuation v if there is a dependency proposition (10) in D such that v(P) = True. A depen­ dency is a set of valuations. Two valuations v and v 1 are said to be incompatible if there exists a dependent fluent F such that v (F) =/: v 1 (F), the set of F -arguments for v is the same as for v 1 and for each F -argument F 1 we have v(F 1 ) = v 1 (P). A dependency~ is coherent if

• every valuation in ~ satisfies the constraints in D , and
• does not contain incompatible valuations.

It is clear that a subset of a coherent dependency is a coherent dependency also. We are interested in the "maximally strong" coherent dependencies, that is, in the coherent dependencies that are maximal with respect to set inclusion. For istance, the maximal coherent de­ pendencies of (4) are {v1,vz} and {v1,v3}.

A state of a domain description D is a pair (v, ~), where ~ is maximal among the dependencies coherent relative to D, and v E ~. For instance, the states of (4) are u1, ... ,0"4 as defined by (5).

4.3 Semantics: The Transition Function

The key element of the semantics of ARV is the defi­ nition of the "result" functions Rest., where ~ is a de­ pendency. Each of these functions applies to an action name and an element of~, and produces a subset of~. Together, these functions define a nondeterministic tran­ sition function on the set of states, as follows: Given an action name A and a state (v, ~) , the possible successor states have the form (v 1 ,~), where v 1 E Resc,.(A,v).

For any dependency~, Res~(A, v) is the set of valua­ tions v 1 in ~ such that for each determinate effect propo­ sition (8) in D, v 1 (C) = True whenever v(P) = True . The elements of Rest. (A, v) will be the valuations in Res~(A, v) which differs from vas little as possible. The difference between v and a valuation v 1 E Res~ (A, v) is measured by New A ( v, v 1 ), defined as the set offormulas

such that

• F is inertial and v (F) =/: v 1 (F), or
• for some indeterminate effect proposition (9) in D, v(P) = True.

The condition v 1 (F) =/: v(F) expresses that (12) is a "new fact" that becomes true if the execution of A in a state (v,~) results in state (v 1 ,~). The set NewA(v,v 1 ) in­ cludes such "new facts" for all inertial fluents F . (If F is noninertial then it is not expected to keep its old value after performing an action, so that the change in its value is disregarded.) On the other hand, if some indeterminate effect proposition allows F to change, we treat its value in (v 1 , ~) as "new" even if it happens to coincide with the value ofF in (v, ~) .

Now we define Res.c.(A,v) to be the set of valuations v' E Res~(A,v) for which NewA(v,v') is minimal rela­ tive to set inclusion- in other words, for which there is nov" E Res~(A,v) such that NewA(v,v") is a proper subset of NewA(v,v').

It is easy to check that in the case of domains (1) and ( 4) this definition leads to the transition diagrams shown in Figures 1 and 2 respectively.

4.4 Semantics: Models and Entailment

A structure is a pair (~, '11) where ~ is a dependency and \11 is partial function from strings of actions into ~ whose domain is nonempty and prefix-closed. If \11 is defined on a string A, we say that A is executable in \11.

A value proposition C after A is true in a structure (~, '11) if A is executable in \11 and 'l!(A)(C) = True.

Consider a domain description D. A structure (~, '11) is a model of D if ~ is maximal and coherent, every value proposition in D is true in \11, and for every string of actions A executable in \11 and every action A one of the following two conditions is satisfied:

• AA is executable in \11 and

or

• AA is not executable in \11 and Res.c.(A, 'l!(A)) = 0.

A value proposition is entailed by a domain description D if it is true in every model of D.

For instance, value propositions (3) are entailed by domain description (1) in the sense of this definition. Consider the corresponding propositions for the second example:

OnTable 1\ Safe after PutOnTable,

·On Table 1\ Safe after PutOnTable; RemoveFromTable. (13)

The first of them is entailed by domain description (4), but the second is not. If we add the "initial condition"

to (4) then the extended domain description will entail both propositions in (13).

5 Some Properties of ARV

It is not difficult to verify that, in the absence of depen­ dent fluents, the semantics of AR.V is equivalent to the semantics of AR.. In this case, the set of all states in the sense of AR. is the only maximal coherent dependency.

Several properties of AR.0 established in [Kartha and Lifschitz, 1994] can be proved for AR.V as well. Clearly, adding a value proposition to a domain description can only make the set of its models smaller, and hence the set of value propositions entailed by it bigger (a "restricted monotonicity property" in the sense of [Lifschitz, 1993]). Any formula can be replaced by an equivalent formula without changing the set of models, and explicitly de­ fined fluent names can be eliminated.

A constant in a domain description D is a dependent fluent F such that no dependency proposition in D be­ gins with F. In any model of D, the value of a constant after executing any sequence of actions is the same as in the initial situation.

6 The Markov Property

Let A be a strin_g_ of actions. We say that a domain description D is A-complete if for every fluent F there exists a value V E Domp such that D entails

We say that two domain descriptions D1 and D2 are A-equivalent if

• every proposition that belongs to one of the descrip­ tions Dt, D2 but not to the other is a value propo­ sition

C after A'

such that A is not a prefix of A',

• for every fluent F and every value V E Domp, proposition (15) is entailed by D1 if and only if it is entailed by D2.

The following theorem expresses the Markov property for AR domain descriptions (that is, for ARV domain descriptions without dependent fluents.)

Proposition. Let D1 , D2 be AR. domain descriptions, and let A, A' be strings of action names such that A is a prefix of A'. If D1 and D2 are A-complete and A­ equivalent then they are A'-equivalent.

For AR.V domain descriptions, this is generally not true. For example, let D1 be ( 4), and let D2 be obtained from D1 by adding value proposition (14). Take A to be PutOnTable, and take A' be PutOnTable; RemoveFromTable. It is easy to see that Dt and D2 are A-complete and A-equivalent, but not A'-equivalent.

Acknowledgements

We are grateful to Michael Gelfond, Matthew Ginsberg, Neelakantan Kartha, Norman McCain, David Smith and Hudson Turner for useful discussions related to the sub­ ject of this paper. This work was partially supported by National Science Foundation under grant IRI-9306751.