On the Optimal Efficiency of A* with Dominance Pruning

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citationer (Scopus)

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.
OriginalsprogEngelsk
TitelProceedings of the AAAI Conference on Artificial Intelligence
ForlagAAAI Press
Publikationsdato18 maj 2021
Sider12007-12014
ISBN (Elektronisk)978-1-57735-866-4
StatusUdgivet - 18 maj 2021
BegivenhedThe Thirty-Fifth AAAI Conference on Artificial Intelligence - Virtually
Varighed: 2 feb. 20219 feb. 2021

Konference

KonferenceThe Thirty-Fifth AAAI Conference on Artificial Intelligence
LokationVirtually
Periode02/02/202109/02/2021
NavnProceedings of the AAAI Conference on Artificial Intelligence
Nummer13
Vol/bind35
ISSN2374-3468

Fingeraftryk

Dyk ned i forskningsemnerne om 'On the Optimal Efficiency of A* with Dominance Pruning'. Sammen danner de et unikt fingeraftryk.

Citationsformater