On the complexity of domain-independent planning
Kutluhan Erol, Dana S. Nau, V. S. Subrahmanian · 1992
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.