On the Optimal Efficiency of A* with Dominance Pruning

A well known result is that, given a consistent heuristic and no other source of information, A * does expand a minimal number of nodes up to tie-breaking. We extend this analysis for A * with dominance pruning, which exploits a dominance relation to eliminate some nodes during the search. We show that the expansion order of A * is not necessarily optimally efficient when considering dominance pruning with arbitrary dominance relations, but it remains optimally efficient under certain restrictions for the heuristic and dominance relation.