

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

that the wave front is the most significant component in the performance of STAN in these experiments.

STAN is capable of efficiently solving larger Towers of Hanoi instances than are presented in the graph in Figure 12, which accounts for the additional point in Figure 13. STAN with the wave front found the 511-step plan for the 9-disc problem in less than 7 minutes using about 15Mb of memory. During the experiments reported here, Ipp was terminated after 15 minutes having reached layer 179 out of 255 layers in the 8-disc problem. We observe that on a machine with 1Gb of RAM, Ipp has solved this problem in 8 minutes.

The results for the Gripper domain demonstrate only a small advantage for STAN. The reason is because the search space grows exponentially in the size of the graph in the Gripper domain, so that the cost of searching dominates everything else. Although the search spaces for Towers of Hanoi instances also grow exponentially, they grow as 2 x whereas Gripper instances grow as xx (where x is the number of discs or balls respectively). Although the wave front helps under these conditions, the size of the search space dwarfs the benefits it offers. The Ferry domain is a less rapidly growing version of the gripper domain since only one vehicle can be carried on each journey, reducing the number of choices at each layer.

The difference in benefits obtained in the Towers of Hanoi domain relative to the Gripper and Ferry domains can be explained by consideration of the table in Figure 16.  The benefits of the wave front are proportional to the number of layers which exist implicitly  between the buffer and the layer from which the plan is ultimately found. In the Towers of Hanoi the number of implicit layers is exponential in the number of discs whereas the number of layers between the initial layer and the buffer is linear in the number of discs. Therefore the benefits offered by the use of the wave front are magnified exponentially as the problem