Reasoning about actions: Non-deterministic effects, Constraints, and Qualification

1 Introduction and Motivation

In this paper we consider several aspects of reasoning about actions: effects (direct, indirect, nondeterministic) of actions, qualification and executability of actions, con­ straints and their manifestations as ramifications and/or qualification, and propose a language that facilitates rep­ resenting and reasoning about all of the above in a uni­ form manner .

We follow the notation of situation calculus [McCarthy and Hayes, 1969] and have three different sets of symbols, called fluents, actions, and situations, respectively. For example, in the statement "Shooting causes the turkey to be dead if the gun was loaded", shoot is an action, dead and loaded are fluents, the initial situation is denoted by so, and the situation after the shoot is performed is denoted by res( shoot, s0 ). The state corresponding to a particular situation is represented by the set of fluents true in that situation.

Consider the action "shoot" . It is impossible to perform this action if the agent does not have a gun. I will re­ fer to the condition of having a gun as an executability condition for the action "shoot". Now let us reconsider the statement "Shooting causes the turkey to be dead if the gun was loaded". Here, the condition of the gun being loaded is a precondition for the fluent "dead" to hold in the situation obtained after performing the ac­ tion "shoot". In the literature related to frame problems [Brown , 1987] both type of conditions are sometimes con­ sidered as part of the qualification l?roblem. In the plan­ ning literature [Allen et al. , 1990j the second kind of conditions and the corresponding effects are referred to as conditional effects. To avoid confusion we will refer to them as "executability condition of an action" and "preconditions of effects" respectively. In other words the condition of having a gun is an executability con­ dition for the action "shoot" while the condition of the gun being loaded is a precondition of the effect of having the turkey dead when the action "shoot" is performed.

We consider two kinds of constraints: dynamic and static. In this paper we only consider one-step dynami c constraints which are general statements that are true about adjacent situations. For example, the statement that "The salary of a person does not decrease by per­ forming an action" is a dynamic constraint that says the salary of a person in a situation S is always less than or equal to the salary of the person in the situation ob­ tained by performing an action in S. The statement "No action can make a dead person alive" is another example of an one-step dynamic constraint.

Static constraints are statements about the world that is true in all situations. For example, the statement that "a person can not be at two different places at the same time" is a static constraint.

Now consider the action moveto_B. The effect of this ac­ tion is to make the fluent aLB true. Now suppose that before the action was executed "aLA" was true, i.e. the agent was at the position A. Not only "aLB" would be true after executing "moveto_B", but also the const raint "a person can not be at two different places at the same time" will dictate that "aLA" be false in the resulting situation. We could explicitly state this as an effect of the action "moveto_B". But there might be several dif­ ferent positions in our world, and also there might be several different actions (fly_to_B, drive_to_B , jump_to_B etc.) which have similar interaction with the constraint. A better approach would be state it as a constraint (i.e. not to state it explicitly for all those actions), and have a mechanism that considers the ramification of a directly specified effect due to the constraints. This is referred to as ramification in the literature.

It was pointed out in [Lin and Reiter, 1994] that some constraints, instead of causing ramifications , affect the executability of an action. Moreover, sometimes these constraints are indistinguishable (in a first order repre­ sentation) from the constraints that cause ramifications.

For example, consider the action of "marry_B", with the effect "married_to_B" and the constraint that "a per­ son can not be married to two different persons at the same t ime". Now suppose "married_to_A." is true in a particular situation S. Intuitively, we would like the ac­ tion "marry _B" to be in-executable in situationS, rather than have a ramification of the action "marry _B" that makes "married_to_A." false.

One of the goal of this paper is to propose a language whi ch dist inguishes between the above two constraints.

Now let us consider the effect of actions in the absence of any precondi tions, executability conditions and con­ straints. Let S and S' be statesand let us represent the effect of an action a by a formula E a . Let us also repre­ sent the set of possible states that may be reached after an action a is performed in a situation with state S be Res( a, S). Using Winslet ts ' definition [Winslett , 1989]:

Definition 1 S' E Res( a, S) if

(a) S' sat isfies Ea, and

(b) There is no other state S" that satisfies Ea and that is closer to S than S', where closer is defined using sym­ met ri c difference,

In terms of the theory of "updates" [Katsuno and Mendelzon, 1992], Res( a, S) can be defined as S' E Res( a, S ) iff S' is a model of S o E a . When the update operator o is defined in terms of symmetric difference t hen this defini t ion coincides with Winslett 's definition .

Now let us consider the action of tossing a coin. Intu­ it ively, t he effect of this action is either "head" or "tail" (not both) regardless of which of the fluents were true before the coin was spun. But if we represent this ef­ fect as E10., = (head 1\ -, tail) V (tail 1\ -, head) and use Winslett 's definition or the update operator o de­ fi ned in terms of symmetric difference, then we have the problem that if the coin was "head" before per­ forming "toss" then it stays "head" after performing "toss" and similarly if it was "tail" before perform­ ing "toss" then it stays "tail" after performing "toss" . This has also been pointed out in [Crawford, 1994; Brewka and Hertzberg, 1993; Kartha and Lifschitz , 1994; Pinto, February 1994; Sandewall , 1992] . Representing, Etos. = head V tail , does not help either.

Let us now consider a different action "paint" whose ef­ fect is to paint a block "red" or "blue". But this time the robot is smart and minimizes its job when it realizes that t he block is already either "red " or "blue". Here, E paint = (red 1\ · blue) V (blue 1\ -, red) is adequate when we use Winslett 's definition .

Consider the action of "spinning" a coin on a chess board. Let us consider the fluents "black" and "white" whi ch mean that the coin touches a black square and the coin touches a white square respectively. Intuitively, after t he coin is spun the fluent "black", "white" or both could be true in the resultant situation regardless of what was true before. But the only way to represent E ·pin , the effect of spinning the coin, in first order logic is through the formula E,pin = black V white, or its equivalent .

Here, we again get unintuitive result if we use Winslett 's definition . Moreover, since Etou and Epaint are equiva­ lent in their propositional representation, any approach that does not specify the differences in their intended meaning will be wrong with respect to one of them.

When we examine our formalization we observe that there are two aspects to it . (i) We use classical logic to represent effects of actions. (ii) We use a fixed defini­ tion of "closeness" based on symmetric difference. To distinguish between "toss" and "paint" we have two choices: (a) to use a more expressive language to rep­ resent Etou and Epaint, and/or (b) to use different defi­ nition of "closeness" for "toss" and "paint", i.e. we use different update operators for "toss" and "paint".

Kartha and Lifschitz [Kartha and Lifschitz, 1994] and Sandewall [Sandewall, 1992] follow the second approach by allowing specification of when inertia of a fluent (w.r .t . an action) is not preserved. (This results in dif­ ferent update operators.)

In this paper we propose to use the first approach of using a more expressive language (than first order logic) to represent effects of actions.

Now let us go back to representing constraints and the resultant ramification and/or qualification. (For simplic­ ity we stay with the assumptions that we do not have preconditions and executability conditions.) In presence of constraints C, Res(a,S), the set of situations that can be possible when a is executed in situation S, is usually [Kartha and Lifschitz, 1994] defined as

Definition 2 S' E Res( a, S) if

(a') S' satisfies Ea U C, and

(b') There is no other state S" that satisfies Ea U C and that is closer to S than S', where closer is defined using symmetric difference,

Now let us reconsider the constraints "a person can not be at two different places at the same time" , and "a per­ son can not be married to two different people at the same time". These two constraints when expressed in first order logic are equivalent. But as discussed before they have different intended meanings, the first causes ramification while the second adds qualification condi­ tions. Here also instead of using different update oper­ ators for different constraints we propose to use a more expressive language to represent constraints. Moreover, the condition (a') suggests that we use the same language to represent effects of actions and constraints. This is one of the main theses of our paper.

In this paper we propose a language to express (i) ef­ fects of actions with their preconditions , (ii) executabil­ ity conditions of actions, and (iii) constraints, such that the drawbacks of using first order logic (FOL) to express them (as described in this section) is avoided.

Before we go on to introduce the syntax and semantics of the language of "state specifications" for specifying effects of actions and constraints, we briefly discuss dis­ junctive logic programs. We later give the semantics of "state specifications" through translations to disjunctive logic programs.

2 Background: Logic Programming Preliminaries

A disjunctive logic program 1 is a collection of rules of the form

where L; 's are literals. When L; 's are only atoms we refer to the program as a normal disjunctive program. When m = n and L; 's are only atoms, we refer to the program as a positive disjunctive logic program.

Definition 3 [Gelfand, 1994] The answer set of a dis­ junctive logic program II not containing not is the smallest (in a sense of set-theoretic inclusion) subset S of Lit, the set of all literals, such that

• (i) for any rule La V .. . V Lk +- Lk+1 , ·.· , Lm if Lk+l, ... , Lm E S, then S n {La, ... , Lk} -:j:. 0
• (ii) if S contains a pair of complementary literals, then S =Lit.

The set of answer sets of a program II that does not contain negation as failure is denoted by a(II). 0

It should be noted that for positive disjunctive logic pro­ gram (all L; 's are atoms, and the program does not con­ tain not ), the answer sets correspond to the minimal Herbrand models.

Definition 4 [Gelfand, 1994] Let II be a disjunctive logic program without variables. For any set S of lit­ erals, let II 5 be the logic program obtained from II by deleting

• (i) each rule that has a formula not L in its body with L E S, and
• (ii) all formulas of the form not L in the bodies of the remaining rules.

Clearly, II 5 does not contain not ' so that then a(II 5 ) is already defined in Definition 3. If S E a(II 5 ), then we say that Sis an answer set of II. 0

2.1 Notational Convenience

In this paper we consider a disjunctive logic program to be of a set of rules of the form (1), where La, ... , Lk are a conjunction of literals. The answer sets of such programs are defined exactly as in Definition 3 and Def­ inition 4, except that (i) in Definition 3 is replaced by the following:

for any rule La V V Lk +- Lk+l ... Lm if Lk+t, ... , Lm E S, then there exist i, 0 ~ i ~ k, such that all conjuncts in L; are in S.

1 Although we use the answer set semantics [Gelfond and Lifschitz, 1991; Gelfond, 1994], we use the symbol V instead of or. Our connective V is not the classical disjunction.

3 State Specifications

For an action a, to specify its effect Ea, we need to make statements about the state reached after 'a' is performed (we refer to this state as the updated state w. r. t. 'a'). To integrate preconditions and executability conditions of 'a' we also need to consider the state where 'a' is to be performed (we refer to this state as initial state w.r.t. 'a'). While to represent static constraints we only need to refer to the updated states of actions, to be able to represent dynamic constraints we need to able to refer to both initial states and updated states of actions.

To be able to express the truth and falsity of fluents in the initial states and updated states of actions we use four special operators "in", "out", "wasin" and "was_out". For any fluent f, the intuitive meaning of in(!) is that f is true in the updated state. The intu­ itive meaning of was_in(f) is that f is true in the initial state. Similarly the meaning of out(!) is that the flu­ ent f is false in the updated state, and the meaning of was_out(f) is that the fluent f is false in the initial state.

A state specification is a set of rules of the form

where, k, l, m, n, p and q could be 0.

Intuitively, the rule

w.r.t an action a means that if t is true and u is false in the initial state then if q is true and s is false in the updated state then p must also be true in the updated state.

3.1 Using state specifications

For every action a, we have a corresponding state speci­ fication Pa that specifies (i) the effect of a together with the preconditions, and (ii) the executability conditions of action a. We refer Pa as the "update specification" of the action a.

For example, for the action "shoot", the update specifi­ cation Pshoot is as follows:

Similarly, the update specifications for the actions "toss", "spin", and "paint" can be given as follows:

An effect of an action "buy" where we can either buy a 'candy' or an 'ice-cream' is represented by

The difference between Pbuy and Ppaint is due to the fact that if we have a candy and we buy an ice-cream we have both candy and ice-cream. On the other hand if we have the color as blue and we paint it red the resultant color is only red .

The set of constraints C is also a state specification. In the absence of constraints to reason about the exe­ cutability and the effects of an action a we only need to consider its update specification Pa. But in the pres­ ence of the constraints C we need to consider the state specification Pa U C.

The one-step dynamic constraint "No action can make a dead person alive" can be represented by the specifi­ cation:

In presence of concurrent actions [Lin and Shoham, 1992; Baral and Gelfond, 1993] a1 and a2 such that they do not interact, the update specification of { a1 , a2} can be given by:

But when a 1 and a 2 interact it is more complex to de­ termine the executability and effects of { a1, a2}. We will further discuss this in Section 6.1.

3.2 Semantics of State Specifications

We now define Res( a, S), the set of states that may be reached by performing action a in a situation correspond­ ing to state S, when the effects and constraints are given as a state specification P.

Our definition of Res( a, S) when effects and constraints are represented by state specifications will be a fixpoint definition similar to the fixpoint definition 2 of McCain and Turner [McCain and Turner, 1995], and is based on translating state specifications to disjunctive logic programs. 3

Algorithm 3.1 Translating State Specifications

INPUT - s: state, P: state specification, a: action OUTPUT- D.,P,a : a disjunctive logic program

2 McCain and Turner [McCain and Turner, 1995] show that the definition of Res(a,S) in Definition 2 is equivalent to Res(a, 5) = {5': 5' = {L: L E Cn((5 n 5') u Ea u C)}}.

3 Turner conjectures that our semantics is equivalent to a semantics that can be obtained by directly extending the definition of P-justified revision in [Marek and Truszczynski, 1994c; Baral, August 1994]. Nevertheless, we consider our characterization to be more intuitive.

Step 1. Initial Database

For any fluent f if f is true in the state s then the program contains holds(!, s) <-

else the program contains

Step 2. Inertia Rule

These rules are motivated by the minimality considera­ tion that only changes that happens to the initial knowl­ edge base are the ones dictated by the revision specifi­ cation.

Step 3. Translating the update rules

Each revision rule of the type (2) in the state specifica­ tion P is translated to the rule

(holds(b0 , res( a, s)) 1\ ab(b0 , a, s)) V ... V (holds(bk, res( a, s)) 1\ ab(bk.a, s)) V (·holds(c0 , res( a, s)) 1\ ab(co, a, s)) V . . . V (·holds(q, res( a, s)) 1\ ab(c1, a, s)) <--holds( do, res( a, s)), ... , holds(dm, res( a, s)), -.holds( eo, res( a, s)), ... , -.holds( en, res( a, s)), holds(f0 , s), ... , holds(fp, s)), -.holds(g0 , s), ... , -.holds(gq, s)

Definition 5 Let S be a state and P be a state spec­ ification corresponding to action a. Let Ds,P,a be the translation of S and P to a disjunctive logic program obtained by Algorithm 3.1.

If A is a consistent answer set of D,,P,a then S' = {! : holds(!, res( a, s)) E A} E Res( a, S).

If Res( a, S) is an empty set we then say that a is not executable in the situations whose state is S.

The definition of executability of an action in a state Sin Definition 5 allows us to specify executability conditions, effect of actions and constraints in a single framework.

4 Examples

Proposition 1 Consider the action "toss", its update specification Ptou and S = { h}. (For convenience we use 'h' for head and 't' for 'tail'.)

Proof( sketch)

Let 111 be the program obtained using Algorithm 3.1. It is easy to show that 111 has the two answer sets {holds(h, s), -.holds(t, s), holds(h, res(toss, s)), ab(fi, toss, s), -.holds(t, res( toss, s)), ab(t, toss, s)} and {holds(h, s), -.holds(t, s), holds(t, res(toss, s)), ab(l, toss, s), -.holds(h, res( toss, s)), ab(h, toss, s)}.

The above two answer sets corresponds to the states { h} and {t} Hence, Res(toss, S) = {{h}, {t} }. 0

Proposition 2 Consider the action "spin', its update specification P·pin and S = { w}. (For convenience we use 'w' for white and 'b' for 'black'.)

Example 1 It is easy to see that for the action 'paint' with the effect specified by Ppaint in Section 3.1, Res(paint,{blue}) = {{blue}}, Res(paint,{red}) = { {red}}, and Res(paint, {}) = { {red}, {blue}}.

On the other hand for the action 'buy' with the effect specified by Pbuy in Section 3.1,

Example 2 Consider the the action "shoot" in YSP [Hanks and McDermott, 1987] and the update specifi­ cation P·hoot.

Consider S1 = { has_gun, loaded, alive},

s2 = { has_gun, alive}, and s3 = {loaded, alive}.

Moreover, Res( shoot, S3 ) = {}, implying that shoot is not executable in a situation whose state is s3. 0

Example 3 Let us consider the constraint C1 which says "a person can not be at two different places at the same time", the action "moveto...B", and let us assume that our world consist of only two places, A and B 4 .

The update specification of "moveto...B", denoted by Pmoveto_B is given by

The constraint C1 is denoted by the following state spec­ ification

It is easy to see that Res( moveto_B, {aLA}) {{aLB}}.

Now let us consider the constraint C2 which says that "a person can not be married to two different persons at the same time". the action "marry ...B", and let us assume that our world consist of only two marriageable persons, A and B.

The update specification of "marry ...B", denoted by Pmarry_B is given by

The constraint C2 is denoted by the following state spec­ ification

<- in(married_to_B), in(married_to_A)

It is easy to see that Res( marry_B, { married_to_A}) = {}, implying that the action marry_B is not executable in a situation whose state is { married_to_A}. 0

4 We generalize this in section 5.1 when we use variables.

5 Further Extensions

5.1 Extending State Specifications: variables, evaluable predicates

Consider the one-step dynamic constraint which says that the salary of a person does not decrease by perform­ ing an action. This can be represented as an extended state specification that allows variables and evaluable predicates ( <, ::; , >, 2, =, f.), in the following way:

It is straight forward to characterize the semantics of extended state specifications. We first instantiate the variables in the extended state specifications. We then evaluate the evaluable predicates in the body of the rules and throw away the rules whose body has an evaluable predicate that evaluates to false, and only consider the rest of the rules with the evaluable predicates eliminated. This gives us a state specification whose semantics is defined in Definition 5.

5. 2 Extending A and Lo

The language A was introduced by Gelfond and Lifschitz in [Gelfond and Lifschitz, 1992], to express actions and their effects. It was later extended to Co [Baral et al., 1994] to include actual situations and to AR [Kartha and Lifschitz, 1994] to include static constraints.

In A, Co and AR, effects of actions were specified through propositions of the following two forms

When using update specifications to express effects and preconditions of actions, propositions of the above form are translated to rules of the following two forms respec­ tively.

respectively, and added to the update specification of A.

The languages A and Co can be extended by having ef­ fects and preconditions of actions being represented by updated specifications. Moreover, the translations of A [Lifschitz and Turner, 1994] and Co to disjunctive logic programs can be easily adapted to the proposed exten­ sions by following Algorithm 3.1 to translate the update specifications of actions.

In AR static constraints 5 are represented as first order theories. Our proposal is to represent constraints us­ ing state specifications. To translate a domain descrip­ tion description in the resulting language to a disjunctive logic program we use Algorithm 3.1 w.r.t . every action a and the corresponding state specification Pa UC, where, Pa is the update specification of a, and C is the con­ straint.

5 An does not allow representation of dynamic constraints.

6 Future Work

Some of the questions that need to be answered are:

1. How expressive is the language of state specifications? Can an arbitrary first order theory be expressed using state specifications?

From the fact that any logic program can be represented as a state specification [Marek and Truszczyitski, 1994a], and from the expressibility of logic programs, the answer is yes. But an efficient algorithm that can translate a first order theory to a state specification still need to be developed. One result that may help is in [Kosheleva and Kreinovich, 1992], where Kosheleva and Kreinovich propose an algorithm to syntactically translate a first­ order theory to a logic program.

2. How easy is to express something using "State Spec­ ifi cations"?

The answer is "as easy as specifying something using disjunctive logic programs". This is clear from the defi­ nition of Res( a, S) which uses a straight forward trans­ lation from state specifications to disjunctive logic pro­ grams.

Some researchers have expressed concern about the in­ tuitiveness of the language of disjunctive logic program­ ming vis-a-vis first order logic. We believe that one rea­ son fisrt-order logic is more intuitive to most of us is because we are more familiar with it . It is quite possible that as we become more familiar with disjunctive logic programming it will appear more intuitive.

Also, why should we expect first-order logic to be the language for all our needs? In deductive databases, logic programming is the language of choice. The similarity between 'deductive databases' and 'reasoning about ac­ tions' is amazing and will be discussed in a future paper.

6.1 Effects of Concurrent Actions

In [Baral and Gelfond, 1993], Baral and Gelfond ex­ tend the language A to allow concurrent actions. Let us consider the execution of actions a and b, with cor­ responding update specifications Pa and Pb. If a and b are completely independent of each other then the ef­ fect of executing a and b concurrently can be given by P{a ,b} = Pa U Pb.

But in general actions executed concurrently are not al­ ways independent of each other. In that case, one way would be to explicitly specify the effect of each possi­ ble sets of actions. This leads to a frame problem in another direction . In [Baral and Gelfond , 1993], Baral and Gelfond suggest that a compound action (a set of actions executed concurrently) normally inherits the ef­ fects of its subactions. Using their method the effect of executing actions a and b concurrently is reasoned by inheriting from Pa and Pb effects that do not contra­ di ct with P{a ,b}, if any. But this approach is weak when effects are represented by state specifications.

Intuitively, the effect of executing {a, b}, can be obtained by (i) inheriting the effects of executing a and b indepen­ dently which do not contradict with P{a,b}· (ii) and the effects specified by P{ a,b} . This dictates that in the state obtained after executing {a,b}, c, f, and gmust be true and e must be false. In this report we leave open the problem of formalizing this.

7 Conclusion

This paper builds on the efforts in [Marek and Truszczyitski, 1994c; 1994b; Baral and Gelfond, 1993]. Marek and Truszczyitski introduce the language of "re­ vision programs" 6 and use it to represent complex effects of actions, such as the action of "reorganizing" a depart­ ment whose effect is given as "If John is in the depart­ ment then peter must not be there", with a non-classical interpretation of "If ... then ... " implying that "John is preferred over Peter". In [Baral, August 1994], Baral shows how to translate "revision programs" to extended logic programs and introduces was_in and was_out, in the body of rules.

In this paper we introduce the language of state spec­ ifications and show that this language is not only able to represent complex effects, but also, non-deterministic effects of actions, executability conditions of actions, pre­ conditions of different effect of actions, and dynamic and static constraints. Moreover, it allows distinct represen­ tations of different non-deterministic effects, and differ­ ent constraints that have same representation in first or­ der theory (See the discussion on "paint" and "toss", and "marry" and "move" in Section 1.). We then show how to incorporate state specifications to action description languages like A and £a, and how to implement state specifications through a translation to disjunctive logic programs 7 .

Recently, McCain and Turner[McCain and Turner, 1995] propose using inference rules for representing constraints so as to distinguish between constraints that. cause ram­ ification, and that add to the qualification. Unlike their approach we are able to ·express both dynamic (one-step) and static constraints, and non-deterministic effects in a single language. Moreover, one of the fundamental thesis of our approach is that effects, and executability condi­ tions of actions be expressed in the same language as the constraints.

One of our main future goal is to study impact of using state specifications with other action theories. In par­ ticular we would like to formalize effects of concurrent actions when the effects are given as state specifications.

6 Revision programs are state specifications, with the fol­ lowing restrictions: (a) No was_in and was_out, (b) No dis­ junctions in the head of rules, and (c) No rules with empty heads.

7 Currently, there exists some systems that can compute the answer sets of disjunctive logic programs.

8 Acknowledgment

I would like to thank Hudson Turner and the referees for their insightful comments. Research in this paper was supported by NSF grants NSF-IRI-92-11-662 and NSF­ CDA 90-15-006.