IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Fri, 24 Oct 2014 20:05:32

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.


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>