The Tradeoff Between Speed and Optimality in Hierarchical Search
Abstraction works by replacing a state space,SS, by another,'abstract' space that is easier to
search,SS¢.Thereare two wellknown strategies for employing the 'abstract' solutions found in
SS¢ to guide search inthe original space.The first uses the lengths of the abstract solutions as a
heuristic for an A* search ofSS. This always produces optimal solutions. The second strategy
uses the steps in the abstract solutions as subgoals for the search inSS. This strategy does not
guarantee optimality,but it does tend to find a solution quickly.Inthis paper,westudy the trade
offs between the loss of optimality and the gain of speed in moving from the one strategy to the
other.Toperform the study,weintroduce two continuous parameterswhose extreme values
represent these two strategies. Because the parametersare continuous we end up with a whole
family of strategies that lie between these two. Using these parameters, we give extensive
empirical results of the effects of perturbing the parametersonsearches in eight different
benchmarks. This allows us to trackacontinuous tradeoffbetween optimality and speed
throughout the space of hierarchic searches.
Citation
R. Holte,
A. MacDonald,
M. Perez,
R. Zimmer.
"The Tradeoff Between Speed and Optimality in Hierarchical Search". Technical Report, January 1995.
| Keywords: |
tradeoff, optimality, machine learning |
| Category: |
Technical Report |
BibTeX
@manual{Holte+al:95,
author = {Robert Holte and Alan J. MacDonald and M.B. Perez and Robert
Zimmer},
title = {The Tradeoff Between Speed and Optimality in Hierarchical Search},
year = 1995,
}Last Updated: January 04, 2007
Submitted by Christian Smith 
