Updates, actions, and planning

1 Introduction

Three subareas of AI seem significantly connected and still, in the literature, work in each of these areas has been so far disconnected, up to a few exceptions. These areas are (a) belief update, (b) reasoning about action and change, and (c) planning in nondeterministic environments.

Belief update (a) mainly focuses on determining how a belief state should evolve after adding a new piece of information reflecting an explicit evolution of the world; how beliefs persist is studied in depth (this often - yet not always - relies on an assumption of minimal change), as well as causality and dependence between pieces of information; in particular, disjunctive information (reflecting uncertainty about the world after update) is taken into account, and many theoretical results exist (characterization of operators thanks to representation theorems, and computational complexity results).

Reasoning about action (b) focuses on the nature of pieces of information to take account for (preconditions for executability, direct changes, indirect changes or ramifications, static laws of the domain) and on the nature of the actions themselves (determinism, conditional effects, normal and/or exceptional effects, concurrent execution...) using sophisticated languages, generally more expressive than those of belief update but slightly less worked from a theoretical point of view (especially to what concerns representation theorems and complexity results - yet some results exist).

Finally, while (a) and (b) care on determining the consequences on the agent's current belief state of, respectively, a new piece of information and the execution of an action, most of the previous works about planning (c) are centered on plan generation; algorithmic developments have been pushed forward especially when actions are very simple - like in STRIPS - but less so when they are more complex 1 .

Our purpose is to show how existing works on belief update can be extended so as to represent complex actions representations and planning in nondeterministic environments.

After some formal preliminaries (Section 2), we introduce in Section 3 a new family of update operators based on literal dependence. Such operators generalize existing dependencebased operators but grasp in a better way the incorporation of the effects of an action in a belief base. Interestingly, this generalization has no influence on computational properties since the complexity of query entailment from an updated belief base is just as hard as classical entailment in the general case (unlike other operators like Winslett's PMA - unless the polynomial hierarchy collapses). Then we show in Section 4 how the effects of more sophisticated (ontic) actions can be represented in our framework by generalizing our family of update operators to deal with conditionals, nondeterminism (distinct from disjunction!) and concurrency; this establishes a closer parallel between updates and effects of complex actions such as considered in action languages. In Section 5, we show how to use our (extended) update operators so as to compute the effect of a (possibly conditional) plan in a nondeterministic domain. We successively consider the case where the environment is fully observable and unobservable. Complexity results for plan verification and plan existence are given for both cases. Finally, connections to relatedwork are discussed in Section 6, before the concluding section.

2 Formal preliminaries

We consider a propositional language CA CB built up from a finite set CB of propositional variables and the boolean constants BQ and BR. Propositional formulas are denoted by BTBNBU etc. and interpretations over CB (or worlds) are denoted by AX etc. We represent them as tuples or conjunctions of literals over CB. In the following, we will identify every propositional formula BT with its set of models D3CSB4BTB5.

Let 
CC be the set of literals of the language, i.e., 
CC BP CB DCBECB CUDCBN BMDCCV. We recall that a formula BT is in Negative Normal Form iff it makes use of the connectives CM, CN, BM, only and the scope of negation connectives appearing in BT includes propositional symbols only. For instance, BT BP BMB4B4BMCP CM CQB5 CN B4CP CM CRB5B5 is equivalent to the NNF formula B4CP CN BMCQB5 CM B4BMCP CN BMCRB5 2 . BTCJDC AW BVCL denotes the formula obtained by uniformly replacing every occurrence of propositional variable DC by the formula BV. BTCJD0 AW BVCL denotes the formula obtained by replacing in a uniform way every positive (resp. negative) occurrence of literal D0 in the NNF of BT by BV (resp. BMBV). We denote by CXD8B4BTB5 AI 
CC the set of literals appearing in the NNF of BT. In the previous example, CXD8B4BTB5 BP CUCPBN BMCPBN BMCQBN BMCRCV. For any  AI 
CC , we note BXBZB4B5 BP CUBMD0 CY D0 BE CV, supposing BMBMDC identified with DC. Lastly, if AX is a world and  a consistent set of literals from 
CC , then BYD3D6CRCTB4AXBN B5 is the world that gives the same truth value as AX to all variables except the variables of literals of  and BYD3D6CRCTB4AXBN B5 CYBP CE D0BE D0. For instance, if AX BP B4CPBN BMCQBN CRBN CSB5 and  BP CUCQBN BMCSCV then BY D3D6CRCTB4AXBN B5 BP B4CPBN CQBN CRBN BMCSB5.

1 Only a few recent works such as [McCain and Turner, 1998], [Rintanen, 1999] and [Ferraris and Giunchiglia, 2000] considered planners with nondeterministic actions represented in sophisticated action languages.

A belief update operator A5 maps the propositional belief base (a formula) BU representing the initial beliefs of a given agent and an input formula BT reflecting some explicit evolution of the world [Katsuno and Mendelzon, 1991], to a new set of beliefs BU A5 BT held by the agent after this evolution has taken place. Katsuno and Mendelzon [Katsuno and Mendelzon, 1991] proposed a general semantics for update. The most prominent feature of KM updates (distinguishing updates from revision) is that update must be performed modelwise, i.e., D3CSB4BU A5BTB5 BP CB AXCYBPBU AX A5BT.

Finally, we assume the reader familiar with some basic notions of computational complexity (see [Papadimitriou, 1994] otherwise).

3 A new family of dependence-based updates

Many proposals for update operators have been made. Recently, several authors showed that there are good reasons for building a belief operator from a dependence relation [Doherty et al., 1998] [Herzig and Rifi, 1999]. The dependencebased update of a belief base BU by an input formula BT consists in first forgetting in BU all information "relevant" to BT (leaving unchanged the truth value of variables not relevant to the update), and then expanding the result with BT. What remains to be defined is the notion of "being relevant to".

3.1 Formula-variable dependence

A formula-variable dependence function is modelled a mapping BWCTD4 from CA CB to BE CB . Many choices for BWCTD4 are possible (see [Herzig and Rifi, 1999] for details). Whatever the choice, the dependence-based update of a world AX by a formula BT w.r.t. BWCTD4, denoted by AX A5 BWCTD4 BT, is the set of all worlds AX BC such that AX BC CYBP BT, and for every propositional variable DC from CB such that DC BIBE BWCTD4B4BTB5, AX and AX BC assign the same truth value to DC.

Interestingly, the complexity of query entailment from an updated belief base is "only" coNP-complete when dependence-based updates are considered [Liberatore, 2000]

2 Note that when BT is built up from the connectives CM, CN, BM, B5, it can be turned into an equivalent NNF formula in linear time by "pushing down" every occurrence of BM and removing double negations. Abusing words, we call the resulting formula the NNF of BT.

while entailment when most usual other operators - like Winslett's PMA - are used is at the second level of the polynomial hierarchy.

3.2 Formula-literal dependence

Forgetting everything about the variables involved in the update often leads to forgetting too much. Consider a robot being told to go to a room with two doors 1 and 2, and to ensure that at least one of them is red (possibly by painting one of the doors), which can be represented as an update by red1CNred2. Suppose now that both doors are initially red: BU BP red1CMred2. Then, using any dependence function BWCTD4 s.t. CUred1, red2CV AI BWCTD4B4red1CNred2), we get BUA5 BWCTD4 (red1CNred2) = red1CNred2. Thus, we forgot that both doors were already red. Clearly, this is not what is expected: intuitively, we should not forget that doors 1 and 2 are red, because updating by red1CNred2 has no negative influence on red1 nor on red2. Hence, only negative occurrences of red1 and red2 should be forgotten before expanding by the input formula, not positive ones.

This may not be a problem in some contexts, but clearly, when reasoning about actions, these update operators make us forget too much and therefore do not handle the frame problem correctly. In order to cope with this limitation, we introduce a new family of dependence-based update operators. Such operators generalize existing ones because they are based on formula-literal dependence [Lang et al., 2000], a more general notion than formula-variable dependence.

¿From now on, a formula-literal dependence function is a mapping BWCTD4 BM CA CB AX BE 
CC . Many full-sense BWCTD4 can be considered. Like formula-variable dependence functions, BWCTD4B4BTB5 can be basically defined as CXD8B4BTB5 or BWCTD4CXD8B4BTB5, where the latter is defined as follows:

Definition 1 (FL independence) [Lang et al., 2000] Let BT be a formula from CA CB and D0B4BP DC or BMDCB5 be a literal from 
CC. BT is literal-independent of DC iff BTCJDC AW BQCL AH BT, and BT is literal-independent of BMDC iff BTCJDC AW BRCL AH BT. Finally, BT depends on D0 iff it is not literal-independent of D0. We denote by BWCTD4CXD8B4BTB5 the set of literals BT depends on.

Thus, BT BP B4CPCNCQB5CMB4BMCPCNCRB5CMB4CPCNCQCNBMCRB5 is literal-dependent on CP, BMCP, CQ and CR; but not on BMCR, because it is equivalent to B4CP CN CQB5 CM B4BMCP CN CRB5, and BMCR does not appear in the NNF of the latter.

More sophisticated dependence functions can also be designed by considering explicit dependence (binary) relations Æ on 
CC. One of them is BWCTD4B4BTB5 BP CB D0BECXD8B4BTB5 ÆB4D0B5 (and similarly with BWCTD4CXD8B4BTB5). We can also take into account persistent literals, i.e., literals remaining true whatever happens, such as BM alive (contrarily to alive). For example, BWCTD4B4BTB5 BP BWCTD4CXD8B4BTB5 CK BXBZB4 CTD6D7B5 where  CTD6D7 is a given set of persistent literals is a possible dependence function. Clearly, persistent literals cannot be taken into account by formula-variable dependence. The other way round, every formula-variable dependence function can be simulated by a formula-literal dependence function.

3.3 Update based on formula-literal dependence

Definition 2 The update AX A5 BWCTD4 BT of the world AX by the formula BT w.r.t BWCTD4 is the set of all worlds AX BC s.t. AX BC CYBP BT and there exists  AI BWCTD4B4BTB5 s.t. AX BP BY D3D6CRCTB4AX BC BN BXBZB4B5B5.

The next result gives us a way to compute BU A5 BWCTD4 BT BP CB AXBED3CSB4BUB5 AX A5 BWCTD4 BT in practice. We first need to define literal forgetting [Lang et al., 2000].

Definition 3 (literal forgetting) For a formula BU and  AI 
CC , BYD3D6CVCTD8CXD8B4BUBN B5 is the formula inductively defined by

Proposition 1

BU A5 BWCTD4 BT AH BT CM BY D3D6CVCTD8CXD8B4BUBN BXBZB4BWCTD4B4BTB5B5B5.

Example 1 BU BP B4BMCPCNBMCSB5CMB4CPCNCQB5CMB4CPCNCRCNCSB5, BT BP CS and let us take BWCTD4 BP BWCTD4CXD8. We have BY D3D6CVCTD8CXD8B4BUBN BWCTD4B4BTB5B5 BP BY D3D6CVCTD8CXD8B4BUBN CUCSCVB5 BP B4BMCPCNBMCSB5CMB4CPCNCQB5; hence BUA5 BWCTD4 BT AH CS CM BMCP CM CQ.

Interestingly, for all the update operators based on literal dependence listed above, we have the following complexity result (this slightly extends Theorem 15 from [Liberatore, 2000])):

Proposition 2 Given three formulas BT, BU and BV, BU A5 BWCTD4 BT CYBP BR BV is coNP-complete.

If BWCTD4CXD8B4BTB5 AI BWCTD4B4BTB5, then BT and BYD3D6CVCTD8CXD8B4BUBN BXBZB4BWCTD4B4BTB5B5B5 are strongly separable, in the sense that, if D0 BE BWCTD4CXD8B4BTB5, then BMD0 BIBE BWCTD4CXD8B4BYD3D6CVCTD8CXD8B4BUBN BXBZB4BWCTD4B4BTB5B5B5B5 holds. This is an important property from a computational point of view when CNF queries are considered since:

Proposition 3 If BV and BW are two strongly separable formulas, then they are separable in the sense of Levesque [Levesque, 1998], i.e., for every clause BX, we have BV CMBW CYBP BX iff BV CYBP BX or BW CYBP BX.

Accordingly, one global entailment test can be replaced by two local (simpler) entailment tests, and exponential savings can be achieved this way in practice. Now, clausal entailment from a BY D3D6CVCTD8CXD8 formula reduces to clausal entailment from a classical formula:

Proposition 4 Let BX be a non-tautological clause. Then BYD3D6CVCTD8B4BUBN B5 CYBP BX iff BU CYBP CF D0BECXD8B4BXB5D2 D0.

Alltogether, the two previous propositions give us some tractable restrictions for clausal query entailment from an updated belief base. Let us say that a formula is tractable when it belongs to a class of formulas for which clausal entailment is known as tractable (e.g., the Horn CNF class). When A5 BWCTD4 satisfies BWCTD4CXD8B4BTB5 AI BWCTD4B4BTB5, BT is a tractable formula for which literal-(in)dependence can be tested in polynomial time and BU is a tractable formula, then determining whether BU A5 BWCTD4 BT CYBP BV can be achieved in polynomial time for every CNF formula BV. This is the case for instance when BWCTD4 BP BWCTD4CXD8, BU is a Horn CNF formula and BT is a set of binary clauses 3 .

3 Here, clausal entailment from the updated base BUA5 BWCTD4 BT is even easier than clausal entailment from the corresponding expanded base BU CMBT since determining whether BTCMBU CYBP BV is coNP-complete in this situation - tractable classes are known not to mix well.

4 Updates and actions

The aim of this section is to show that belief update is not far from being able to determine the effects of an arbitrary action. In order to do so, we introduce the notion of extended input.

Definition 4 (extended inputs) Extended inputs are defined inductively as follows:

• AF every formula BT of CA CB is an extended input;
• AF if A8andA9are extended inputs thenA8CJA9 is an extended input (nondeterminism);
• AF if A8 and A9 are extended inputs then A8CYCYA9 is an extended input (concurrency);
• AF if A8 and A9 are extended inputs and BV is a formula of CA CB then if BV then A8 else A9 is an extended input (conditional).

Definition 5 (updates by extended inputs) Let A5 be an arbitrary update operator, AX a world and A8 an extended input. We define the update of AX by A8 inductively as follows:

• AF if BT BE CA CB , then AX A5BT is given by the definition of A5;
• AF AX A5 B4A8 CJ A9B5 BP B4AX A5 A8B5 CJ B4AX A5 A9B5;
• AF AX A5 CXCU BV D8CWCTD2 A8 CTD0D7CTA9BP AQ AX A5A8 CXCU AX CYBP BV AX A5A9 CXCU AX CYBP BMBV
• AF AX A5 B4A8CYCYA9B5 BP AX A5 B4A0B4A8CYCYA9B5B5 where A0B4A8CYCYA9B5B5 is defined inductively by:

AXA5B4A8CJA9B5 is a nondeterministic update, namely, AX is nondeterministically updated by A8 or by A9. This has been first introduced by Brewka and Hertzberg [Brewka and Hertzberg, 1993], who have observed that AX A5 B4BT CJ BUB5 is in general different from AX A5 B4BT CN BUB5. In the case where A8 BP BT and A9 BP BU are simple propositional formulas, updating AX by BT CJ BU intuitively means that a nondeterministic action has been performed, whose possible effect is either BT or BU, and that (quoting from [Brewka and Hertzberg, 1993]) the planner has no way to know whether one of the postcondition is already satisfied and nondeterministically choose to update by BT or by BU. A first example is the toss action, representable by the extended input head CJ BM head. Another example (adapted from [Brewka and Hertzberg, 1993]): recall the red doors example (Section 2). If the robot is told to paint door 1 or door 2 in red but has no way to know whether one of the doors is already red (because it has no sensors), then the action should be modelled by red1 CJ red2. On the other hand, the action consisting of an update by red1 CNred2 corresponds to a context where the robot can check whether one of the doors is initially red (and leaves the world unchanged if this is the case). The introduction of these two kinds of nondeterministic actions needs both standard disjunction and CJ. Note that we have BU A5 B4BT CJ BVB5 AH B4BU A5 BTB5 CN B4BU A5 BVB5.

AX A5 CXCU BV D8CWCTD2 A8 CTD0D7CT A9 is a conditional update: the initial model is updated by A8 or by A9 depending on whether AX

satisfies the branching condition BV or not. In the case where A8 BP BT and A9 BP BW are simple propositional formulas, we have BUA5CXCU BV D8CWCTD2 BT CTD0D7CT BW AH B4BUCMBVB5A5BTCNB4BUCMBMBVB5A5BW. Conditional updates are needed for action with conditional effects, such as the well-used turkey shooting action, which corresponds to an update by if loaded then (BMalive CMBMloaded) else BQ. Conditional actions are not well handled with pure unconditional updates.

AX A5 B4A8CYCYA9B5 is a concurrent update. It basically works by gathering conjunctively all possible combinations of alternative results, and then performing the corresponding updates separately; in particular, BU A5 B4B4BT BD CJ BT BE B5CYCYB4BU BD CJ BU BE B5B5 AH BUA5B4BT BD CMBU BD B5CNBUA5B4BT BD CMBU BE B5CNBUA5B4BT BE CMBU BD B5CNBUA5B4BT BE CMBU BE B5. This can be easily generalized to the case where more than two extended inputs must be considered as concurrent update formulas. Concurrent updates aim at representing compactly independent effects of actions. Consider the action of loading the gun which has two independent effects, namely: (1) the gun is loaded and (2) the turkey goes hiding if it is not deaf. It corresponds to the concurrent update by AB BP (loaded CYCY if BMdeaf then hidden else BQ). Concurrency can as well be used for concurrent (or parallel) actions 4 .

Consider parallel actions having some inconsistent effects. As the effect of the update by their combination is an empty set of models, this has no impact on the final result. This means that our notion of action compatibility is very loose. For instance, if AX BP B4CPBN CQBN CRB5 and if we have two actions AB and AC corresponding to the extended inputs AB BP B4CP CM CQB5 CJ B4CP CM CRB5 and AC BP BMCP CJ BMCQ then AX A5 B4ABCYCYACB5 BP B4AX A5 BRB5 CJ B4AX A5 BRB5 CJ B4AX A5 BRB5 CJ B4AX A5 B4CP CM BMCQ CM CRB5B5 BP CUB4CPBN BMCQBN CRB5CV. More precisely, two nondeterministic actions AB BP BT BD CJ BMBMBM CJ BT D4 and AC BP BU BD CJ BMBMBM CJ BU D5 are compatible (i.e., concurrently executable) iff there is an effect BT CX of AB and an effect BU CY of AC such that BT CX CMBU CY is consistent 5 .

The previous definition is independent of the choice of a particular update operator. In the case of a dependence-based operator, the complexity results established in Section 3 enable us to say that the prediction problem (i.e., the problem of determining if the execution of an action in a given belief state leads to satisfying a given formula) is coNP-complete 6 .

Note that usual ramification methods, such as the use of integrity constraints or causal rules (see [Doherty et al., 1998] for their handling in an update framework) can be added on top of our framework. We do not discuss them since it is not a contribution of our paper.

4 Note that our notion of concurrency differs from concurrency in dynamic logic which is defined by B4AXA5A8B5CKB4AXA5A9B5. Like in language BV [Giunchiglia and Lifschitz, 1998], concurrency means that the effects of the concurrent actions must be gathered before being used as inputs for belief update. Consider for instance the two actions "open the door" and "open the window", corresponding to the updates door and window, applied concurrently to the initial state AX BP B4BM door BN BM windowB5. For any dependence-based update operator A5 for which door and window are independent we get AXA5 door BP B4 doorBN BM windowB5, AXA5 window BP B4BM doorBN windowB5, and thus B4AXA5 doorB5 CK B4AXA5 windowB5 BP BN, while with our definition we get the intended result AX A5 B4door CYCY windowB5 BP AX A5 B4door CM windowB5 BP B4doorBN windowB5.

5 Other notions of compatibility can be represented in our framework. They are not developed further due to space limitations.

6 If the update operator was instead A5 D4 BE -complete, as many operators are, then extended update would be A5 D4 BE -complete too.

5 Update-based planning

5.1 Definitions

In the following, we consider standard ontic actions, which are meant to act on the world, and do not have any other effects on the knowledge state of the agent than the realization of its ontic effects. In our framework, a standard ontic action AB is described by an extended input, denoted by AB as well (thus, we identify the action and its effects, which will not lead to ambiguities), and determining its effects on a world AX simply consists in updating AX by AB.

What is missing now in order to define a plan is the notion of update sequences.

Definition 6 (plans) Given a finite set of standard ontic actions BTBVCC  , (branching) plans are defined inductively by:

• AF AL (empty plan) is a plan;
• AF for any extended input AB BE BTBVCC  , AB is a plan;
• AF if AP BD and AP BE are plans, then AP BD BN AP BE is a plan;
• AF if AP BD and AP BE are plans and BV is a propositional formula, then if BV then AP BD else AP BE is a plan.

Thus, plans are sequential and conditional extended updates (these extended updates being themselves conditional, nondeterministic and concurrent) 7 . At the plan level, nondeterministic choice and parallel composition are not allowed.

Definition 7 (planning problems) A planning problem is a triple  BP CW
BN BTBVCC  BN BZCX where:

• AF
  is a propositional formula representing the knowledge on the initial state;
• AF BTBVCC  BP CUAB BD BN BMBMBMBN AB D5 CV is a set of standard ontic actions;
• AF BZ is a propositional formula representing the goal.

Note that these definitions do not mention anything regarding observability. They can therefore be used as generic definitions. What changes when various assumptions about observability are made is the type of plans allowed. When full observability is assumed, any branching is allowed, while with unobservability, branching is never allowed. With partial observability we may branch only on conditions whose truth value can be determined by the agent.

Definition 8 (trajectories) A trajectory AS is a nonempty sequence AS BP CWAX BC BN BMBMBMBN AX CC CX of models (CC AL BC). If AS BP CWAX BC BN BMBMBMBN AX CC CX, then D0CTD2CVD8CWB4ASB5 BP CC. If AP is a plan and
an initial knowledge base, AS is a possible trajectory for (
, AP) w.r.t. BTBVCC  iff (1) AX BC CYBP
and (2) one of the following conditions holds:

1. AP BP AL and CC BP BC; 2. AP BE BTBVCC  and CC BP BD and AX BD BE D3CSB4AX BC A5 APB5;

7 Note that if .. then .. else is used both at the action and at the plan levels. Formally, both structures are identical but both kinds of conditionals do not share the same purpose; especially, observability considerations may restrict the range of allowed branching conditions at the plan level, but not at the action level.

1. AP BP AP BD BN AP BE and AS can be decomposed in two subtrajectories AS BD BP CWAX BC BN BMBMBMBN AX CX CX, AS BE BP CWAX CX BN BMBMBMBN AX CC CX, s.t. AS BD is a possible trajectory for (
   BN AP BD ), and AS BE is a possible trajectory for B4AX CX BN AP BE B5);
2. AP BP if BV then AP BD else AP BE and
3. AF either AX BC CYBP BV and AS is a possible trajectory for B4
   BN AP BD B5
4. AF or AX BC CYBP BMBV and AS is a possible trajectory for B4
   BN AP BE B5.

Definition 9 (succeeding plans) A plan AP is a succeeding plan for a planning problem  BP CW
BNBTBVCC  BNBZCX iff every possible trajectory AS for B4
BN APB5 is s.t. AX D0CTD2CVD8CWB4ASB5 CYBPBZ.

5.2 Fully observable environments

Under full observability, any plan is allowed. Let us consider the complexity of plan verification and existence.

Proposition 5 (complexity of plan verification/existence)

Suppose that the update operator used A5 is one of the dependence-based operator given in the previous sections.

1. determining whether AP is a succeeding plan for  BP CW
   BNBTBVCC  BNBZCX is coNP-complete;
2. determiningwhether there exists a succeeding planAP for  BP CW
   BNBTBVCC  BNBZCX is EXPTIME-complete, and determining whether there exists a succeeding plan AP of polynomially bounded length for  is PSPACE-complete.

Point 1. is a key result. It is a strong generalization of Theorem 20 from [Liberatore, 2000]. Point 2. is easier to establish: the upper bounds are a byproduct of Point 1., and the lower bounds are derived from Littman's results on probabilistic planning [Littman, 1997]. These results (especially Point 1.) show that update-based planning in fully observable environments is not harder than STRIPS-based nondeterministic planning, which (somewhat) means that the facilities brought with the use of update are "for free".

5.3 Unobservable environments

Definition 10 (unbranching plans) An unbranching plan is a (possibly empty) sequence AB BC BN BMBMBMBN AB CC of standard ontic actions, or equivalently a plan in which no if ... then ... else appears at the outer level 8 .

Trajectories and succeeding plans are defined the same way as above. The following property, reformulating succeeding plans in terms of iterated updates, is almost straightforward:

Proposition 6 Let AP BP AB BD BN BMBMBMBN AB CC be an unbranching plan, and  BP CW
BNBTBVCC  BNBZCX a planning problem. Then AP is a succeeding plan for  iff B4B4BMBMB4
A5 AB BD B5 A5 AB BE B5 A5 BMBMBMB5 A5 AB CC CYBP BZ.

Proposition 7 (complexity of plan verification/existence)

Suppose the update operator used A5 is one of the dependencebased operator given in the previous sections.

1. determining whether an unbranching plan AP is a succeeding plan for  BP CW
   BN BTBVCC  BN BZCX is coNP-complete.

8 However, if ... then ... else may appear inside the extended inputs, for representing conditional effects.

1. determining whether there exists a succeeding unbranching plan AP for  BP CW
   BNBTBVCC  BNBZCX is EXPSPACE-complete, and determining whether there exists a succeeding unbranching plan AP for  of polynomially bounded length is A6 D4 BE -complete.

The EXPSPACE-hardness result is a direct consequence of a result from [Haslum and Jonsson, 1999]. The latter point (A6 D4 BE -completeness) is similar to results in [Baral et al., 1999] and in [da Costa et al., 1997], which again suggests that dependence-based updates can be added "for free".

6 Related work

[Brewka and Hertzberg, 1993] were the first to use belief update operators for representing actions with conditional and nondeterministic effects. In Sections 3 and 4, we truly follow in their steps. They use Winslett's PMA update operator, which has been shown in many places to possess severe drawbacks (both from the points of view of expressivity and complexity). By making use of further advances in belief update, especially in what concerns dependence-based update, we were able to go much further than they did towards the practical computation of plans (and as well by allowing for concurrent actions, conditional plans and epistemic actions). See also the transition-based update-like operators of Cordier and Siegel [Cordier and Siegel, 1995].

[Fargier et al., 2000] use dependence-based update for one-stage decision making processes (that can be viewed as degenerated planning problems). Their use of a formulavariable dependence is, as we show in Section 3, not the best choice for reasoning about action, and they do not use nondeterministic updates, nor sequences of updates.

[del Val and Shoham, 1994] point out some correspondances between the Katsuno-Mendelzon postulates and generic properties of action (by rewriting KM postulates in the situation calculus and showing that each KM postulate can be expressed as a specific property of actions), which enable them to give some intuitive reasons to accept or reject some of the KM postulates. Rather than practically proposing action languages based on belief update operators as we did, their work remains at the meta-level and made us think that such an update-based framework for planning was feasible.

[Shapiro et al., 2000] represent iterated updates as well as epistemic actions in the situation calculus. They distinguish between ontic actions (leading to updates) and epistemic (leading to revisions). They represent the set of possible worlds (or situations) explicitly, while, using STRIPS-like representation and a propositional formalism, we represent it in a compact way, which makes our framework very different from theirs.

A line of work which is parallel to ours is the planning as satisfiability frameworks with actions languages, especially [Giunchiglia, 2000] based on the language BV and [McCain and Turner, 1998] based on the causal theory developed by the authors. The main differences between these languages and update is in the handling of disjunction: the literal completions used in [Giunchiglia, 2000] and [McCain and Turner, 1998] require that dynamic laws expressing the effects of actions have a single literal in their head. The exact links between these expressive languages and belief update is an interesting topic for further research. [Geffner, 1996] also makes use of causal theories for actions and planning, and uses plausibility functions to distiguish various levels of exceptionality in the effects of actions.

7 Conclusion

In this paper, we have presented a new update-based framework for planning. Our contribution is manyfold. We have introduced a new family of dependence-based update operators, based on formula-literal dependence, which includes existing dependence-based operators as specific cases, suits better the needs of reasoning about action, and whose computational complexity is not being above that of classical entailment. We have also shown how belief update has to be augmented with conditionals, nondeterminism and concurrency in order to be fully adapted to the representation of actions. Third, we have shown how to define (conditional or unconditional) plans in our framework. Finally, we have shown that the complexity of plan verification and existence in our framework is not higher than with a STRIPS-like representation.

This work calls for several perspectives. One of them concerns the introduction of partial observability in our framework. The simplest way to do it consists in considering that a fixed set of formulas is directly observable; allowed branching conditions are in this case formulas whose truth value can be determined from the truth values of these formulas. A more expressive solution consists in allowing for epistemic actions in the framework. Unlike ontic actions, epistemic actions leave the world unchanged and therefore do not imply an update, but instead, a knowledge expansion. In order to distinguish between facts and knowledge, an epistemic modality  can be introduced. Plans can be defined in a similar way as before except for branching conditions, for which we allow only for epistemically interpretable branching conditions as in [Herzig et al., 2000].

Acknowledgements

The third author has been partly supported by the IUT de Lens and the R´egion Nord/Pas-de-Calais.