Complexity, decidability and undecidability results for domain-independent planning

Kutluhan Erol*, Dana S. Nau, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

125 Scopus citations


In this paper, we examine how the complexity of domain-independent planning with STRIPS-style operators depends on the nature of the planning operators. We show conditions under which planning is decidable and undecidable. Our results on this topic solve an open problem posed by Chapman (1987), and clear up some difficulties with his undecidability theorems. For those cases where planning is decidable, we explain how the time complexity varies depending on a wide variety of conditions: • • whether or not function symbols are allowed; • • whether or not delete lists are allowed; • • whether or not negative preconditions are allowed; • • whether or not the predicates are restricted to be propositional (i.e., 0-ary); • • whether the planning operators are given as part of the input to the planning problem, or instead are fixed in advance. • • whether or not the operators can have conditional effects.

Original languageEnglish (US)
Pages (from-to)75-88
Number of pages14
JournalArtificial Intelligence
Issue number1-2
StatePublished - Jul 1995
Externally publishedYes

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Complexity, decidability and undecidability results for domain-independent planning'. Together they form a unique fingerprint.

Cite this