The computational complexity of propositional STRIPS planning

摘要

I present several computational complexity results for propositional STRIPS planning, i.e., STRIPS planning restricted to ground formulas. Different planning problems can be defined by restricting the type of formulas, placing limits on the number of pre-and postconditions, by restricting negation in pre- and postconditions, and by requiring optimal plans. For these types of restrictions, I show when planning is tractable (polynomial) and intractable (NP-hard). In general, it is PSPACE-complete to determine if a given planning instance has any solutions. Extremely severe restrictions on both the operators and the formulas are required to guarantee polynomial time or even NP-completeness. For example, when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. When definite Horn ground formulas are permitted, determining plan existence is PSPACE-complete even if operators are limited to zero preconditions and one postcondition. One of the interesting tractable problems is if each operator is restricted to positive preconditions and one postcondition (only ground literals). The blocks-world problem, slightly modified, is a subproblem of this restricted planning problem. These results in combination with previous analyses are not encouraging for domain-independent planning.