

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

will be more efficient. In practice the Complete-Graph Travelling Salesman domain seems exceptional, since search is eliminated if the graph is constructed to layer n, and if this were not the case the explicit construction and subsequent search would be more costly than the use of the wave front.

## 5.1 The Wave Front Heuristic

The queue of candidate goal sets considered in the buffer can be implemented as an unordered structure in which goal sets are selected for consideration according to more sophisticated critena than the order in which they were stored. In principle, this could save much searching effort since it could avoid costly consideration of goal sets which turn out to be unsolvable before meeting a solvable goal set. We have experimented with a number of goal set selection heunstics which favour goal sets for which the search progresses deepest into the graph structure. These sets are considered to be closer to being solvable than sets which fail in a layer very close to the buffer. Candidates are evaluated by considering the length of the plan fragment associated with the candidate and the extent to which the failed search penetrated into the graph when initiated from the fix point layer when the candidate was first generated. The search penetration should be maximized while the plan fragment length should be minimized. Considering the goal sets in some order other than that in which they are generated does not affect any of the formal properties of the planner other than the optimality of the plans generated. Non-optimal plans can be favoured because