Understanding and extending Graphplan

Subbarao Kambhampati, Eric Parker, Eric Lambrecht

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations


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 Graph-plan. 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.

Original languageEnglish (US)
Title of host publicationRecent Advances in AI Planning - 4th European Conference on Planning, ECP 1997, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540639128, 9783540639121
StatePublished - 1997
Event4th European Conference on Planning, ECP 1997 - Toulouse, France
Duration: Sep 24 1997Sep 26 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1348 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th European Conference on Planning, ECP 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Understanding and extending Graphplan'. Together they form a unique fingerprint.

Cite this