On the Optimal Efficiency of A* with Dominance Pruning
AbstractA 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.
How to Cite
Torralba, Álvaro. (2021). On the Optimal Efficiency of A* with Dominance Pruning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 12007-12014. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17426
AAAI Technical Track on Planning, Routing, and Scheduling