On the Optimal Efficiency of A* with Dominance Pruning
DOI:
https://doi.org/10.1609/aaai.v35i13.17426Keywords:
Deterministic PlanningAbstract
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.Downloads
Published
2021-05-18
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. https://doi.org/10.1609/aaai.v35i13.17426
Issue
Section
AAAI Technical Track on Planning, Routing, and Scheduling