Suppose that the planning graph has been constructed up to . 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 ; see also ). If the planning graph has not stabilized, then it can be extended further by adding and . 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 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
At each level, the search for a plan could be quite costly. The idea is to start from and perform a backward and/or search. To even begin the search, the goal literals must be a subset of , and no pairs are allowed to be mutex; otherwise, immediate failure is declared. From each literal , an ``or'' part of the search tries possible operators that produce 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 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  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).
Steven M LaValle 2012-04-20