Elly Zoe Winner

Learning Domain-Specific Planners From Example Plans Degree Type: Ph.D. in Computer Science
Advisor(s): Manuela M. Veloso
Graduated: May 2008

Abstract:

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 special- purpose 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 and -writeable programming language for describing learnable domain-specific planners; the SPRAWL algorithm for analyzing observed plans and uncovering the rationale underlying the plan; the DISTILL algorithm for automatically learning non-looping dsPlanners from sets of example plans; and the Loop- DISTILL algorithm for automatically learning looping dsPlanners from examples. I show that the careful analysis of example plans can make learning so efficient that a dsPlanner that covers large classes of arbitrarily large problems can be learned from a single example in under a second for a wide variety of domains. Automatically learned dsPlanners can then be used to solve new planning problems in linear time, modulo state matching effort.

Thesis Committee:
Manuela Veloso (Chair)
Avrim Blum
Reid Simmons
Leslie Kaelbling (M.I.T.)

Peter Lee, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Planning, Learning, Domain-specific planning, Program synthesis, Looping plan learning