Limits for compact representations of plans
2011 (English)In: ICAPS 2011 : proceedings of the twenty-first international conference on automated planning and scheduling : annual ICAPS conference : Jun 2011, Freiburg, Germany / [ed] Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp, Malte Helmert, AAAI Press, 2011, 18-25 p.Conference paper (Refereed)
Most planning formalisms allow instances with shortest plans of exponential length. While such instances are problematic, they are usually unavoidable and can occur in practice. There are several known cases of restricted planning problems where plans can be exponential but always have a compact (ie. polynomial) representation, often using recursive macros. Such compact representations are important since exponential plans are difficult both to use and to understand. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. Further, we show that it is unlikely to get around this by reformulating planning into some other problem. The results are discussed in the context of abstraction, macros and plan explanation.
Place, publisher, year, edition, pages
AAAI Press, 2011. 18-25 p.
IdentifiersURN: urn:nbn:se:liu:diva-74513ISBN: 978-1-57735-503-8OAI: oai:DiVA.org:liu-74513DiVA: diva2:486229
The Twenty-First International Conference on Automated Planning and Scheduling, June 11–16,Freiburg, Germany