Plan extraction

Suppose that the planning graph has been constructed up to $L_i$. At this point, the planning graph can be searched for a solution. If no solution is found and the planning graph has stabilized, then no solution exists to the problem in general (this was shown in [117]; see also [382]). If the planning graph has not stabilized, then it can be extended further by adding $O_i$ and $L_{i+1}$. The extended graph can then be searched for a solution plan. A planning algorithm derived from the planning graph interleaves the graph extensions and the searches for solutions. Either a solution is reported at some point or the algorithm correctly reports that no solution exists after the planning graph stabilizes. The resulting algorithm is complete. One of the key observations in establishing completeness is that the literal and operator layers each increase monotonically as $i$ increases. Furthermore, the sets of pairs that are mutex decrease monotonically, until all possible conflicts are resolved.

Rather than obtaining a fully specified plan, the planning graph yields a layered plan, which is a special form of partial plan. All of the necessary operators are included, and the layered plan is specified as

$$(A_1,A_2,\ldots,A_k) ,$$ (2.31)

in which each $A_i$ is a set of operators. Within any $A_i$, the operators are nonmutex and may be applied in any order without altering the state obtained by the layered plan. The only constraint is that for each $i$ from $1$ to $k$, every operator in $A_i$ must be applied before any operators in $A_{i+1}$ can be applied. For the flashlight example, a layered plan that would be constructed from the planning graph in Figure 2.20 is

$$(\{RemoveCap\},\{Insert(Battery1),Insert(Battery2)\},\{PlaceCap\}) .$$ (2.32)

To obtain a fully specified plan, the layered plan needs to be linearized by specifying a linear ordering for the operators that is consistent with the layer constraints. For (2.32), this results in (2.24). The actual plan execution usually involves more stages than the number in the planning graph. For complicated planning problems, this difference is expected to be huge. With a small number of stages, the planning graph can consider very long plans because it can apply several nonmutex operators in a single layer.

At each level, the search for a plan could be quite costly. The idea is to start from $L_i$ and perform a backward and/or search. To even begin the search, the goal literals $G$ must be a subset of $L_i$, and no pairs are allowed to be mutex; otherwise, immediate failure is declared. From each literal $l \in G$, an ``or'' part of the search tries possible operators that produce $l$ as an effect. The ``and'' part of the search must achieve all literals in the precondition of an operator chosen at the previous ``or'' level. Each of these preconditions must be achieved, which leads to another ``or'' level in the search. The idea is applied recursively until the initial set $L_1$ of literals is obtained. During the and/or search, the computed mutex relations provide information that immediately eliminates some branches. Frequently, triples and higher order tuples are checked for being mutex together, even though they are not pairwise mutex. A hash table is constructed to efficiently retrieve this information as it is considered multiple times in the search. Although the plan extraction is quite costly, superior performance was shown in [117] on several important benchmarks. In the worst case, the search could require exponential time (otherwise, a polynomial-time algorithm would have been found to an NP-hard problem).