Oversubscription planning: Complexity and compilability
2014 (English)In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AI Access Foundation , 2014, Vol. 3, 2221-2227 p.Conference paper (Refereed)
Many real-world planning problems are oversubscription problems where all goals are not simultaneously achievable and the planner needs to find a feasible subset. We present complexity results for the so-called partial satisfaction and net benefit problems under various restrictions; this extends previous work by van den Briel et al. Our results reveal strong connections between these problems and with classical planning. We also present a method for efficiently compiling oversubscription problems into the ordinary plan existence problem; this can be viewed as a continuation of earlier work by Keyder and Geffner.
Place, publisher, year, edition, pages
AI Access Foundation , 2014. Vol. 3, 2221-2227 p.
Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-116727ScopusID: 2-s2.0-84908192348ISBN: 9781577356790OAI: oai:DiVA.org:liu-116727DiVA: diva2:801501
28th AAAI Conference on Artificial Intelligence, AAAI 2014, 26th Innovative Applications of Artificial Intelligence Conference, IAAI 2014 and the 5th Symposium on Educational Advances in Artificial Intelligence, EAAI 2014