DOI:
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.