@techreport{R-90-16, TITLE = {Planning in Polynomial Time: The SAS-PUBS Class. This revised version appears in Computational Intelligence 7(3):181-197(1991) }, AUTHOR = {Christer B{\"a}ckstr{\"o}m and Inger Klein}, YEAR = {1990}, NUMBER = {R-90-16}, INSTITUTION = ida, ADDRESS = idaaddr, ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-90-16+abstr}, 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.}, IDANR = {LiTH-IDA-R-90-16}, NOTE = {A short version appears in Expert Systems in Engineering: Principles and Applications. International Workshop, pages 103-118, Vienna, Austria, September 1990}