would also like to thank them, as well as Terry Zimmerman, Biplav Srivastava, Dan Weld, Avrim Blum and Steve Minton for comments on previous drafts of this paper. Special thanks are due to Dan Weld, who hosted me at University of Washington in Summer 1997, and spent time discussing the connections between CSP and Graphplan. Finally, I thank Mark Peot and David Smith for their clean Lisp implementation of the Graphplan algorithm, which served as the basis for my extensions.

## References

Anderson, C., Smith, D., & Weld, D. (1998). Conditional effects in graphplan. In Proc. AI Planning Systems Conference.

Bacchus, F., & van Run, P. (1995). Dynamic variable ordering in CSPs. In Proc. Principles and Practice of Constraint Programming (CP-95). Published as Lecture Notes in Artificial Intelligence, No. 976. Springer Verlag.

Bayardo, R., & Schrag, R. (1997). Using CSP look-back techniques to solve real-world sat instances. In *Proc. AAAI-97*.

Blum, A., & Furst, M. (1997). Fast planning through planning graph analysis. *Artificial Intelligence*,
90(1-2).

Bonet, B., Loerincs, G., & Geffner, H. (1999). A robust and fast action selection mechanism for planning. In *In Proc. AAAI-97*.

Do, B., & Kambhampati, S. (2000). Solving planning graph by compiling it into CSP. In *Proc. 5th* International Conference on AI Planning and Scheduling.

Do, B., Srivastava, B., & Kambhampati, S. (2000). Investigating the effect of relevance and reachability constraints on the sat encodings of planning. In *Proc. 5th International Conference on* AI Planning and Scheduling.

Fox, M. (1998). Private correspondence..

Fox, M., & Long, D. (1999). Efficient implementation of plan graph. *Journal of Artificial Intelligence Research*, 10.

Frost, D., & Dechter, R. (1994). In search of the best constraint satisfactions earch. In *Proc. AAAI94*.

Gelle, E. (1998). *On the generation of locally consistent solution spaces in mixed dynamic constraint problems*. Ph.D. thesis, Ingenieure informaticienne EPFL de nationalite Suisse, Lausanne, Switzerland.

Gerevini, A. (1999). Fast planning through greedy planning graphs. In *Proc. AAAI-99*.

Gomes, C., Selman, B., & Kautz, H. (1998). Boosting combinatorial search through randomization.

In *Proc. AAAI-98*, pp. 431–437.

Kambhampati, S. (1997). Challenges in bridging plan synthesis paradigms. In *Proc. IJCAI-97*.