6 Planning with Certainty

6.5 Partial-Order Planning

Dimensions: flat, features, indefinite horizon, fully observable, deterministic, goal directed, non-learning, single agent, offline, perfect rationality

The forward and regression planners enforce a total ordering on actions at all stages of the planning process. The CSP planner commits to the particular time that the action will be carried out. This means that those planners have to commit to an ordering of actions when adding them to a partial plan, even if there is no particular reason to put one action before another.

A partial-order planner maintains a partial ordering between actions and only commits to an ordering between actions when forced. This is sometimes also called a non-linear planner, which is a misnomer because such planners often produce a linear plan.

Because the same action may be used a number of times in the same plan, for example, the robot may need to move clockwise a number of times, the partial ordering will be between action instances, where an action instance is just a pair of an action and an integer, which we will write as act#i. By the preconditions and effects of the action instance, we mean the precondition and the effects of the action.

A partial ordering is a binary relation that is transitive and asymmetric. A partial-order plan is a set of action instances together with a partial ordering between them, representing a “before” relation on action instances. Write act0<act1 if action instance act0 is before action instance act1 in the partial order. This means that the action of act0 must occur before the action of act1. The aim of the planner is to produce a partial ordering of the action instances so that any total ordering consistent with the partial ordering will solve the goal from the initial state.

There are two special action instances, start, that achieves the relations that are true in the initial state, and finish, whose precondition is the goal to be solved. Every other action instance is after start and before finish in the partial ordering. The use of these as action instances means that the algorithm does not require special cases for the initial situation and for the goals. When the preconditions of finish are achieved, the goal is solved.

Any action instance, other than start or finish, will be in a partial-order plan to achieve a precondition of an action instance in the plan. Each precondition P of an action instance act1 in the plan is either true in the initial state, and so achieved by start, or there will be an action instance act0 in the plan that achieves P. The action instance act0 that achieves P must be before act1; that is, act0<act1. To be correct, the algorithm must also ensure that nothing makes P false in between act0 and act1.

A causal link is a triple act0,P,act1, where act0 and act1 are action instances and P is a Var=val assignment that is in the precondition of act1, and in the effect of act0. This means that act0 makes P hold for act1. With this causal link, any other action instance that makes P false must either be before act0 or after act1.

Informally, a partial-order planner works as follows. Begin with the action instances start and finish and the partial order start<finish. The planner maintains an agenda that is a set of P,A pairs, where A is an action instance in the plan and P is a variable-value assignment that is a precondition of A that remains to be achieved. Initially, the agenda contains pairs G,finish, where G is an assignment that must be true in the goal state.

At each stage in the planning process, a pair G,act1 is chosen from the agenda, where P is in the precondition for action instance act1. Then an action instance, act0, is chosen to achieve P. That action instance is either already in the plan – it could be the start action, for example – or it is a new action instance that is added to the plan. Action instance act0 must happen before act1 in the partial order. The planner adds a causal link that records that act0 achieves P for action act1. Any action in the plan that makes P false must happen either before act0 or after act1. If act0 is a new action, its preconditions are added to the agenda, and the process continues until the agenda is empty.

The algorithm Partial_order_planner is given in Figure 6.6. This is a non-deterministic procedure. The “choose” and the “either …or …” form choices that must be searched over. There are two choices that require search:

  • which action is chosen to achieve P and

  • whether an action instance that deletes P happens before act0 or after act1.

1:non-deterministic procedure Partial_order_planner(As,Gs)
2:      Inputs
3:            As: possible actions
4:            Gs: goal, aset of variable-value assignments to achieve       
5:      Output
6:            linear plan to achieve Gs
7:      Local
8:            Agenda: set of P,A pairs where P is an atom and A an action instance
9:            Actions: set of action instances in the current plan
10:            Constraints: set of temporal constraints on action instances
11:            CausalLinks: set of act0,P,act1 triples       
12:      Agenda:={G,finish:GGs}
13:      Actions:={start,finish}
14:      Constraints:={start<finish}
15:      CausalLinks:={}
16:      repeat
17:            select and remove G,act1#i from Agenda
18:            either
19:                 choose act0#jActions such that act0 achieves G
20:            Or
21:                 choose act0As such that act0 achieves G
22:                 select unique integer j
23:                 Actions:=Actions{act0#j}
24:                 Constraints:=add_const(start<act0#j,Constraints)
25:                 for each CLCausalLinks do
26:                       Constraints:=protect(CL,act0#j,Constraints)                  
27:                 Agenda:=Agenda{P,act0#j:P is a precondition of act0}             
28:            Constraints:=add_const(act0#j<act1#i,Constraints)
29:            new_cl:=acto#j,G,act1#i
30:            CausalLinks:=CausalLinks{new_cl}
31:            for each AActions do
32:                 Constraints:=protect(new_cl,A,Constraints)             
33:      until Agenda={}
34:      return total ordering of Actions consistent with Constraints
Figure 6.6: Partial-order planner

The function add_const(A0<A1,Constraints) returns the constraints formed by adding the constraint A0<A1 to Constraints, and it fails if A0<A1 is incompatible with Constraints. There are many ways this function can be implemented. See Exercise 12.

The function protect(A0,G,A1,A) checks whether AA0, AA1 and the effect of A is inconsistent with G. If so, either A<A0 is added to the set of constraints or A1<A is added to the set of constraints. This is a non-deterministic choice that is searched over.

Example 6.17.

Consider the goal of Sam not wanting coffee and no mail waiting (i.e., ¬swc¬mw), where in the initial state Rob is in the lab, Sam wants coffee, Rob does not have coffee, there is mail waiting and Rob does not have mail, i.e., RLoc=lab, swc, ¬rhc, mw, ¬rhm.

We will write instances of action Act as Act#n where n is a unique integer.

Initially the agenda is

{¬swc,finish,¬mw,finish}.

Suppose ¬swc,finish is chosen and removed from the agenda. One action can achieve ¬swc, namely deliver coffee, dc, with preconditions off and rhc. So it inserts an instance, say dc#6, into the plan. After the first time through the repeat loop, Agenda contains

{off,dc#6,rhc,dc#6,¬mw,finish}.

At this stage, the value of Constraints is {start<finish,start<dc#6,dc#6<finish}. There is one causal link, dc#6,¬swc,finish. This causal link means that no action that undoes ¬swc is allowed to happen between dc#6 and finish.

Suppose ¬mw,finish is chosen from the agenda. One action can achieve this, pum, with precondition {mw,RLoc=mr}. The algorithm constructs a new action instance, say pum#7. The causal link pum#7,¬mw,finish is added to the set of causal links; mw,pum#7 and mr,pum#7 are added to the agenda.

Suppose mw,pum#7 is chosen from the agenda. The action start achieves mw, because mw is true initially. The causal link start,mw,pum#7 is added to the set of causal links. Nothing is added to the agenda.

At this stage, there is no ordering imposed between dc#6 and pum#7.

Suppose off,dc#6 is removed from the agenda. There are two actions that can achieve off: mc_cs with preconditions cs, and mcc_lab with preconditions lab. The algorithm searches over these choices. Suppose it chooses the action instance mc_cs#9. The causal link mc_cs#9,off,dc#6 is added.

The first violation of a causal link occurs when a move action is used to achieve mr,pum#7. This action violates the causal link mc_cs#9,off,dc#6, and so must happen after dc#6 (the robot goes to the mail room after delivering coffee) or before mc_cs#9.

Eventually, it finds a plan of action instances, such as:

start;mc_lab#15;pum#7;mc_mr#40;puc#11;mc_cs#9;dc#6;finish

This is the only total ordering consistent with the partial ordering.

A partial order planner works particularly well when no ordering of actions can achieve a goal, as it does not need to search over all permutations of the actions. It also works well when many orderings can solve the goal, in which case it can find a flexible plan for the robot.