construction efficiency obtained by the use of the spike. The second set of data shows the advantages obtained during the search of the plan graph by using the wave front.

STAN also employs the state invanant inference machinery of TIM (Fox & Long, 1998),
but in version 2 the integration of the invariants into the graph construction process is still only partial. We observe that the mutex relations generated in the Complete-Graph TSP, in particular, are almost entirely domain invariants of the kind inferred by T I M . Integration of these inferred invariants into the graph would allow these mutex relations to be identified immediately as permanent and eliminate them from retesting, dramatically enhancing STAN's graph construction performance in this domain. A similar advantage would be obtained across other domains since many of the mutex relations inferred during graph construction correspond to invariants of the various forms inferred efficiently by Tim during a preprocessing stage.

## Appendix A. Website Addresses

Online Appendix 1 contains a complete collection of the domains and problems used in this paper, executables (Linux and Sparc-Solaris binaries) for STAN and the reduced version of STAN for graph construction, and a diff file showing how the graph constructing version of IPP was generated.

The results of the AIPS-98 planning competition can be found at:
http://ftp.cs.yale.edu/pub/mcdermott/aipscomp-results.html.

The STAN website can be found at:
http://www.dur.ac.uk/~dcsOwww/research/stanstuff/planpage.html.

## References

Blum, A., & Furst, M. (1997). Fast Planning through Planning Graph Analysis. Artificial Intelligence, 90, 281–300.

Fox, M., & Long, D. (1998). The Automatic Inference of State Invariants in TIM. JAIR,
9, 317 371.

Kambhampati, S. (1998). EBL and DDB for Graphplan. Tech. rep. ASU CSE TR 98-008, Arizona State University.

Kambhampati, S. (199). On the Relations Between Intelligent Backtracking and Explanation Based Learning in Planning and CSP. Artificial Intelligence, 105 (1-2).

Koehler, J., Nebel, B., & Dimopoulos, Y. (1997). Extending Planning Graphs to an ADL
Subset. In Proceedings of 4th European Conference on Planning.

Smith, D., & Weld, D. (1998). Incremental Graphplan. Tech. rep. TR 98-09-06, University of Washington.