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 $act_{0} if action instance $act_{0}$ is before action instance $act_{1}$ in the partial order. This means that the action of $act_{0}$ must occur before the action of $act_{1}$. 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 $act_{1}$ in the plan is either true in the initial state, and so achieved by $start$, or there will be an action instance $act_{0}$ in the plan that achieves $P$. The action instance $act_{0}$ that achieves $P$ must be before $act_{1}$; that is, $act_{0}. To be correct, the algorithm must also ensure that nothing makes $P$ false in between $act_{0}$ and $act_{1}$.

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

Informally, a partial-order planner works as follows. Begin with the action instances $start$ and $finish$ and the partial order $start. The planner maintains an agenda that is a set of $\left$ 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 $\left$, where $G$ is an assignment that must be true in the goal state.

At each stage in the planning process, a pair $\left$ is chosen from the agenda, where $P$ is in the precondition for action instance $act_{1}$. Then an action instance, $act_{0}$, 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 $act_{0}$ must happen before $act_{1}$ in the partial order. The planner adds a causal link that records that $act_{0}$ achieves $P$ for action $act_{1}$. Any action in the plan that makes $P$ false must happen either before $act_{0}$ or after $act_{1}$. If $act_{0}$ 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 $act_{0}$ or after $act_{1}$.

The function $add\_const(A_{0} returns the constraints formed by adding the constraint $A_{0} to $Constraints$, and it fails if $A_{0} is incompatible with $Constraints$. There are many ways this function can be implemented. See Exercise 12.

The function $protect(\left,A)$ checks whether $A\neq A_{0}$, $A\neq A_{1}$ and the effect of $A$ is inconsistent with $G$. If so, either $A is added to the set of constraints or $A_{1} 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., $\neg{swc}\wedge\neg{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$, $\neg{rhc}$, $mw$, $\neg{rhm}$.

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

Initially the agenda is

 $\{\left<\neg{swc},finish\right>,\left<\neg{mw},finish\right>\}.$

Suppose $\left<\neg{swc},finish\right>$ is chosen and removed from the agenda. One action can achieve $\neg{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

 $\{\left,\left,\left<\neg{mw},finish\right>\}.$

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

Suppose $\left<\neg{mw},finish\right>$ 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 $\left$ is added to the set of causal links; $\left$ and $\left$ are added to the agenda.

Suppose $\left$ is chosen from the agenda. The action $start$ achieves $mw$, because $mw$ is true initially. The causal link $\left$ 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 $\left$ 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 $\left$ is added.

The first violation of a causal link occurs when a move action is used to achieve $\left$. This action violates the causal link $\left$, 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.