General Policies, Serializations, and Planning Width
Preprint
Abstract
It has been observed that in many of the benchmark planning domains, atomic goals can be reached with a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width. Such problems have indeed a bounded width: a width that does not grow with the number of problem variables and is often no greater than two. Yet, while the notion of width has become part of the state-of-the-art planning algorithms like BFWS, there is still no good explanation for why so many benchmark domains have bounded width. In this work, we address this question by relating bounded width and serialized width to ideas of generalized planning, where general policies aim to solve multiple instances of a planning problem all at once. We show that bounded width is a property of planning domains that admit optimal general policies in terms of features that are explicitly or implicitly represented in the domain encoding. The results are extended to much larger class of domains with bounded serialized width where the general policies do not have to be optimal. The study leads also to a new simple, meaningful, and expressive language for specifying domain serializations in the form of policy sketches which can be used for encoding domain control knowledge by hand or for learning it from traces. The use of sketches and the meaning of the theoretical results are all illustrated through a number of examples.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Planning With Pixels in (Almost) Real TimeProceedings of the AAAI Conference on Artificial Intelligence, 2018
- The actorʼs view of automated planning and acting: A position paperArtificial Intelligence, 2014
- A Concise Introduction to Models and Methods for Automated PlanningSynthesis Lectures on Artificial Intelligence and Machine Learning, 2013
- The Arcade Learning Environment: An Evaluation Platform for General AgentsJournal of Artificial Intelligence Research, 2013
- Abandoning Objectives: Evolution Through the Search for Novelty AloneEvolutionary Computation, 2011
- The LAMA Planner: Guiding Cost-Based Anytime Planning with LandmarksJournal of Artificial Intelligence Research, 2010
- Automatic Derivation of Memoryless Policies and Finite-State Controllers Using Classical PlannersProceedings of the International Conference on Automated Planning and Scheduling, 2009
- In defense of PDDL axiomsArtificial Intelligence, 2005
- Ordered Landmarks in PlanningJournal of Artificial Intelligence Research, 2004
- A Sufficient Condition for Backtrack-Free SearchJournal of the ACM, 1982