Planning in Polynomial Time
1990 (English)In: Porceedings of the 1990 International Workshop on Expert Systems in Engineering, Principles and Applications, 1990, 103--118 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
1990. 103--118 p.
Planning, Polynomial time, Computational tractability
IdentifiersURN: urn:nbn:se:liu:diva-91619DOI: 10.1007/3-540-53104-1_36ISBN: 978-3-540-46711-3OAI: oai:DiVA.org:liu-91619DiVA: diva2:626231
1990 International Workshop on Expert Systems in Engineering, Principles and Applications, Vienna, Austria, September, 1990