Bäckström, C. and Nebel, B. (1993). Complexity Results for SAS+ Planning. Technical Report LiTH-IDA-R-93-34, Department of Computer and Information Science, Linköping University, Sweden. A short version of this report appears in the Proceedings of the 13th International Conference on Artificial Intelligence, Chambery, France, Aug 29 - Sep 3, 1993. (bibtex),
Abstract: We have previously reported a number of tractable planning problems defined in the \SASx\ formalism. This \paper\ complements these results by providing a complete map over the complexity of \SASx\ planning under all combinations of the previously considered restrictions. We analyze the complexity both of finding a minimal plan and of finding any plan. In contrast to other complexity surveys of planning we study not only the complexity of the decision problems but also of the generation problems. We prove that the \SASx-PUS problem is the maximal tractable problem under the restrictions we have considered if we want to generate minimal plans. If we are satisfied with any plan, then we can generalize further to the \SASx-US problem, which we prove to be the maximal tractable problem in this case.
CS Dept TR Overview