Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation
Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 237-246
DOI: 10.1609/icaps.v36i1.42833 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von María Fernanda Salerno Garmendia und 2 weiteren Autor:innen.
Abstract (Originalsprache)
In optimal heuristic search, A* is known to be optimally efficient in terms of node expansions when the only source of information available to guide the search is a heuristic function. However, when a dominance relation is available, dominance pruning can further reduce the number of node expansions while preserving optimality. In this work, we show that pruning nodes does not fully leverage the information dominance relations provide. Instead, one can use dominance to propagate heuristic information between states. This results in a search algorithm that shares information among different regions of the search space. This is always as informative as dominance pruning, and can potentially reduce search effort.
Zitieren
APA
Garmendia, M. F. S., Fišer, D., & Torralba, Á. (2026). Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 237-246. https://doi.org/10.1609/icaps.v36i1.42833
Vancouver
Garmendia MFS, Fišer D, Torralba Á. Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):237-246. doi:10.1609/icaps.v36i1.42833
BibTeX
@article{Garmendia2026,
author = {Garmendia, María Fernanda Salerno and Fišer, Daniel and Torralba, Álvaro},
title = {Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2026},
volume = {36},
number = {1},
pages = {237--246},
doi = {10.1609/icaps.v36i1.42833}
}
EUVIMED