mjr58, ruml at cs.unh.edu

holte at cs.ualberta.ca In problem domains for which an informed admissible heuris-tic function is not available, one attractive approach is hi-erarchical search. Hierarchical search uses search in an abstracted version of the problem to dynamically generate heuristic values. This paper makes two contributions to hi-erarchical 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 ap-proximately half, while maintaining its guarantee of optimal-ity. Second, we propose a new algorithm for suboptimal hi-erarchical search, called Switch. Empirical results suggest that Switch yields faster search than straightforward modi-fications of Switchback, such as weighting the heuristic or greedy search. The success of Switch illustrates the poten-tial for further research on specifically suboptimal hierarchi-cal search