Defeasible Specifications in Action Theories

1 Introduction and Motivation

Recent research in formalizing effects of actions on a world in the presence of constraints have mostly concen­ trated on non-defeasible specifications, where the effect of actions and constraints are strictly specified 1 . The focus of these research was more on solving the frame problem and other problems such as the qualification and the ramification problem, .and it made sense to start with non-defeasible specifications.

In this paper we show how to incorporate defeasibility in the specification without loosing any of the good proper­ ties of previous specification languages. It is important to consider defeasible specifications for the same reason Jorge Lobot Department of EECS Univ. of Illinois at Chicago 851 S. Morgan St Chicago, IL 60607, USA jorge@eecs. uic. edu as the necessity of non-monotonic theories in knowledge representation and common-sense reasoning. The spec­ ifications are not definite and un-modifiable and may evolve. Our language should allow easy evolution or in the words of McCarthy, they should be 'elaboration tol­ erant'. We take a first step in this direction by allowing defeasible specifications.

*Support was provided by the National Science Founda­ tion, under grant Nr. IRI-9501577.

1 Support was provided by Argonne National Laboratory under contrad N r. 963042401.

1 Among the various approaches, the strictness of the high level specification language of A [5] and its successors [6], and the language used by Sandewal [10] is clear. Although, Reiter [9] and his group do not use a particular specification language per se, the syntactic restriction they put on how the effect axioms and constraints can be initially specified in first­ order logic, and the dependence of the compilation process that follows on the input syntax amounts to a specification language.

In our approach we consider 2 extensions of the high level language A of Gelfond and Lifschitz [5] and introduce defeasible constraints and effect propositions. Direct se­ mantics of A and many of its early successors (particu­ larly, the formalization of transition functions that map state-action pairs to states) do not use a logical language. But our formalization of the transition function is done using extended logic programming. This is due to the defeasibility of the specification. (Earlier, Baral [1] and McCain and Turner [8] use logic programming and infer­ ence rules respectively, to formalize transition functions in presence of causal constraints.) We then show how with minor modifications to the logic programming spec­ ification plus the addition of a few rules we can reason about the effect of a sequence of actions.

The necessity of defeasible specifications may be illus­ trated by the following example from [12]. Suppose we have a lamp with a switch on the side. Turning the switch causes an internal circuit in the lamp to flip be­ tween close (not open) and open. We can say then that the effect of executing the action turning_switch causes the circuit to close if it was open; or it will cause the switch to open if it was not open. It is also the case that when the circuit is close (not open) the light in the lamp is on, and when the circuit is open the light is off. Notice that although the state of the light is determined by the state of the circuit, the state of the light is indirectly affected by the action of turning the switch. This indi­ rect effect is known in action theories as a ramification of the action. In an action description language such as AC [11] this action domain may be described by the following propositions: 3

2 We consider this language due to its simplicity. Our ideas are important for other specification languages and their for­ malizations. We would consider the impact of defeasible spec­ ifications on them in the full version of this paper.

Ramification effects are usually derived from the state of fluents, 4 while direct effects come from the execution of an action. An equivalent formulation can be written using Lin's formalization [7] or the state specifications of Baral [1] .

Suppose now that we can also unplug the lamp and that a consequence of this action is that there will be no power going through the lamp. We can add to our description the following proposition to cover this action :

If there is no power going through the lamp the light in the lamp can never be on (this is regardless of the state of the circuit). We then must add the following ramification proposition:

Notice too, this proposition together with the previous propositions may create contradictions or forbid certain sequences of actions. For example, executing the se­ quence [unplugJamp, turning...switch] creates problems because there will be a state where the circuit is not open that causes the light to be on, and at the same time the light can not be on since the lamp is unplugged and there is no power going through the lamp. The problem is that a closed circuit not always, but normally, causes the light in lamp to be on. 5 Thus, the causality in proposition (4) must be defeasible.

In the following section we present AVC, an action de­ scription language with defeasible causality propositions. To make it easier for the reader we have excluded many of the other features of action description languages such as constraints, that are described in the literature. Most of these can be easily added to AVC. Following our ex­ ample, we start by describing how we can specify defeasi­ ble ramification effects. Later in Section 5 we show how our framework can also be used to capture defeasibility of the direct effect of actions.

3 At this point we appeal to the intuition of the reader with the meaning of the language. In the following sections we will present a formal description of an action language similar to AC.

4 Symbols that are used to represent the state of the world are called fluents. In this example the fluents are open and light_on.

5 There are many other reasons why a closed circuit may not cause the light to be on. It could be that the bulb in the lamp is burned, or there was a storm that blacked out the entire neighborhood.

2 The language A'DC

The language AVC has two disjoint non-empty sets of symbols called fiuents and actions, and four kinds of propositions: initial propositions, effect propositions, sufficiency propositions and defeasible sufficiency propo­ sitions. An initial proposition is an expressiOn of the form

where f is a fluent literal. A fluent literal is either a fluent or a fluent preceded by -.. A fluent literal is negative if it is preceded by -., otherwise it is called positive. An effect proposition is an expression of the form

where a is an action, and f and and each of P1, .. . , Pn (0:::; n) is a fluent literal. If n = 0 we will write:

Two effect propositions with preconditions P1, . .. , Pn and ql, ... , qm respectively are said to be contradictory if they describe the effect of the same action a on com­ plementary fs, and {pl , . . . ,pn} n {qi, ... 'qm} = 0

Non-defeasible and defeasible sufficiency propositions are expressions of the form:

where f and each Pl, . . . , Pn (1 :S n) is a fluent literal. A domain description is a collection of initial, effect, suffi­ ciency and defeasible sufficiency propositions. The ini­ tial propositions are referred to as facts and the other propositions are referred to as causal laws.

3 Transition functions of A'DC

We take a slightly different approach in defining the se­ mantics of the language AVC. Most of the action de­ scription languages [11; 6; 2] that are inspired by A have an independent characterization without involving any of the standard logical formalisms, such as logic pro­ gramming, default logic, circumscription, classical logic, etc . But when we allow defeasible causality and keep open the possibility of hierarchies of such causality it is not clear if we can avoid using standard logical for­ malisms and have independent characterizations.

An inherent component of semantics of action descrip­ tion languages is the transition function Res from ac­ tions and states to power set of states, where a state is a set of fluents . Intuitively, if s' E Res( a, s) we say that execution of action a in a state s may take us to the state s'. When we have only deterministic actions we can treat Res as a function from actions and states to states.

In this section we define the transition function of AVC through a translation of the domain description into an extended logic program. (We use the answer set seman­ tics of extended logic programs [4].) Given a set of causal laws D, an action a, and a state s, we construct an extended logic program IT(D, a, s), and use its answer sets to define Res( a, s) . The extended logic program IT(D, a, s) uses variables of three sorts: situation vari­ ables S, S1 , ... , fluent variables F, F1 , .. . , and action variables A, A1 , ....

For convenience, we use the following notations. The atom H olds(f, s) denotes the literal holds(!, s) if f is a positive fluent literal and the literal ·holds(lfl, s) if f is a negative fluent literal. Also, for any fluent f, If I = f and l·fl = f. By H olds(f, s) we denote the literal which is complementary to Holds(!, s). In addi­ tion, we will have an special postfix function symbol 1 that we will apply to fluents and fluent variables. It is used to distinguish negative from positive fluent literals occurring as predicate arguments. 6

We now describe the construction of the program TI( D , a , s), which consists of the translations of the indi­ vidual propositions in D and certain other rules.

Translation 3.1 {Constructing TI(D, a, s)}

1. Initial Database

Iff is true in s then TI(D, a, s) contains

Otherwise, II(D, a, s) contains

2. Inertia Rule

TI( D , a, s) contains the following inertia rules:

This rule is motivated by the minimality consideration which states that only changes that happens to a state as a result of an action a are the ones dictated by the direct and indirect effects of the action. If a has a direct effect on a fluent F (resp. the negated fluent F'), we say that that F (resp. F') is abnormal with respect to a in s. Thus, we expect abo(F, a, s) (resp. ab0 (F', a, s)) to be true (see item 3 below). Similarly, if If a has an indirect effect on a fluent F (resp. the negated fluent F'), we say that that F (resp. F') is abnormal with respect to a in s. Thus, we expect ab1(F, a, s) (resp. ab1(F', a, s)) to be true (see item 4 below).

3. Translating Effect propositions

For each effect proposition of the form (8) in D which describes the effect of the action a, TI(D, a, s) contains the following rules:

6 We could have used ..., instead of ' and write holds(·(f),s), but the unary negation..., is already used as predicate negation in extended logic programs.

For each non-defeasible sufficiency proposition of the form (10) in D, IT(D, a, s) contains the following rules:

For each defeasible sufficiency proposition of the form (11) in D, TI(D, a, s) contains the following rules:

Definition 3.1 For a states, and an action a, Res( a, s) is defined with respect to the causal laws D through the program II(D, a, s) in the following way:

Let A be the set of answer sets of IT(D, a, s) .

If II(D, a, s) is inconsistent (i.e., only the set Lit is in A ) then Res( a, s) is undefined, meaning that the action a is not executable in the state s.

Otherwise,

Note that Res( a, s) is defined if contradictory effect rules are absent and sufficiency propositions are signed 7 . In addition stratification of the sufficiency propositions guarantee Res( a, s) to be a singleton set.

3.1 Examples

, Example 3.1 Let D1 consist of the the causal laws (1), (2), (3), and (4). Let s1 = {open,power}, and s2 = {lighLon,power}. Intuitively, the ac­ tion turning....switch should cause the transition from s1 to s2 and from s2 to s1 . We now verify that this indeed is the case, by examining the answer sets of the programs 11(D1 , turning ....switch, sl) and IT(D1,turning....switch,s2 ). For s1 the initial database Sis:

The following four rules are the effect propositions:

7 We use the term 'signed' loosely. What we mean is that the sufficiency propositions result in a signing of the rules obtained in step 4 and 5. Stratification of sufficiency propo­ sitions has a similar meaning.

holds( open, res(turning_switch, s 1)) <­ ·holds( open, sl) abo( open', turning ...switch, s1) <- ·holds( open, sl) --,fwlds(open, res(turning_switch, sl)) <­ holds( open, sl) abo( open, turning _switch, st) <---- holds( open, s1)

Non-defeasible rules:

·holds(lighLon, res(A, St)) <----holds( open, res(A, s1)) ab0(lighLon', A, st) <---- holds( open, res( A, si)) holds(lighLon, res(A, s 1)) <------,holds( open, res(A, s 1 )) abo(lighLon', A, s1) <---- ·holds( open, res( A, st))

Inertia rules:

holds(F, res(turning_switch, s1)) <---- holds(F, si), not ab0(F, turning ...switch, sl), not abt(F, turning ...switch, St) ·holds(F, res(turning...switch, s1)) <---- ·holds(F, si), not ab0(F', turning...switch, s 1), not abt(F', turning ...switch, s 1)

The effect rules depend on the initial state S which will be part of any answer set of the program. Hence, the set

E = { ·holds( open, res(turning_switch, s1)), abo( open, turning _switch, s 1)}

will also be part of any answer set. Therefore, from the third and fourth non-defeasible rules we get that the set:

N D = {holds(lighLon, res(turning...switch, sl)), abo( lighLon', turning ...switch, s1 )}

will be part of any answer set too. The inertia rules, based on the initial state, will try to make the fluent literals power, ·lighLon and open true in the situation res(turning_switch, st). We can ignore the ab1 predi­ cates since there are no defeasible rules. However, abo in E blocks open and ab0 in N D blocks --,[ighLon. Hence, the inertia rules generate the set

I = { hold.s(power, res( turning _light, st))}

No other holds literal with situation argument res(turning_light, si) or ab0 predicate with third argu­ ment s1 will be in any answer set. Notice too, that the evaluation of the rules was stratified, first the effect rules, then the non-defeasible rules and finally the inertia rules. Hence, it is easy to see that Res(turning_.switch, si) = s2 and it is completely determined by E UN D U J.

It can also be shown that Res(turning_switch,s2) = s1 . 0

Example 3.2 If we add to the previous example the causal laws (5) and (6), we can see that the answer set of II( D1, unplug, s2) is inconsistent. This is because we will have the effect rule:

that is unconditionally true, and the following two non­ defeasible sufficiency rules:

·holds(lighLon, res( unplug, s2)) <- ·holds(power, res( unplug, s2)) holds(lighLon, res( unplug, s2)) <- ·holds( open, res( unplug, s2))

The first rule justifies ·holds(lighLon, res( unplug , s2)) because of the effect rule and the second rule will jus­ tify holds( light_on, res( unplug, s2)) based on the inertia rule:

·holds( open, res( unplug, s2)) <- ·holds( open, s2), not abo(open',unplug,s2), not ab1 (open', unplug, s 2)

The literal --,holds( open, s2 ) is part of the initial database, open' will never appear in the first argument of any ab0 in the translation and ab1 is irrelevant in the example. 0

Example 3.3 In this final example, we show the cor­ rect representation of the problem. We need the causal laws (1), (2), (5) and (6), plus the defeasible sufficiency propositions:

open normally suffices for ·lighLon ·open normally suffices for lighLon

In this case the second non-defeasible sufficiency rule from the previous example is replaced by the rule

holds( lighLon, res( unplug, s2)) <- ·holds( open, res( unplug, s2)), not abo(ligt 0 n, unplug, s2)

and this rule will not be justified since the following rule is also part of the translation

abo(lighLon, unplug, s2) <------, holds(power, 1'es(unplug, s2))

which is justified by (12).

D

Observe that the translation presented above is equiv­ alent to a simpler version where, we replace both ab0 and ab1 by ab, and in the first rule of step 5 we re­ place not ab0 (J, A, s) by not H olds(J, res( A, .5')). 8 This is similar to Turner's [11] use of

not H olds(f, res( A, S)) instead of an abnormal predi­ cate to define sufficiency propositions. However, with Turner's translation there is no obvious way to add de­ feasible causality to his formalism. Furthermore, the structure of our translation (compared to Gelfand's sug­ gestion) allows us to easily add more levels of defeasi­ ble propositions; i.e., defeasible propositions that can be defeated by other defeasible propositions 9 which could be also be defeated by other propositions. In general , when there are several levels of defeasibility the guard not H olds(f, res( A , S)) can be used in the last (mean­ ing highest) but one layer. All layers below that need an ab predicate. In the language A'DC the lowest layer corresponds to inertia, the next layer corresponds to the defeasible causality and the highest layer is the effect propositions and non-defeasible causality propositions.

8 This simplification was suggested by Michael Gelfond. The subtle use of the not H olds(f, res( A, S)) instead of H olds(f, res( A, S)) was first introduced in [5] to reason about actions in presence of incomplete information.

9 Geffner in [3] also deals with hierarchy of defeasible propositions by assigning non-negative integer priorities to them and then characterizes them using an approach based on infinitesimal probabilities. We plan to compare our ap­ proaches in the full paper.

4 Semantics of AVC and a logic programming translation

In this section we use the formalization of Res to present a semantics of A'DC which allows us to make inferences about the effect of a sequence of actions.

An interpretation is a partial function \II from sequences of actions to states such that:

1. The empty sequence [] belongs to the domain of \II and
2. \II is prefix-closed 10 .

\II([]) is called the initial state of \II .

Given a fluent f and a state a, we say that f holds in a (!is true in a) iff E a; ·f holds in a(! is false in a) iff fl. a .

Definition 4.1 An interpretation \II satisfies the causal laws of D if for any sequence a o a from the language of D,

otherwise \II( a o a) is undefined.

We say \II is a causal model of D if it satisfies the causal laws of D. D

We say an initial proposition of the form initially f is true in an interpretation \II iff is true in \li(O) .

Definition 4.2 An interpretation \II will be called a model of a domain description D in A 'DC if the following conditions are satisfied:

1. \II is a causal model of D.

A query in AVC is an expression of the form

where, f is a fluent literal and a; 's are actions .

Definition 4.3 We say a query of the form (13) is true in an interpretation \II iff is true in \ll([a1, ... , an]).

We say D f= f after a1, ... , an iff is true in all models of\ll([al , ... , an]). D

10 By "prefix closed" we mean that for any sequence of ac­ tions a and action a, if a o a is in the domain of IJ! then so is 0'.

4.1 Logic programming characterization

We can modify the translation II(D, a, s) to give a logic programming characterization of A'DC. (Note that II(D, a, s) only characterizes the effect of a single ac­ tion and to characterize A'DC we need to be able to reason about sequences of actions.) We introduce a new predicate p_holds (which intuitively means 'possibly holds') and replace all occurrences of holds(!, res( a, s)) and ·holds(!, res( a, s)) in the steps 1, 3, 4 and 5, and the head of the rules in step 2, by p_holds(f, res( a, S)) and p_holds(f', res( a, S)). We then modify step 2 by re­ placing the constants a and s, by the variables A and S. Then, we add the following rules: 11

The first rule verifies if the effects produced by actions when we are trying to reach the situation S are contra­ dictory. This indicates that S should be unreachable. The second rule says that S is reachable otherwise. 12 And , finally we add rules to make sure that sufficiency propositions are true w.r.t. the initial state so. For a non-defeasible sufficiency proposition of the form (10) we add the rules:

For defeasible sufficiency propositions of the form ( 11) we add the rule:

Let us refer to the resultant program as II( D).

Proposition 4.1 For any domain description D with complete information about the initial state

5 Defeasible effect propositions

Our new approach of defining the semantics of the ac­ tion language as a logic program gives us the flexibility to directly add defeasible effect propositions to A'DC. Consider the following effect proposition.

open_faucet causes water _on_sink.

However , in the rare occasion when the pipe is blocked the action will not have any effect 13 . A better description for the effect proposition would be:

11 Similar to H old8(f, 8 ), the atom p_H old8(f, 8) denotes the literal p_hold8{f, 8) iff is a positive fluent literal and the literal p_hold8(7, s) if f is a negative fluent literal.

12 T his indirect definition of reachable is to be able to rep­ resent 'i(F)(p_hold8(F, S), p_hold8(F', S)) in the logic rules.

13 Note the similarity to McCarthy's example of the potato in the pipe.

open_faucet normally _causes water _on_sink.

The constraint about the case when the pipe is blocked can then be specified as:

pipe_blocked suffices for ·water _on_sink .

In general, we will call a defeasible effect proposition an expression of the form

where a is an action, and f and and each of Pl , . .. , Pn (0 ~ n) is a fluent literal.

To describe the semantics of a domain description D with defeasible effect propositions we expand the pro­ gram II(D, a, s) as follows.

6. Translating Defeasible Effect propositions

For each defeasible effect proposition of the form (14) in D which describes the effect of the action a, II(D, a, s) contains the following rules:

We also need to add to the two rules of the translation of non-defeasible sufficiency propositions the following rule (step 4 of the original transformation):

To expand the logic programming characterization of ADC domains we merely need to replace the Holds in the rules of part (6) with the corresponding p_holds and proposition 4.1 holds for the new domain descriptions.

In the above formalization we assumed that defeasible ef­ fect propositions are overridden by non-defeasible causal rules and defeasible effect propositions do not contradict with non-defeasible effect propositions . A different for­ malization can be given when we modify the assumptions such as (i) allowing defeasible effect propositions to con­ tradict with non-defeasible effect propositions and giving non-defeasible effect propositions a higher priority; (ii) giving effect propositions higher priority than sufficiency propositions. The new formalizations will mainly express the priority between the different abnormal predicates. We will discuss this in greater detail in the full paper.

6 Conclusion

We have showed how to formalize defeasible causality in action theories. We used logic programming to encode the defeasible causalities. It is not clear to us if use of a logical formalism can be avoided (in the spirit of A [5]) while encoding defeasibility, particularly when we allow several level of defeasibility. In the full paper we will add additional examples involving several levels of defeasibil­ ity and discuss how defeasibility can be incorporated in other specification languages. To make our point clear we avoided additional constructs and features. Most of these can be easily added to the proposed language, and we will need default logic (as in [11]), instead of logic pro­ gramming, to encode defeasibility when we allow fluent formulas instead of fluent literals.