Complexity Results for Planning

Abstract

I describe several computational complexity results for planning, some of which identify tractable planning problems. The model of planning, called "propositional planning," is simple-conditions within operators are literals with no variables allowed . The different planning problems are defined by different restrictions on the preconditions and postconditions of operators. The main results are: Propositional planning is PSPACE-complete, even if operators are restricted to two positive (nonnegated) preconditions and two postconditions, or if operators are restricted to one postcondition (with any number of preconditions). It is NP-complete if operators are restricted to positive postconditions, even if operators are restricted to one precondition and one positive postcondition. It is tractable in a few restricted cases, one of which is if each operator is restricted to positive preconditions and one postcondition. The blocks-world problem, slightly modified, is a subproblem of this restricted planning problem.