Learning Abstractions for Planning

Abstract

Planners for hard problems must exploit domain-specific structure to find solutions efficiently. Yet, hand-engineered solutions and optimizations are often expensive and difficult or impossible to adapt to other problems. This work applies automatic machine learning techniques to increase planner performance for specific problem domains and to learn useful abstract representations for planning. In particular, this dissertation develops methods to address important aspects of learning in planning in four different areas:

State-of-the-art domain-independent classical planners utilize multiple search heuristics and decide how to allocate computational effort between heuristics prior to planning. This work presents a heuristic planning algorithm that uses a learned model of heuristic search dynamics to dynamically allocate computational effort to available heuristics during planning.

Non-parametric function approximators can be used to represent state transition models, reachability estimators and distance functions for planning. However when training data is not uniformly distributed, variations in sample density can result in local neighborhood bias that negatively affects accuracy. Two new algorithms are presented for k-nearest neighbor (kNN) regression and classification that explicitly compensate for the asymmetric distribution of local neighborhood samples.

A novel abstraction-guided planning algorithm using control policies is presented and implemented for a multi-goal physics-based game. This work develops learned predictive models for abstract state connectivity and control policy utility and shows they can increase the efficiency of exploration and construction of the abstract model.

Lastly, this work proposes a novel approach for automatically identifying useful abstract states using random transition sampling and graph analysis. Experiments show the method yields results similar to hand-engineered abstractions implemented by human experts for the same domain.