Date of Award

Spring 2012

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Wheeler Ruml

Abstract

In problem domains for which an informed admissible heuristic function is not available, one attractive approach is hierarchical search. Hierarchical search uses search in an abstracted version of the problem to dynamically generate heuristic values. This thesis makes three contributions to hierarchical search. First, we propose a simple modification to the state-of-the-art algorithm Switchback that reduces the number of expansions (and hence the running time) by approximately half, while maintaining its guarantee of optimality. Second, we propose a new algorithm for suboptimal hierarchical search, called Switch. Empirical results suggest that Switch yields faster search than straightforward modifications of Switchback, such as weighting the heuristic. Finally, we propose a modification to our optimal algorithm that uses multiple additive abstractions in order to improve performance of both optimal and suboptimal hierarchical search on some domains.

Download

Share

COinS