On the Optimal Efficiency of A* with Dominance Pruning

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

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.
Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Publication date18 May 2021
Pages12007-12014
ISBN (Electronic)978-1-57735-866-4
Publication statusPublished - 18 May 2021
EventThe Thirty-Fifth AAAI Conference on Artificial Intelligence - Virtually
Duration: 2 Feb 20219 Feb 2021

Conference

ConferenceThe Thirty-Fifth AAAI Conference on Artificial Intelligence
LocationVirtually
Period02/02/202109/02/2021
SeriesProceedings of the AAAI Conference on Artificial Intelligence
Number13
Volume35
ISSN2374-3468

Keywords

  • Deterministic Planning

Fingerprint

Dive into the research topics of 'On the Optimal Efficiency of A* with Dominance Pruning'. Together they form a unique fingerprint.

Cite this