The computational complexity of propositional STRIPS planning

Reviewer: Kutluhan Erol

A number of computational complexity results are presented for STRIPS-style planning problems under the restriction that no variables are allowed. Many classical, domain-independent AI planning systems are based on STRIPS representation. The paper also discusses an extension to the STRIPS representation, which augments it via a domain theory (a set of formulas that describe the stationary properties of the world). The paper is a successful attempt at “providing a complexity map of the territory of planning,” as the author puts it, although there is still much to be explored. The introduction does a good job of describing the planning problem and explaining the related work on the complexity of planning. It also provides a summary of the results and their implications, shielding the casual reader from the technical details presented in the rest of the paper. Nonetheless, familiarity with STRIPS-style planning is required to follow the arguments. The remarks section is especially intriguing, although not everyone will agree with Bylander's conclusions.