Understanding and extending Graphplan

Abstract

We provide a reconstruction of Blum and Furst's Graphplan algorithm, and use the reconstruction to extend and improve the original algorithm in several ways. In our reconstruction, the process of growing the planning-graph and inferring mutex relations corresponds to doing forward state-space refinement over disjunctively represented plans. The backward search phase of Graphplan corresponds to solving a binary dynamic constraint satisfaction problem. Our reconstruction sheds light on the sources of strength of Graphplan. We also use the reconstruction to explain how Graphplan can be made goal-directed, how it can be extended to handle actions with conditional effects, and how backward state-space refinement can be generalized to apply to disjunctive plans. Finally, we discuss how the backward search phase of Graphplan can be improved by applying techniques from CSP literature, and by teasing apart planning and scheduling (resource allocation) phases in Graphplan.

This research is supported in part by the NSF NYI award IRI-9457634, the ARPI Initiative grant F30602-95-C-0247 and the ARPA AASERT grant DAAH04-96-1-0231. We would like to thank Avrim Blum and Dan Weld for helpful discussions on Graphplan, and Mark Peot and David Smith for making their Lisp implementation of Graphplan available to us.