Faster Optimal and Suboptimal Hierarchical Search

Authors

  • Michael Leighton University of New Hampshire
  • Wheeler Ruml University of New Hampshire
  • Robert Holte University of Alberta

DOI:

https://doi.org/10.1609/socs.v2i1.18203

Keywords:

hierarchical, search, optimal, suboptimal, Short Circuit, Switch

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 paper makes two 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 or greedy search. The success of Switch illustrates the potential for further research on specifically suboptimal hierarchical search.

Downloads

Published

2021-08-19