Jacky Baltes.
DoLittle: a learning multi-strategy planning system.
PhD thesis,
University of Calgary,
June 1996.
Abstract: |
Multi-strategy planning focuses on the selection and combination of different problem solving methods. Since planning is intractable in complex domains, researchers have developed different methods to restrict, restructure, or reorder the search space and to search the new space. These reformulations of the search space are based on assumptions about the domain or other features of the task such as the problem order, plan structure, or subgoal hierarchy. These planners, then, work well in domains where the underlying assumptions are met, and fail otherwise. Furthermore, in complex domains it is possible that only parts of a task can be efficiently solved with a given planning method. But for other parts of the tasks, a different planning strategy may be appropriate. The goal of multi-strategy planning is to alleviate this problem by selecting and combining different problem solving methods on a single problem. First, planning is seen as search through the space of partial plans. Different planning strategies can be described by the language of partial plans, the set of transformations on partial plans, and the search method. Secondly, the thesis develops a theory of multi-strategy planning and shows that a multi-strategy planner can exponentially improve performance over a single strategy planner and derives sufficient conditions for this improvement. Thirdly, the thesis proposes \emph{general operators} (\Strips\ operators with added refinements) as a representation for different planning strategies and shows how general operators can represent different planning methods. Fourthly, the thesis develops a search control method that, given a planning method expressed as a general operator reduces the associated search space similarly to the original problem solving strategy. % The search strategy is based on a cheapest first method. Based on % the assumption that all planning strategies have similar reduction % probabilities, the planning strategy with the smallest refinement % cost is selected. Since the generation of general operators may be cumbersome by hand, and since the system is intended as a part of a learning apprentice system, \DoLittle\ learns new general operators from examples. The planning bias learners are highly specific methods that have knowledge of \DoLittle's operator set and search method and create new general operators to exploit a given planning bias. Through an empirical evaluation, this research shows (a) that multi-strategy planning improves the performance over single strategy planning in some toy domains, (b) that multi-strategy planning can solve problems in at least one complex domain (the kitchen domain), and (c) and that an unordered subproblem coordinated multi-strategy planner performs better in the kitchen domain than a problem coordinated one. |
@phdthesis{baltes-1996,
author = {Jacky Baltes},
title = {DoLittle: a learning multi-strategy planning system},
school = {University of Calgary},
year = 1996,
month = {June},
abstract = {Multi-strategy planning focuses on the selection and combination of different problem solving methods. Since planning is intractable in complex domains, researchers have developed different methods to restrict, restructure, or reorder the search space and to search the new space. These reformulations of the search space are based on assumptions about the domain or other features of the task such as the problem order, plan structure, or subgoal hierarchy. These planners, then, work well in domains where the underlying assumptions are met, and fail otherwise. Furthermore, in complex domains it is possible that only parts of a task can be efficiently solved with a given planning method. But for other parts of the tasks, a different planning strategy may be appropriate. The goal of multi-strategy planning is to alleviate this problem by selecting and combining different problem solving methods on a single problem. First, planning is seen as search through the space of partial plans. Different planning strategies can be described by the language of partial plans, the set of transformations on partial plans, and the search method. Secondly, the thesis develops a theory of multi-strategy planning and shows that a multi-strategy planner can exponentially improve performance over a single strategy planner and derives sufficient conditions for this improvement. Thirdly, the thesis proposes \emph{general operators} (\Strips\ operators with added refinements) as a representation for different planning strategies and shows how general operators can represent different planning methods. Fourthly, the thesis develops a search control method that, given a planning method expressed as a general operator reduces the associated search space similarly to the original problem solving strategy. % The search strategy is based on a cheapest first method. Based on % the assumption that all planning strategies have similar reduction % probabilities, the planning strategy with the smallest refinement % cost is selected. Since the generation of general operators may be cumbersome by hand, and since the system is intended as a part of a learning apprentice system, \DoLittle\ learns new general operators from examples. The planning bias learners are highly specific methods that have knowledge of \DoLittle's operator set and search method and create new general operators to exploit a given planning bias. Through an empirical evaluation, this research shows (a) that multi-strategy planning improves the performance over single strategy planning in some toy domains, (b) that multi-strategy planning can solve problems in at least one complex domain (the kitchen domain), and (c) and that an unordered subproblem coordinated multi-strategy planner performs better in the kitchen domain than a problem coordinated one. },
pdf = {http://aalab.cs.umanitoba.ca/%7ejacky/Publications/pdf/baltes-1996.pdf}
}