On the Optimal Efficiency of A* with Dominance Pruning

Authors

  • Álvaro Torralba Aalborg University

Keywords:

Deterministic Planning

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.

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17426

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling