November 13, 1998
3:15pm

Rob Holte
School of Information Technology and Engineering
University of Ottawa

Hierarchical Search using Multiple Abstractions

In hierarchical heuristic search the distance estimates used to guide search are computed by finding exact distances in an abstract, smaller search space. My previous work on Hierarchical A* used a single abstract space, but the the closely related work on Pattern Databases (by Culberson and Schaeffer) has always used multiple abstractions.

This talk presents the initial results of an ongoing experimental investigation of the effectiveness of multiple abstractions in hierarchical search. One goal of this work is to derive insight into which abstractions (or sets of abstractions) produce the most effective heuristics. A second goal is to understand the space-time tradeoff of memory-intensive methods such as Hierarchical A* and Pattern Databases. The talk will present the first direct evidence concerning Korf's conjecture that for these methods memory*(search time) is a constant.