COMPLEXITY RESULTS FOR SAS+ PLANNING
Authors:
- 1 November 1995
- journal article
- Published by Wiley in Computational Intelligence
- Vol. 11 (4) , 625-655
Abstract
We have previously reported a number of tractable planning problems defined in the SAS+ formalism. This article complements these results by providing a complete map over the complexity of SAS+ planning under all combinations of the previously considered restrictions. We analyze the complexity of both finding a minimal plan and finding any plan. In contrast to other complexity surveys of planning, we study not only the complexity of the decision problems but also the complexity of the generation problems. We prove that the SAS+‐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 SAS+‐US problem, which we prove to be the maximal tractable problem in this case.Keywords
This publication has 11 references indexed in Scilit:
- The computational complexity of propositional STRIPS planningArtificial Intelligence, 1994
- On the computational complexity of temporal projection, planning, and plan validationArtificial Intelligence, 1994
- On the complexity of blocks-world planningArtificial Intelligence, 1992
- A validation-structure-based theory of plan modification and reuseArtificial Intelligence, 1992
- Planning in polynomial time: the SAS‐PUBS classComputational Intelligence, 1991
- Planning in polynomial time1990
- Reasoning about partially ordered eventsArtificial Intelligence, 1988
- Planning as search: A quantitative approachArtificial Intelligence, 1987
- Planning for conjunctive goalsArtificial Intelligence, 1987
- Strips: A new approach to the application of theorem proving to problem solvingArtificial Intelligence, 1971