Bäckström, C. and Klein, I. (1990). Planning in Polynomial Time: The SAS-PUBS Class. This revised version appears in Computational Intelligence 7(3):181-197(1991). Technical Report LiTH-IDA-R-90-16, Department of Computer and Information Science, Linköping University, Sweden. A short version appears in Expert Systems in Engineering: Principles and Applications. International Workshop, pages 103-118, Vienna, Austria, September 1990. (bibtex),
Abstract: This paper describes a polynomial-time, O(n3), planning algorithm for a limited class of planning problems. Compared to previous work on complexity of algorithms for knowledge-based or logic-based planning, our algorithm achieves computational tractability, but at the expense of only applying to a significantly more limited class of problems. Our algorithm is proven correct and complete, and it always returns a minimal plan if there is a plan at all.
CS Dept TR Overview