2.5.1 Searching in a Space of Partial Plans

One alternative to searching directly in $X$ is to construct partial plans without reference to particular states. By using the operator representation, partial plans can be incrementally constructed. The idea is to iteratively achieve required subgoals in a partial plan while ensuring that no conflicts arise that could destroy the solution developed so far.

A partial plan $\sigma$ is defined as

1. A set $O_\sigma$ of operators that need to be applied. If the operators contain variables, these may be filled in by specific values or left as variables. The same operator may appear multiple times in $O_\sigma$, possibly with different values for the variables.
2. A partial ordering relation $\prec_\sigma$ on $O_\sigma$, which indicates for some pairs $o_1,o_2 \in O_\sigma$ that one must appear before other: $o_1 \prec_\sigma o_2$.
3. A set $B_\sigma$ of binding constraints, in which each indicates that some variables across operators must take on the same value.
4. A set $C_\sigma$ of causal links, in which each is of the form $(o_1,l,o_2)$ and indicates that $o_1$ achieves the literal $l$ for the purpose of satisfying a precondition of $o_2$.

Example 2..7 (A Partial Plan)   Each partial plan encodes a set of possible plans. Recall the model from Example 2.6. Suppose

$$O_\sigma = \{ RemoveCap, Insert(Battery1)\} .$$ (2.27)

A sensible ordering constraint is that

$$RemoveCap \prec_\sigma Insert(Battery1) .$$ (2.28)

A causal link,

$$(RemoveCap,\neg On(Cap,Flashlight),Insert(Battery1)),$$ (2.29)

indicates that the $RemoveCap$ operator achieves the literal $\neg On(Cap,Flashlight)$, which is a precondition of $Insert(Battery1)$. There are no binding constraints for this example. The partial plan implicitly represents the set of all plans for which $RemoveCap$ appears before $Insert(Battery1)$, under the constraint that the causal link is not violated. $\blacksquare$

Several algorithms have been developed to search in the space of partial plans. To obtain some intuition about the partial-plan approach, a planning algorithm is described in Figure 2.19. A vertex in the partial-plan search graph is a partial plan, and an edge is constructed by extending one partial plan to obtain another partial plan that is closer to completion. Although the general template is simple, the algorithm performance depends critically on the choice of initial plan and the particular flaw that is resolved in each iteration. One straightforward generalization is to develop multiple partial plans and decide which one to refine in each iteration.

Figure 2.19: Planning in the plan space is achieved by iteratively finding a flaw in the plan and fixing it.

In early works, methods based on partial plans seemed to offer substantial benefits; however, they are currently considered to be not ``competitive enough'' in comparison to methods that search the state space [382]. One problem is that it becomes more difficult to develop application-specific heuristics without explicit references to states. Also, the vertices in the partial-plan search graph are costly to maintain and manipulate in comparison to ordinary states.