In Search of the Tractability Boundary of Planning Problems

All Papers

Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. To this end, we present complexity results for two classes of planning problems from the literature. First, we show that approximating a solution to a planning problem in the class 3S to within polynomial factors is NP-hard. We also show that plan existence is NP-hard for planning problems with chain causal graphs and variables with domain size at most 7. In addition to the immediate implications, our results provide some insight into what makes some planning problems intractable.