ORCID Identifier(s)

0000-0002-1078-1897

Graduation Semester and Year

2020

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Science

Department

Computer Science and Engineering

First Advisor

Manfred Huber

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.

Keywords

Planning, Abstraction, Machine learning

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

29095-2.zip (2494 kB)

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.