On the Optimal Efficiency of A* with Dominance Pruning

No. 13: AAAI-21 Technical Tracks 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Planning, Routing, and Scheduling

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.

10.1609/aaai.v35i13.17426