Planning in Polynomial Time
1990 (English)In: Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems: Selected Papers, 1990, 125-129 p.Conference paper (Refereed)
This paper describes a polynomial-time, O(n 3), 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. 125-129 p.
Planning, Polynomial time, Computational tractability
IdentifiersURN: urn:nbn:se:liu:diva-91620ISBN: 9780444015754OAI: oai:DiVA.org:liu-91620DiVA: diva2:626234
5th International Symposium on Methodologies for Intelligent Systems, Knoxville, TN, USA, October, 1990