A Possibilistic Planner that Deals with Non-Determinism and Contingency

1 Introduction

An autonomous robot system operating in an environ­ ment in which there is uncertainty and changes, needs to combine reasoning and reaction. To correctly plan in an uncertain and dynamic environment, the planner needs an accurate description of the world, of the actions which could be planned and a goal success definition. There is also a need to model non-determinism as well as contin­ gent events.

One can classify actions into four types: determinis­ tic actions (there is only one possible outcome), condi­ tional actions (outcomes are context dependent) , non­ deterministic actions (several possible outcomes) and perception actions (one outcome out of n). In addition a perception action improves knowledge.

Another key feature is the ability of the planning al­ gorithm to concentrate on the exploration of the most "probable" courses of action and to evaluate the robust­ ness and the goal achieving ability of a given plan.

This paper presents a planner which partially fulfills the requirements discussed above. To model the environ­ ment uncertainty we use the possibility theory [Dubois and Prade, 1988] which allows to represent complete ignorance as well as qualitative inaccuracy. A goal is described as a conjunction of possibilistic facts which can qualify the goal achievement necessity. It is impor­ tant to note that with uncertain information, actions with conditional effects can be used as a class of ac­ tions with non-deterministic outcomes. Consequently non-determinism can result from uncertainty (condi­ tional actions) as well as from insufficient modeling (non­ deterministic actions) . Our planner uses explicitly these two kinds of sources of non-determinism in planning as well as perception actions . which allow to build condi­ tional plans.

Our planner can anticipate and oppose contingent events by avoiding situations where they can occur or by preparing an adapted reaction. However , this feature is limited to situations which are the result of previous robot action.

In the next sections we describe our representation of the world, of the robot actions and of contingent events. Then we present an algorithm inspired from Graphplan search[Blum and Furst, 1997] as well as some illustrative outputs produced by our planner. Finally, we give an overview and a short conclusion.

2 An uncertain environment

It is certainly useful to distinguish between several types of uncertainties: the complete ignorance of a fact (e.g. the robot does not know where the red test tube is) , the qualitative inaccuracy of a fact (e.g. the robot only knows that the red test tube is probably on Tablet ) and the quantitative inaccuracy of a fact (e.g. the robot knows that the probability that the red test is on Tablet is 0.9). Some planners like CGP [Smith and Weld, 1998] or Cassandra [Pryor and Collins, 1996] use a set of dis­ tinct possible worlds which corresponds to our complete ignorance idea. The probabilistic approach, used espe­ cially in BURIDAN [Kushmeric et al., 1995], is partic­ ularly interesting for describing the uncertainty associ­ ated to state transitions . However, probabilities do not allow to represent complete ignorance; besides , there are numerous situations where it is not possible to give to the robot planner probabilities based on statistical mea­ sures, but only qualitative information provided by the operator or deduced from previous missions. This is the reason why we use the possibility theory.

2.1 Possibility background

The possibility theory [Zadeh, 1978; Dubois and Prade, 1988] offers an uncertainty modeling framework where two values are associated to every fact A:

• II(A): the "possibility" for the fact A to be true,
• N(A): the "necessity" for the fact A to be true.

The duality between necessity and possibility is expressed by the relation N(A) = 1 - IT(·A) . For example if we do not know if the door is open or not , we can write: IT(Open(Door)) 1 and N(Open(Door)) = 0 (the door may be open but not necessarily). If the red test tube usually is on Table 1 , we can write: IT(On(RedTestTube , Table!)) = 1 and N(On(RedTestTube, Table!))= 0.9. Note that this is a qualitative measure; only the order between the different possibility and necessity values is relevant.

2.2 The world representation

We define a state as a conjunction of possibilistic facts . The Closed-World Assumption allows, when a fact A is false, to delete it from the state description. Conse­ quently we extend this assumption, in our context, and we only represent in the state the facts that are known in necessity terms ; in other words we only insert facts which have a positive necessity. Table 1 shows an example of an initial state. Note that the possibility is missing; in­ deed, with the duality between possibility and necessity we could replace II(A) by N(·A) . So if II(A) = 1 then N ( ·A) = 0 and it will not be represented in the state description. In this example, we see that the light on top of Table 1 often works, whereas the light on top Tabl e2 almost usually works .

A goal for our planner is represented by a conjunc­ tion of facts with a strictly positive necessity (to avoid disjunctions).

3 Modeling robot actions

We model the robot actions by possibilistic rules that change the state description. These rules are based on an extension of STRIPS [Fikes and Nilsson, 1971] Pre­ conditions , Add-lists and Delete-lists. The computation of the necessities associated to action effects is based on the following propagation rule (fig. 1):

where B; is the ith effect , N (B; I A1 1\ .. . I\An))) is the ne­ cessity of having B; given the precondition A 1 1\ ... 1\ An, Nb( B; ) is the necessity of the fact B; before applying the action and N(B;) is its value after applying the action .

Deterministic actions 3.1

A deterministic action changes a state into another in foreseeable way. For example the Take WithLight action may be represented by:

If we apply this action in the initial state described in Table 1, we obtain Holding(RedTestTube) with necessity N ~ 0.7. Note that because there is uncertainty, the action may be executed in situations where its precon­ ditions are not satisfied. We assume that in a such case, it will have no effect . However, if a more sophisticated model is necessary, one can use conditional actions.

3.2 Non-deterministic actions

Non-deterministic actions may lead to several possible outcomes. An outcome is represented by a conjunction offacts (with their necessities) and a possibility-necessity measure of occurrence of that outcome (fig. 2); all possi­ ble outcomes must appear (to have N(all outcomes)=!)

To keep consistency, the different worlds w; that result from the application of a non-deterministic action must verify:

For example, when the Take WithoutLight action is ap­ plied , we are sure to hold a test tube , but we do not know if it is Red or Green:

TakeWithoutLight (X:Table)

Pre: At Robot X, HandEmpty Eff: (w1 ,IT = 1,N=0): (Holding(RedTestTube),0.7), ( ·HandEmpty,O. 7) ... (w2,II = l,N=O) : (Holding(GreenTestTube),0.7), ( ·HandEmpty,O. 7) .. .

3.3 Conditional actions

For conditional actions, the effects are context dependent (fig. 3). The conditions must be exhaustive and mutually exclusive. Note that we allow action definitions which combine different types of effects (deterministic, condi­ tional , . . . ). The Take action combines conditional and non-deterministic effects:

In classical logic an action with conditional effects is deterministic. Indeed when we plan this action we know the current state and we can decide which conditional effects will apply. With such a model , one can always change an action which has n conditional effects , each with m conjuncts, in 2nm actions 1

However, in our state model the different facts are possibilistic, so if the fact Light(Tablel) is not completely certain -.Light(Tablel) is possible (if IT(Light(Tablel)) = 1/\ N(Light(Tablel)) = 0.7 then fi(-,Light(Tabl el)) = 0.3 1\ N(..,Light(Tablel)) = 0) . We are in one of two possible worlds; the Take action, because of its conditional effects, is applicable in both worlds with different effects . This is what we call non­ determinism due to uncertainty.

1 For more details about conditional effects associated to Graphplan search see [Koehler et al., 1997; Anderson et al., 1998].

3.4 Perception actions

Perception actions allow to improve the robot knowledge about a given set offacts. It will allow the robot to know on which branch of the course of actions it is (fig. 4) . This will entail a higher necessity associated to the facts that have been observed. In the current implementation, we use a simple hypothesis: the perception is assumed perfect , and the necessity associated to the outcome is 1. One possible improvement can be the use of conditional effects (C-BURIDAN [Draper et al. , 1994] models that an observation can fail).

For example the perception action which determines if the robot has taken the red or the green test tube, can be represented by:

4 An algorithm based on Graphplan

Graphplan is a fast planner developed by [Blum and Furst , 1997] which plans with STRIPS operators and uses a constraint propagation method. It performs in two steps: first, it builds a constraint graph expansion; and then it searches for the plan with a constraint reso­ lution extraction.

4.1 Possibilistic treatment

To compute the necessity of a fact in a given state we apply the propagation rule defined in section 3. The use and definition of mutex is the same as Graphplan except for "interference" : two actions , A1 and A2 are mutually exclusive if the A1 effects contain the fact m, A 2 preconditions contain -.m and min(IT(m) , IT(-.m)) > 1- N(Goal) . One advantage of Graphplan is to keep on a level only one specimen of a fact . Consequently if we want to keep this advantage, we must use at each level the most "pessimistic" path (lowest necessity) as for proposition mutex: if the fact A has the necessity 0.9 with a first path and 0.8 with a second one, we associate 0.8 to A (see for example AtRobotTable1 in figure 5) . The real fact necessity will be reevaluated during the Graphplan backward phase. With a Graphplan algo­ rithm we cannot optimize the plan necessity (Graphplan only optimizes the number of levels) , but the necessity that we associate to the arcs (induced by the action mod­ els) can be used as a heuristic during backtrack.

4.2 Non-deterministic treatment

During the graph expansion, the planner applies actions with n non-deterministic effects as n deterministic ac­ tions (but we associate a label with necessity and possi­ bility to each branch as shown in figure 5). The solution

extraction is more complex; if the plan contains a non­ deterministic branch then either the branch necessity is better than the goal necessity (and the plan is valid), or the branch necessity is lower . In this case, the plan­ ner must verify that the plan is also valid for the other branches.

For example on figure 6, the planner applies a non­ deterministic action Take which "creates" two possible worlds w 11 and w21 . At this point, the robot will not be able to distinguish in which world it is . The next actions should be applicable both in w11 and w21 (e.g. M ove(Table1 , Table2)) until a perception action allows to distinguish between the two "branches".

4.3 Perception treatment

The main difference between non-deterministic and per­ ception action is that the robot will know after percep­ tion on which "branch" it is . The planner can then build a conditional plan. For example, in figure 7, the planner inserts a perception action Wich0ne?(Table2) to dis­ tinguish if the robot is holding a red or a green test tube. Note that WichOne?(Table2) must be applicable in w12 and wn- After the WichOne?(Table2) action, the two plan "branches" are independent and involve differ­ ent actions. This branches will be explored sequentially. This exploration is not necessary exhaustive. The plan­ ner will stop when it finds a plan that satisfies the goal necessity.

This corresponds to two plan synthesis starting from w13 and w23 · Note that , the planner can re-use, in the second branch exploration, the graph expansion built during the first one. However , it will have to extend it .

4.4 A first step towards dealing with contingent events

A key requirement for robot planning is to be able to reason about contingencies.We have introduced in our planner a capability that allows to deal with a subclass of external events.

Indeed, we distinguish between "actions" and "events"; while actions are opera tots over which the robot has full control, events are triggered whenever there is a situation that satisfies their preconditions. This model of the environment dynamics is based on extension of the NODEP representation of contingent events [Perret and Alami , 1995] . Similarly to action types, we have defined events with possibilistic, non­ deterministic or conditional effects.

Obviously, an elaborated reasoning on external events imposes temporal reasoning capabilities which are not included in our planner . However, we have chosen to exploit the number of plan steps as an estimation of du­ rations.

We distinguish two types of events:

• "immediate events" i.e events which apply immedi­ ately after the situation which verifies their precon­ ditions (one level in Graphplan search) ,
• events with delay: an event with a delay of n time units will occur if its triggering situation lasts during n levels.

For example, our goal is to cool the red test tube. At the end of the plan, the red test tube must be at Table3 in the cold-room. But if the door stays open, will the cold-room continue to cool? After a moment the test tube which is in the cold-room will be damaged . This is modeled by an undesirable fact called Fail ,

Such an event can be modeled by:

High Temperature

Pre: Opened(Door)

Eff: After(10,(Fail,Il=l,N=0.7))

After(JO,{Fail,II=l,N=O. 7)) means that after 10 time units the effect Fail (with necessity N=0 .7) will occur.

A "reasonable" robot should avoid such situations. A plan must be "safe" . While applying the plan to the initial state of the world, given its foreseeable evolu­ tion modeled by external events, no situation shall arise where the "Fail" fact appears.

We have extended our planning algorithm in order to fulfill such a requirement. During the graph expansion phase, the planner fires all events whose preconditions are satisfied. And, at each backtrack state the planner tests if in this partial state an event has possibly caused a failure. If so, the state is declared unsafe and the plan is rejected. This method ensures a safe plan synthesis even if an event appears after achieving the goal.

5 Results

In this section, we present our planner capabilities through a realistic example and sample problems. The current version is implemented in C++, and it uses an algorithm based in Graphplan.

As shown in figure 8, a robot stands beside Tablet in a room which contains two tables (Tablet and Table2 ) . On each table a lamp is fixed : the first lamp often lights whereas the second one usually lights. At the initial state, a red test tube and a green one are on Tablet. The goal is to cool the red test tube. A closed door separates the room from a cold-room in which there is a third table (Table3). In order to cool a test tube, the robot must put it on Table3. The robot may move from a location to another, take a test tube, see what it holds, open and close the door and put a test tube on a table. Table 1 shows the initial state.

First, we require a plan which achieves the goal with N ~ 0.7: (IT(On(RedTestTube , Table3)) = 1 1\N(On(RedTestTube, Table3)) ~ 0.7). The planner finds a solution with 6 actions in 95 msec:

Take(RedTestTube,Table!) Move(Table 1 , RoomDoor)

Open(Door) Move(RoomDoor, ColdRoomDoor) Move( ColdRoomDoor ,Table3 ) Put(RedTestTube ,Table3)

An advantage of our planner is its capability of find­ ing a better (but more complex) plan upon request; for example if its requested to find a plan that satisfies the same goal with higher necessity (N ~ 0.9) , the planner produces:

In this case, the planner has been obliged to use non­ deterministic action as well as perception action to know which test tube it holds. Note that, the light of Tablet does not allow the robot to see the tube that it holds, and thus the robot must go to Table 2 so as to distinguish its color. In addition, we observe that the first three actions define a conformant plan [Smith and Weld, 1998].

In the third example, we add two external events: if the cold-room door stays open too long (10 lev­ els) , the contents of the cold-room will be damaged; if the robot stays too long in the cold-room with the door closed it will be damaged. The planner finds a safe conditional plan (in 11780 msec) that satisfies (N(On(RedTestTube , Table3) 1\ -,damage)~ 0.9):

Take(Table!) Move(Table 1 ,Table2 ) Which0ne?(Table 2 )

• if Robot holds RedTestTube then Move(Table,,RoomDoor) Open(Door) Put( RedTestTube,Table3) Move(Table3 ,C oldRoomD oor)

Move(RoomDoor,ColdRoomDoor) Move(ColdRoomDoor ,Table3 ) Move(ColdRoomDoor, RoomDoor) Close(Door) if Robot holds GreenTestTube then Put( GreenTestTube,Table 2 ) Move(Table 2 ,Table1 ) Take(RedTestTube,Table 1 ) Move(Table 1 ,RoomDoor) Open(Door) Move(RoomDoor, ColdRoomDoor) Move( ColdRoomDoor ,Table 3 ) Put(RedTestTube ,Table3) Move(Table 3,ColdRoomDoor) Move(ColdRoomDoor , RoomDoor) Close(Door)

Note that the door is only closed at the end of the plan: close the door is not a reflex, it has been planned and inserted in the right place.

To upgrade our goal description, we will introduce, in further work, the notion of flexible goals as in POS­ PLAN [Da Costa Pereira et al., 1997] with qualitative utility [Dubois and Prade, 1995]. Indeed the robot se­ curity can be more important than mission achieving, that we will model by N(On(RedTestTube, Table3) ~ 0.9 1\ N (cold) = 1.

In table 2, we present set of a classical problems solved by our planner. Note that the CPU time is not com­ pletely significant, because the current version was im­ plemented only to validate our representation. "Bomb

in Toilet" is a problem proposed by [McDermott, 1987] (with sensing action), "Medical" by [Weld et al., 1998] and "Fetch another package" by [Pryor and Collins, 1996]).

6 Conclusion

In this paper, we have represented the uncertainty with the possibility theory; this allowed us to distinguish be­ tween two types of non-determinism: a non-determinism from insufficient modeling and a non-determinism from uncertainty. Besides, we have introduced perception ac­ tions as well as a model of the environment dynamics through "contingent events". Finally, we have presented an implemented experimental planner which is able to produce plans that are robust with respect to contin­ gent events, and whose goal-achieving ability is evalu­ ated a priori. The obtained plans can be conformant or conditional depending on the context and the user requirements.

6.1 Related work

WARPLAN [Warren, 1976] is the first planner which works on the non-deterministic action and conditional effects. We can distinguish two planner types: the robot environment is uncertain and safe. For example BURl­ DAN [Kushmeric et al., 1995] is a conditional probabilis­ tic planner. The plan produced by BURIDAN is a lin­ ear action sequence which achieves the goal whatever the initial world. POSPLAN [DaCosta Pereira et al., 1997] is possibilistic planner which searches an optimal plan with uncertainty non-determinism. UWL [Etzioni et al., 1992] introduces a formalism for conditional branches and observations with runtime variables. C-BURIDAN [Draper et al., 1994] proposes perception actions with probabilistic outcomes (noisy sensors). The complete ig­ norance modeling is the main problem of these planners because of the probabilistic representation. CASSAN­ DRA [Pryor and Collins, 1996] is a non-deterministic planner with conditional effects which can only model the complete ignorance. SGP [Weld et al., 1998] is the most recent non-deterministic planner with complete ig­ norance modeling. It is an extension of the conformant planner CGP[Smith and Weld, 1998] with sensing ac­ tions. SGP builds quickly plans using Graphplan al­ gorithm. We can note that SGP cannot produce new worlds during planning; moreover it can plan without sensing actions if the world is unobservable. The second type of planners deals with on dynamical environments as [Kabanza, 1992] works about reactive planning. The environment is uncertain and dynamic, but observable. It has defined the safe situation notion to have secure planning.

6.2 Future work

Our planner can build safe conditional plans involving non-deterministic actions and perception actions. How­ ever, it does not have the ability to concentrate on the exploration of the most "probable" courses of action and to anticipate the (safe) situations where it will have tore­ plan if it detects an error during execution. As we men­ tioned it previously, we will also integrate "flexible" goals which will allow to model the robot safety as more im­ portant than the mission. Another direction is to study more elaborate treatment of contingent events based on temporal reasoning.