Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation

Abstract

In optimal heuristic search, A* is known to be optimally efficient in terms of node expansions when the only source of information available to guide the search is a heuristic function. However, when a dominance relation is available, dominance pruning can further reduce the number of node expansions while preserving optimality. In this work, we show that pruning nodes does not fully leverage the information dominance relations provide. Instead, one can use dominance to propagate heuristic information between states. This results in a search algorithm that shares information among different regions of the search space. This is always as informative as dominance pruning, and can potentially reduce search effort.