November 13, 1998
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.