On the Complexity of Domain-Independent Planning

Natural Language

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

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.