On the Complexity of Domain-Independent Planning

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.

Authors

• Kutluhan Erol James Hendler

Keywords

No keywords are indexed for this paper.