Intermediate Results on the Complexity of STRIPS$_{1}^{1}$
This work tackles a theoretical problem in AI planning, providing incremental insights into the complexity of a specific STRIPS variant.
The paper investigates the computational complexity of propositional STRIPS planning, specifically addressing whether STRIPS$^1_1$ (with operators limited to one precondition and one effect) is NP-complete, by using SAT solvers, literal graphs, and Petri nets to analyze small instances.
This paper is based on Bylander's results on the computational complexity of propositional STRIPS planning. He showed that when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. While NP-hardness is settled, it is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete. We shed light on the question whether this small solution hypothesis for STRIPS$^1_1$ is true, calling a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.