ML Anthology

On the Complexity of Domain-Independent Planning

Kutluhan Erol, Dana S. Nau, V. S. Subrahmanian
AAAI 1992 pp. 381-386
/aaai/1992/erol1992aaai-complexity/

Abstract

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 how the time complexity varies depending on a wide variety of conditions: • whether or not delete lists are allowed; • whether or not negative preconditions are allowed; • whether or not the predicates are restricted to be propositions (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.

PDF AAAI Semantic Scholar

Cite

Text

Erol et al. "On the Complexity of Domain-Independent Planning." AAAI Conference on Artificial Intelligence, 1992.

Markdown

[Erol et al. "On the Complexity of Domain-Independent Planning." AAAI Conference on Artificial Intelligence, 1992.](https://mlanthology.org/aaai/1992/erol1992aaai-complexity/)

BibTeX

@inproceedings{erol1992aaai-complexity,
  title     = {{On the Complexity of Domain-Independent Planning}},
  author    = {Erol, Kutluhan and Nau, Dana S. and Subrahmanian, V. S.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1992},
  pages     = {381-386},
  url       = {https://mlanthology.org/aaai/1992/erol1992aaai-complexity/}
}