Conditional progressive planning under uncertainty

1 Introduction

In this article, we describe a conditional planner called PTLplan. A conditional planner does not presuppose that there is complete information about the state of its environment at planning time, but that more information may be available later due to sensing, and that this new information can be used to make choices about how to proceed. Hence, a conditional planner generates plans that may contain conditional branches. In addition, PTLplan can handle degrees of uncertainty, either in possibilistic or in probabilistic terms. The "P" in PTLplan stands for exactly that.

PTLplan is a progressive (forward-chaining) planner; it starts from an initial situation and applies actions to that and subsequent resulting situations, until a situation where the goal is satisfied is reached. Being progressive, PTLplan has the disadvantage that the search space is potentially very large even for small problems The advantage is that PTLplan can reason from causes to effects, and always in the context of a completely specified situation. The latter makes it possible to apply a technique that can reduce the search space considerably: the use of strategic knowledge that helps pruning away unpromising plan prefixes.

PTLplan builds on a conditional planner ETLplan [Karlsson, 2001], which in turn built on a sequential (nonconditional) planner called TLplan [Bacchus and Kabanza, 1996; 2000] ("TL" stands for "temporal logic"). Two of the features that makes TLplan interesting are its fairly expressive first-order representation and its good performance due to its use of strategic knowledge. The latter is indicated by its outperforming most other comparable planners in empirical tests, as has been documented in [Bacchus and Kabanza, 2000]. ETLplan added two features to TLplan:

•  The representation of actions and situations used in ETLplan permitted actions that have sensing effects, that is the agent may observe certain fluents (state variables).
•  Based on these observations, the planning algorithm could generate conditional plans.

In addition to these features, PTLplan also incorporates:

•  Assignments of degrees of uncertainty, either in possibilistic or probabilistic terms, to effects, observations and situations/states.
•  Based on these degrees, measures of how likely a plan is to succeed or fail. In the absence of plans that are completely certain to succeed, PTLplan is still capable of finding plans that, although they may fail, are likely enough to succeed.

PTLplan is the first progressive planner utilizing strategic knowledge to incorporate the features mentioned above, and as indicated by tests, it does so successfully. In the rest of the article, we describe the plan representation of PTLplan, the use of strategic knowledge and the planning algorithm, and we also briefly provide some data from performance tests.

2 Related work

Planning in partially observable domains has been a hot topic since the mid 90's. There has been a good amount on work on POMDPs (partially observable Markov decision processes), see e.g. [Kaebling et al., 1998]. POMDPs typically utilize explicit enumerations of states, but there are also results on the use of more compact propositional representations [Boutilier and Poole, 1996]. Note that this work is on the more general problem of generating policies that maximize utilities, and not plans with sequences and branches that achieve goals.

One of the earliest conditional probabilistic systems originating from classical planning was the partial-order planner C-BURIDAN [Draper et al., 1994], which had a performance which made in impractical for all but the simplest problems. The partial-order planner MAHINUR [Onder and Pollack, 1999] improved considerably on C-BURIDAN by handling contingencies selectively. MAHINUR focuses its efforts on those contingencies that are estimated to have the greatest impact on goal achievement. C-BURIDAN and MAHINUR are regressive planners: they perform means-ends reasoning from effects to causes.

WEAVER [Blythe and Veloso, 1997] is a system that iterates between a classical planner and a probabilistic evaluator. It can model stochastic exogenous events but not sensing.

C-MAXPLAN and ZANDER [Majercik and Littman, 1999] are two conditional planners based on transforming propositional probabilistic planning problems to stochastic satisfiability problems (E-MAJSAT and S-SAT, respectively). The latter can be solved in a highly efficient manner, in particular when certain pruning techniques are used. But, as pointed out in [Majercik and Littman, 1999], the translation from planning problems to satisfiability problems can lead to blow-ups in size and obscures the problem structure.

On the possibilistic side, there is Gu´er´e's and Alami's conditional planner [Gu´er´e and Alami, 1999], which also has been demonstrated to have a practical level of performance. Their planner is based on Graph Plan [Blum and Furst, 1995]. It assumes that sensing actions are perfectly reliable and do not have preconditions. Another Graph Plan derivative is Sensing Graph Plan (SGP) [Weld et al., 1998], which can deal with incomplete information but has no means for quantifying uncertainty.

3 Representation

3.1 Uncertainty

PTLplan can represent uncertainty either using possibility theory [Dubois and Prade, 1988] or probability theory, simply by interpreting the connectives used as follows. 1

Thus, PTLplan can be used both when one is only interested in the relative likelihood of different facts and outcomes, and when one has precise information about probabilities.

3.2 Syntax: Fluents

The state of the world is described in terms of fluents (state variables) and their values. A fluent-value formula has the form f=v, denoting that the fluent f has the value v; if the value is omitted, it is implicitly assumed to be T (true). Examples of fluent-value formulae are door(d1) and robot-at(table1)=F. A fluent formula is a logical combination of fluent-value-formulae using the standard connectives and quantifiers. A fluent-assignment formula has the form f:=v denoting that f is caused to have the value v; e.g. robot-at(table1):=F.

1 The probabilistic versions of the connectives are justified by the fact that they are only applied to mutually exclusive and independent situations or branches and Markovian transitions.

3.3 Syntax: Actions

An action schema consists of a tuple ha;; P;; Ri where a is the action name, P is a precondition (a fluent formula) and R is a set of result descriptions. Each result description r 2 R is a tuple hC;; p;; E;; Oi where

•  C is a context condition (a fluent formula) that determines when (in what states) the result is applicable.
•  p is the possibility or probability of the result.
•  E is a set of fluent assignment formulae (f:=T or f:=F) which specifies the effects of the result. We let E + denote the fluents with positive assignments in E and we let E ; be those with negative ones.
•  O is a set of fluents f, denoting that the current value of f is observed, and/or fluent-value-formulae f=v denoting that f is (correctly or incorrectly) observed to have the value v. These observations are assumed to be made by the agent executing the plan.

Note that restrictions apply to the p values; the sum of the p in applicable results must always be 1 for the probabilistic case, and the maximum of the p must always be 1 for the possibilistic case.

Example 1 The following are action schemas for the tiger scenario (the scenario is due to [Kaebling et al., 1998]). There are two doors, one to the left (ld) and one to the right (rd). Behind one of them lurks a tiger, and behind the other there is a reward. The fluent tiger(d) stands for that the tiger is behind door d. Probabilities are used.

The agent can listen at the doors, and this gives a indication of behind which door the tiger lurks. Unfortunately, there is a 15% chance of error. This is an action that yields observations but no concrete effects.

act: listen() pre: true context p effects observations res: (tiger(ld), 0.85, fg, ftiger(ld)=Tg), (tiger(ld), 0.15, fg, ftiger(rd)=Tg), (tiger(rd), 0.85, fg, ftiger(rd)=Tg), (tiger(rd), 0.15, fg, ftiger(ld)=Tg)

The agent can open one of the doors, which either leads to the reward (rew), or to tiger-induced death (dead).

act: open(?d) pre: door(?d) context p effects observations res: (:tiger(?d),1.0,frew:=Tg, frew=Tg), (tiger(?d), 1.0,fdead:=Tg,fdead=Tg)

3.4 Semantics: Situations and epistemic situations

We use a model of knowledge and action which is based on the concepts of a situation and an epistemic situation. In short, a situation describes one possible state of the world at a given point in time, where time is defined in terms of what actions has occurred. An epistemic situation, or esituation for short, is essentially a set of situations with associated possibilities/probabilities that describes the agent's knowledge at a point in time. In this PTLplan is similar to e.g. C-BURIDAN [Draper et al., 1994] which employs a probability distribution over states. A transition relation res over situations provides the temporal dimension; the transitions are due to applications of actions. The global possibility/probability of a situation s is denoted p(s). This represents the possibility/probability that some given choice of actions (plan) will lead to s. The global possibility/probability p(s) of an e-situation is computed from those of its constituents: p(s) = L s2s p(s). The local possibility/probability p l (s) of a situation s is obtained by normalizing relative to its containing e-situation s: p l (s) = p(s)=p(s). This represents the possibility/probability the agent assigns to s inside s.

The state state(s) of a situation s is a mapping from fluents to values (i.e. a set of fluents), and the observation set obs(s) is a set of fluent-value-pairs hf;; vi. We impose the constraint that all situations in an e-situation s should have the same observation set; we denote this set by obs(s).

Example 2 The initial e-situation for the tiger scenario has no observations (obs= fg), but contains two situations with associated probabilities and states. In one situationwhere p = 0:5, the tiger is behind the left door, and in the other, where p = 0:5, it is behind the right door.

obs= fg 0.5: ftiger(ld),door(ld),door(rd)g 0.5: ftiger(rd),door(ld),door(rd)g

3.5 Semantics: results of actions

The results of an operator/action A in a situation is defined as follows: for each result description hC i ;; p i ;; E i ;; O i i, if context condition C i is true in s then there is a situation s 0 resulting from s (i.e. res(s;; s 0 )) where the effects in E i occur (i.e. state(s 0 ) = (state(s)[E + i )nE ; i ) and the observations inO i are made (if f 2 O i and f has value v in s, or if "f=v" 2 O i , then hf;; vi 2 obs(s 0 )). Finally, p(s 0 ) = p(s) p i . For an epistemic situation s, the result of an action A is determined by applying A to the different situations s 2 s as above, and then partitioning the resulting situations into new e-situations according to their observation sets.

Example 3 We attempt to apply some different actions to the initial e-situation. Applying open(ld) yields the following two new e-situations (". . . " stands for "door(ld), door(rd)"):

obs= fdead=Tg 0.5: ftiger(ld),dead,. . . g obs= frew=Tg 0.5: ftiger(rd),rew,. . . g

Applying listen() to the initial e-situation yields the following two new e-situations:

obs= ftiger(ld)=Tg 0.425: ftiger(ld),. . . g 0.075: ftiger(rd),. . . g obs= ftiger(rd)=Tg 0.425: ftiger(rd),. . . g 0.075: ftiger(ld),. . . g

Note how the resulting situations are partitioned into esituations based on their observations.

3.6 Syntax: Conditional plans

Plans in PTLplan are conditional. This means that there can be points in the plans where the agent can choose between different ways to continue the plan depending on some explicit condition. Therefore, in addition to the sequencing plan operator (;), we introduce a conditional operator (cond). The syntax of a conditional plan is as follows:

plan ::= success j fail j action;plan j cond branch* branch ::= (cond : plan) action ::= action-name(args)

A condition cond is a conjunction of fluent-value formulae. The conditions for a branch should be exclusive and exhaustive relative to the potential e-situations at that point in the plan. Success denotes predicted plan success, and fail denotes failure.

Example 4 The following is a plan which is a solution to the tiger scenario (see example 6 for how it could be generated).

listen(); cond(tiger(rd)=T : open(ld); cond (rew=T:success) (dead=T:fail)) (tiger(ld)=T : open(rd); cond (rew=T:success) (dead=T:fail))

3.7 Semantics: Application of conditional plans

The application of a plan to an epistemic situation s i results in a set of new e-situations. First, the application of an action a to s i is defined as in section 3.5. Next, the application of a sequence a;p is defined as applying the first action a to s i , and then the rest of the plan p to each of the resulting e-situations. Finally, the application of a conditional plan element cond (c 1 :p 1 ): : :(c n :p n ) is defined as an application of the branch p j whose context condition c j matches with obs(s i ) (there should only be one such branch).

This concludes how actions and plans are represented in PTLplan. Next, we proceed to investigate how strategic knowledge can be represented and used.

4 Strategic knowledge

In order to eliminate unpromising plan prefixes and reduce the search space, PTLplan (and TLplan and ETLplan before it) utilizes strategic knowledge. This strategic knowledge is encoded as expressions (search control formulae) in an extension of first-order linear temporal logic (LTL) [Emerson, 1990] and is used to determine when a plan prefix should not be explored further. One example could be the condition "never pick up an object and then immediately drop it again". If this condition is violated, that is evaluates to false in some e-situation, the plan prefix leading there is not explored further and all its potential continuations are cut away from the search tree. A great advantage of this approach is that one can write search control formulae without any detailed knowledge about how the planner itself works; it is sufficient to have a good understanding about the problem domain.

LTL is based on a standard first-order language consisting of predicate symbols, constants and function symbols and the

Algorithm Progress(f,s)

Case:

1: f = Kf 1 : f + := 8 < : true if K  (1 ; L s2S ; p l (s)) where S ; = fs 2 sjs j= :f 1 g;; false otherwise 2: f = O(f 1 =v) : f + :=  true if hf 1 ;; vi 2 obs(s);; false otherwise 3: f = Gf 1 : f + :=  true if s j= f 1 for all s 2 G;; false otherwise 4: f = f 1 ^ f 2 : f + := Progress(f 1 ;; s)^ P rogress(f 2 ;; s) 5: f = :f 1 : f + := :Progress(f 1 ;; s) 6: f = f 1 : f + := f 1 7: f = f 1 Uf 2 : f + := Progress(f 2 ;; s)_ (P rogress(f 1 ;; s) ^ f ) 8: f =3f 1 : f + := Progress(f 1 ;; s) _ f 9: f = 2f 1 : f + := Progress(f 1 ;; s) ^ f 10: f = 8x[f 1 ] : f + := V c2U Progress(f 1 (x=c);; s) 11: f = 9x[f 1 ] : f + := W c2U Progress(f 1 (x=c);; s) Return f +

usual connectives and quantifiers. In addition, there are four temporal modalities: U (until), 2 (always), 3 (eventually), and (next). In LTL, these modalities are interpreted over a sequence of situations, starting from the current situation. For the purpose of PTLplan, we can interpret them over a sequence/branch of epistemic situations B = hs 1 ;; s 2 ;; : : :i and a current epistemic situation s i in that sequence. The expression  1 U 2 means that  2 holds in the current or some future e-situation, and in all e-situations inbetween  1 holds; 2 means that  holds in this and all subsequent e-situations; 3 means that  holds in this or some subsequent e-situation; and  means that  holds in the next e-situation s i+1 .

In addition to the temporal modal operators from LTL, PTLplan also uses a goal operator G, which is useful for referring to the goal in search control formulae. We let G' denote that it is among the agent's goals to achieve the fluent formula '. Semantically, this modality will be interpreted relative to a set of goal states G, i.e. the set of states that satisfy the goal. We also introduce two new modal operators: K' ("knows") means that the necessity/probability that the fluent formula ' is true in the current e-situation exceeds some prespecified threshold K, given the information the agent has; and Of=v denotes that f is observed to have the value v in the current e-situation. We restrict fluent formulae to appear only inside the K, G and (for fluent-value formulae) O operators.

We can now define the semantics of these modal operators relative to a branch B of epistemic situations, a current epistemic situation s i , a variable assignment V , and a set of goal states G, as follows.

•  (B;; s i ;; V;;G) j=  1 U 2 iff there exists a j  i such that (B;; s j ;; V;;G) j=  2 and for all k such that i  k < j, (B;; s k ;; V;;G) j=  1 .
•  (B;; s i ;; V;;G) j= 2 iff for all j  i, (B;; s j ;; V;;G) j= .

Algorithm PTLplan(s;; f;; g;; A;; )

1. If s j= g then return hsuccess;; p(s);; 0i.
2. Let f + := Progress(f;; s); if f + = false then return hfail;; 0;; p(s)i.
3. For the actions a i 2 Awhose preconditions are satisfied in all s 2 s do:
4. Let S + = Apply(a i ;; s).
5. For each s + j 2 S + , let hP 0 j ;; succ 0 j ;; fail 0 j i := PTLplan(s + j ;; f;; g;;A;; ).
6. If ( L j fail 0 j )  1; then let cont i = hfail;; 0;; p(s)i.
7. If jS + j = 1, let cont i = ha 1 ;P 0 1 ;; succ 0 1 ;; fail 0 1 i. Otherwise let cont i = hP i ;; succ i ;; fail i i where P i = a i ;(cond(c 0 1 :P 0 1 )...(c 0 n :P 0 n )), succ i = ( L j succ 0 j ), fail i = ( L j fail 0 j ) and each c 0 i = V ff=v j hf;; vi 2 obs(s + i )g.
8. Return the cont i = hP i ;; succ i ;; fail i i with the lowest fail i , provided fail i < (1 ; ), or otherwise return hfail;; 0;; p(s)i.

Figure 2: The PTLplan planning algorithm.

•  (B;; s i ;; V;;G) j= 3 iff there exists a j  i such that (B;; s j ;; V;;G) j= .
•  (B;; s i ;; V;;G) j=  iff (B;; s i+1 ;; V;;G) j= .
•  (B;; s i ;; V;;G) j= G' iff for all s 2 G, (s;; V ) j= '.
•  (B;; s i ;; V;;G) j= K' iff K  1 ; ( L s2S ; p l (s)) where S ; = fs 2 s i j(s;; V ) j= :'g.
•  (B;; s i ;; V;;G) j= Of=v iff hf;; vi 2 obs(s i ).

The interpretation of K' is motivated by the fact that in possibility theory, necessity is defined as Nec(') = 1;P os(:'), and in probability theory P (') = 1 ; P (:').

In order to efficiently evaluate control formulas, PTLplan incorporates a progression algorithm (similar to the ones of TLplan and ETLplan) that takes as input a formula f and an e-situation and returns a formula f + that is "one step ahead", i.e. corresponds to what remains to evaluate of f in subsequent e-situations. It is shown in figure 1. (The goal states G in case 3 are fixed for a given planning problem and need not be passed along.) Note that the algorithm assumes that all quantifiers range over a finite universe U.

Example 5 The following is a control formula stating that a robot should never pick an object up and then drop it immediately again, i.e. hold it only one moment.

5 The planning algorithm

PTLplan is a progressive planner, which means that it starts from an initial e-situation and then tries to sequentially apply actions until an e-situation where the goal is satisfied is reached. The algorithm is shown in figure 2. It takes as input an e-situation s, a search control formula f, a goal formula g (with a K), a set of actions A and a success threshold  (the failure threshold is 1 ; ). It returns a triple hplan;; succ;; faili containing a conditional plan, a degree (possibility/probability) of success, and a degree of failure. It is initially called with the given initial e-situation and a search control formula.

Step 1 checks if the goal is satisfied in s, if this is the case it returns the possibility/probability p(s) of s . Step 2 progresses the search control formula; if it evaluates to false, the plan prefix leading to this e-situation is considered unpromising and is not explored further. In step 3, we consider the different applicable actions. For each such action, we obtain a set of new e-situations (a). We then continue to plan from each new e-situation separately (b). For those subplans thus obtained, if the combined possibility/probability of failure is above the failure threshold, we simply return a fail plan (c). If there was a single new e-situation, we return a simple sequence starting with the chosen action (d). Otherwise, we add to the chosen action a conditional plan segment where branches are constructed as follows. The conditions are derived from the different observations of the different esituations, and the sub-plans are those obtained in (b). The success and failure degrees of this new plan are computed by combining those of the individual sub-plans. In step 4, finally, we return the best of those plans (i.e. the one with the least failure degree) found in step 3, or a fail plan if the degree of failure is too high.

Example 6 To give a feel for the operation of PTLplan, we go through the tiger scenario. The actions are defined as in example 1, and the initial e-situation is as in example 2. There is one search control formula: 2

Finally, the goal is:

This goal should be achieved with a probability of at least  = 0:8, giving a failure threshold of 0:2.

1. From the initial e-situation, the applicable actions are open(ld), open(rd) and listen().
2. We first apply open(ld), resulting in the e-situations described in the first half of example 3.

(a) Continuing planning from the first of these esituations, the condition 2(K(:dead)) after progression evaluates to false, so this branch yields hfail;; 0;; 0:5i (plan, success degree,failure degree); see step 2 in the algorithm.

(b) In the second one, the goal is achieved, yielding hsuccess;; 0:5;; 0i.

Thus, the combined probability of failure is 0  0:5 = 0:5, which is above the failure threshold (step 3.c).

1. Applying open(rd) gives a similar outcome.
2. Applying listen() to the initial e-situation yields the
3. two e-situations from the second half of example 3. (a) Continuing from the first new e-situation, we eventually find that choosing open(rd) leads

2 The same effect could be achieved by including :dead in the preconditions of the actions, but we encode it as a search control formula to have the opportunity to see one in action.

to success with a degree of 0.425: hopen(rd); cond (rew=T : success)(dead=T : fail);; 0:425;; 0:075i

(b) Continuing from the second one, we find that choosing open(ld) leads to success with a probability of 0.425: hopen(ld);cond(rew=T:success) (dead=T : fail);; 0:425;; 0:075i.

Combining the branches from (a) and (b) and appending them to listen(), finally, yields the plan shown in example 4, with 0.85 and 0.15 as probabilities of success/failure.

6 Implementation and experiments

PTLplan has been implemented in Allegro CommonLisp, and uses a breath first search method involving detection of previously visited situations. The performance of PTLplan has been tested on some scenarios encountered in the literature. All tests were performed on a 300 MHz Pentium II. Table 3 presents the results of the experiments. Note that the use of search control formulae has a considerable impact, in particular in the three last scenarios. We also include some results documented for some other planners [Majercik and Littman, 1999; Onder and Pollack, 1999; Gu´er´e and Alami, 1999] in order to give some rough indication about the relative merits of PTLplan. 3

The tiger scenario was solved for success probabilities  = 0:5;; 0:85;; 0:939. Only the marginally helpful control formula in example 6 was used. The coffee robot scenario [Boutilier and Poole, 1996; Onder and Pollack, 1999] involves a robot that is to go to a cafe in order to buy coffee with cream and sugar, and then bring the coffee back to the office. If it is raining (50% chance) the robot has to bring an umbrella along, otherwise not. A conjunction of 6 search control formulae were used in this scenario. The solution plan had two branches; the longest one had 8 steps. In the asking coffee robot scenario [Majercik and Littman, 1999], the robot does not have to bother about cream and sugar, but has to ask the user whether he wants coffee (50% chance). The solution had 4 branches. The cold-room scenario is a more complex, possibilistic scenario from [Gu´er´e and Alami, 1999] involving a poorly illuminated table with two test tubes. A robot should move the red tube to a second table in a cold-room. A conjunction of 8 search control formulae were used in this scenario, and one of them is shown in example 5. The solution plan involved going to a third well-illuminated table to ensure that the correct test tube was picked up. It had two branches; the longest one had 14 steps.

3 Unfortunately, the lack of agreed-upon, standard scenarios for conditional probabilistic/possibilistic planning makes systematic comparisons difficult. Also note that differences in hardware, small variations in how the scenarios were encoded etc, could account for some of the differences.

7 Conclusions and future work

In this paper, we have presented work on the planner PTLplan. It is a progressive planner which utilizes strategic knowledge to reduce its search space. We have described PTLplan's fairly rich representation: actions with contextdependent and uncertain effects and observations, and plans with conditional branches. The semantics of this representation is based on associating different possible situations with degrees of possibility or probability. We have also described the planning algorithm and how we utilize a temporal logic to encode search control knowledge that can be used to prune unpromising branches in the search tree. PTLplan is based on TLplan [Bacchus and Kabanza, 2000] and ETLplan [Karlsson, 2001]. The novel contribution of PTLplan is the introduction of uncertainty into the context of progressive planning with strategic knowledge.

In this paper, we have also given some brief but quite promising performance data on PTLplan, indicating that it compares favorably to other probabilistic/possibilistic conditional planners. Yet, more remains to be done, both in order to improve the performance of PTLplan, and to evalute it more systematically, in particular on larger scenarios. Finally, we are now working on integrating PTLplan with a robotic system capable of action and perception [Coradeschi and Saffiotti, 2001].

Acknowledgements

This work was funded by the Swedish KK foundation. Many thanks to Silvia Coradeschi and Alessandro Saffiotti for helpful suggestions, and to Stephen Majercik for answering questions about ZANDER.