On the Optimal Efficiency of A* with Dominance Pruning
Abstract
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.
Cite
Text
Torralba. "On the Optimal Efficiency of A* with Dominance Pruning." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17426Markdown
[Torralba. "On the Optimal Efficiency of A* with Dominance Pruning." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/torralba2021aaai-optimal/) doi:10.1609/AAAI.V35I13.17426BibTeX
@inproceedings{torralba2021aaai-optimal,
title = {{On the Optimal Efficiency of A* with Dominance Pruning}},
author = {Torralba, Álvaro},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {12007-12014},
doi = {10.1609/AAAI.V35I13.17426},
url = {https://mlanthology.org/aaai/2021/torralba2021aaai-optimal/}
}