Efficient Planning Using Plan Libraries to Capture the Structure of the State Space

Ph.D. Dissertation Defense

Automated, domain-independent planning is a research area within Artificial Intelligence that is used in a variety of practical applications, especially those for which a large degree of autonomy is required. Planning programs that are given information about the current state of the world, the available actions, and a set of goals that should be achieved. The planner's task is determining the plan: a set of actions and ordering constraints among them. A domain-independent planner is not tailored for a specific planning domain but can understand any domain encoded in a generic, expressive description language. Ideally, in domain-independent planning, the planner should be able to analyze the domain on its own, and adjust its reasoning method accordingly.

This work focuses on improving the speed of automated, domain-independent planners in different planning domains by automatically reusing the planner's experience from previous planning episodes, and proactively exploring the problem to gather more experience about it. The experience is then stored in a novel type of plan library called a planning backbone, which contains the explored parts of the state space graph for the planning problem. Since the state space of a planning problem is closely related to the structure of the problem, the backbone approach results in a plan library that reflects that underlying structure.

The dissertation presents algorithms for building planning backbones, modifying them, and using them in planning. It also presents a theoretical analysis of topological properties of state spaces for benchmark planning domains, and examines the effect of these topological properties on backbone coverage and the resulting performance improvements in planners that use the backbone.

Dissertation committee members:

• Dr. Marie desJardins (Chair)
• Dr. Tim Oates
• Dr. Tim Finin
• Dr. Fusun Yaman
• Dr. Dana Nau (UMCP)