@inproceedings{e44b57b7025f47d4b12f27fa47679ba6,
title = "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.",
keywords = "Deterministic Planning",
author = "Alvaro Torralba",
year = "2021",
month = may,
day = "18",
language = "English",
series = "Proceedings of the AAAI Conference on Artificial Intelligence",
publisher = "AAAI Press",
number = "13",
pages = "12007--12014",
booktitle = "Proceedings of the AAAI Conference on Artificial Intelligence",
address = "United States",
note = "The Thirty-Fifth AAAI Conference on Artificial Intelligence ; Conference date: 02-02-2021 Through 09-02-2021",
}