The Tradeoff Between Speed and Optimality in Hierarchical Search.pdfVIP

The Tradeoff Between Speed and Optimality in Hierarchical Search R.C. Holte, M.B. Perez, R.M. Zimmer, A.J. MacDonald Abstract Abstraction works by replacing a state space, SS, by another, abstract space that is easier to search, SS′. There are two well-known strategies for employing the abstract solutions found in SS′ to guide search in the original space. The first uses the lengths of the abstract solutions as a heuristic for an A* search of S S. This always produces optimal solutions. The second strategy uses the steps in the abstract solutions as subgoals for the search in SS. This strategy does not guarantee optimality, but it does tend to find a solution quickly. In this paper, we study the trade- offs between the loss of optimality and the gain of speed in mo ving from the one strategy to the other. To perform the study, we introduce two continuous parameters whose extreme values repr esent these two strategies. Because the parameters are continuous we end up with a whole family of str ategies that lie between these two. Using these parameters, we give extensive empirical results of the effects of perturbing the parameters on searches in eight different benchmarks. This allows us to track a continuous trade-off b etween optimality and speed throughout the space of hierarchic searches. The Tradeoff Between Speed and Optimality in Hierarchical Search 1 1 2 3 R.C. Holte , M.B. Perez , R.M. Zimmer , A.J. MacDonald 1. Introduction This paper draws together two separate strands of research. The common idea is that of hierarchical search, i.