

![0_image_0.png](0_image_0.png)

Graphplan rebuilds the sliding window, shown in Figure 11, oflayers between FP and n - 1 as layers FP + 1 through to n. STAN simply promotes the leaves of the tree, generated at layer FP in GT n-FP G n-1, into layer FP + 1.

It is straightforward to show that the wave front maintains soundness. The search that Graphplan performs generates a goal tree of goal sets, as defined in Definition 12. In the example in Figure 10, the tree is rooted at G, with G1, G2 and G3 its children and G4 and G5 the children of G1. It can be seen from the picture that the tree structure generated by Graphplan, in which each successive layer would be embedded in a separate layer of the explicitly constructed graph, appears in a spiral of related goal sets between the fix point and buffer layers. All of the candidate goal sets lie in this same search tree and therefore no additional goal sets are generated. Graphplan constructs the final plan by reading off the sequence of action choices at each layer in the final graph. In STAN, the plan is obtained by reading off the initial fragment of the plan in the same way, from the layers preceding the fix point. The rest of the plan is extracted from the spiral. This extraction process yields the same path of action choices from the top level goal set to the candidate goal set as would be recorded explicitly in the Graphplan plan graph.

The only question remaining to be considered is whether the wave front has the same termination properties as Graphplan. It can be seen that it does since, if no new unsolvable goal sets are generated at the fix point, the queue will become empty and the planner terminates. This corresponds exactly to the termination conditions of Graphplan.

A subtlety concerns the interaction between the wave front and the subset memoization discussed in Section 2.2. In principle, subset memoization could cause the loss of all three of the desired properties of the graph. The way that STAN generates candidate goal sets is by