Computer Science Department
School of Computer Science, Carnegie Mellon University
Learning Domain-Specific Planners from Example Plans
Elly Zoe Winner
Automated problem solving involves the ability to select actions from a specific state to reach objectives. Classical planning research has addressed this problem in a domain-independent manner–the same algorithm generates a complete plan for any domain specification. While this generality is in principle desirable, it comes at a cost which domain-independent planners incur either in high search efforts or in tedious hand-coded domain knowledge.
Previous approaches to efficient general-purpose planning have focused on reducing the search involved in an existing general-purpose planning algorithm. Others abandoned the general-purpose goal and developed specialpurpose planners highly optimized in efficiency for the specific aspects of a particular problem solving domain. An interesting alternative is to use example plans in a particular domain to demonstrate how to solve problems in that domain and to use that information to solve new problems independently of a domain-independent planner. Others have used example plans for case-based and analogical planning, but the retrieval and adaptation mechanisms were still domain-independent and efficiency issues were still a concern. Recently, example plans have been used to induce decision lists, but many examples and hours or even days of computation time were needed to learn the lists.
This thesis presents a novel way of using example plans: by analyzing
individual example plans thoroughly, our algorithms reveal the rationale and
structure underlying the plan, and use this information to rapidly learn
complex, looping domain-specific planners (or dsPlanners) automatically.
In this thesis, I introduce the dsPlanner language, a clear, human-readable
programming language for describing learnable domain-specific planners;