Multihierarchical graph search

The use of hierarchical graph search for finding paths in graphs is well known in the literature, providing better results than plain graph search regarding computational costs in many cases. This paper offers a step forward by including multiple hierarchies in a graph-based model. Such a multihierarchical model has the following advantages: First, a multiple hierarchy permits us to choose the best hierarchy to solve each search problem; second, when several search problems have to be solved, a multiple hierarchy provides the possibility of solving part of them simultaneously; and third, solutions to the search problems can be expressed in any of the hierarchies of the multiple hierarchy, which allows us to represent the information in the most suitable way for each specific purpose. In general, multiple hierarchies have proven to be a more adaptable model than single-hierarchy or nonhierarchical models. This paper formalizes the multihierarchical model, describes the techniques that have been designed for taking advantage of multiple hierarchies in a hierarchical path search, and presents some experiments and results on the performance of these techniques.