EUVIMEDEUVIMED entdecken
Crossref

Beyond Pruning: Leveraging Dominance Relations for Heuristic Propagation

María Fernanda Salerno Garmendia, Daniel Fišer, Álvaro Torralba

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →