

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

ploiting the resource analysis techniques of Tim (Fox & Long, 1998), whilst a significant proportion of the advantage is obtained from the use of the wave front, as Figure 20 shows. Resource analysis allows a lower bound to be determined on the number of layers that must be built in a plan graph before it is worth searching for a plan. In the Complete-Graph Travelling Salesman domain this is very powerful, as the calculated bound is n, the number of cities in the instance, which is precisely the correct plan length. In this domain, if no search is done until n layers are constructed, no search needs to be done at all since it doesn't matter in what order the cities are visited. This would allow the problem to be ssss TSP used here is simpler than the NP-hard TSP). However, when the wave front is used, the buffer is at layer 4 and the only way of finding the plan is to generate all of the candidate goal sets at layer 4, of which there are an exponential number. The use of the wave front in this domain therefore forces Stan to take exponential time in the size of the instances.

Despite this the wave front offers great advantages. The benefits increase exponentially as instance sizes grow although the magnification of these benefits at each layer is only linear, see Figure 16, although the benefits are offset by the exponential growth in the number of candidates. It must be observed that in Figure 19, the figures are extrapolated for Ipp for instances in which n is greater than 14. The extrapolation was based on Ipp's performance on instance sizes between 2 and 14, which demonstrates a clear exponential growth.

It appears that we could allow the resource analysis to over-ride the wave front when a domain is encountered in which it can be guaranteed that explicit construction of the graph