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 nonlinear 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\mathrm{\#}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 if action instance $ac{t}_0$ is before action instance $ac{t}_1$ in the partial order. This means that the action of $ac{t}_0$ must occur before the action of $ac{t}_1$. The aim of the planner is to produce a partial ordering of the action instances so that any total ordering that is 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 $ac{t}_1$ in the plan is either true in the initial state, and so achieved by $start$, or there will be an action instance $ac{t}_0$ in the plan that achieves $P$. The action instance $ac{t}_0$ that achieves $P$ must be before $ac{t}_1$; that is, . To be correct, the algorithm must also ensure that nothing makes $P$ false in between $ac{t}_0$ and $ac{t}_1$.

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

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

At each stage in the planning process, a pair is chosen from the agenda, where $P$ is in the precondition for action instance $ac{t}_1$. Then an action instance, $ac{t}_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 $ac{t}_0$ must happen before $ac{t}_1$ in the partial order. The planner adds a causal link that records that $ac{t}_0$ achieves $P$ for action $ac{t}_1$. Any action in the plan that makes $P$ false must happen either before $ac{t}_0$ or after $ac{t}_1$. If $ac{t}_0$ is a new action, its preconditions are added to the agenda, and the process continues until the agenda is empty.

The algorithm $Partial\mathrm{\_}order\mathrm{\_}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$

• •

  whether an action instance that deletes $P$ happens before $ac{t}_0$ or after $ac{t}_1$.

The function returns the constraints formed by adding the constraint to $Constraints$, and it fails if is incompatible with $Constraints$. There are many ways this function can be implemented. See Exercise 6.11.

The function checks whether $A\ne A_0$, $A\ne A_1$, and the effect of $A$ is inconsistent with $G$. If so, either is added to the set of constraints or is added to the set of constraints. This is a non-deterministic choice that is searched over.

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.