DoLittle: A learning multi-strategy planner

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 general operators (S scTRIPS 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 similarity to the original problem solving strategy.;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, D scOL scITTLE learns new general operators from examples. The planning bias learners are highly specific methods that have knowledge of D scOL scITTLE'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.