Planning in Polynomial Time
1990 (English)In: Proceedings of the 9th Annual Workshop and Meeting of the Swedish AI Society, 1990Conference paper (Other academic)
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
Planning, Polynomial time, Computational tractability
IdentifiersURN: urn:nbn:se:liu:diva-100556OAI: oai:DiVA.org:liu-100556DiVA: diva2:663072
9th Annual Workshop and Meeting of the Swedish AI Society, April, 1990, Stockholm, Sweden