EUVIMEDEUVIMED entdecken
Crossref

Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning

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) · 247-255

DOI: 10.1609/icaps.v36i1.42834 ↗

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)

Dominance pruning is a technique to reduce search effort by comparing states against each other and discarding dominated states. However, despite being effective at significantly reducing the number of expansions in many domains, the overhead of comparing states may lead to reduced performance. This is specially critical in hard problems, as the overhead of comparing all pairs of states grows quadratically with the number of explored states. In this paper, we investigate how to use data structures that exploit the inner structure of dominance relations in order to perform this check efficiently. We show that these data structures can avoid the quadratic worst-case in many domains, significantly improving the performance of search with dominance pruning.

Zitieren

APA

Garmendia, M. F. S., Fišer, D., & Torralba, Á. (2026). Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 247-255. https://doi.org/10.1609/icaps.v36i1.42834

Vancouver

Garmendia MFS, Fišer D, Torralba Á. Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):247-255. doi:10.1609/icaps.v36i1.42834

BibTeX
@article{Garmendia2026,
  author = {Garmendia, María Fernanda Salerno and Fišer, Daniel and Torralba, Álvaro},
  title = {Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2026},
  volume = {36},
  number = {1},
  pages = {247--255},
  doi = {10.1609/icaps.v36i1.42834}
}
Kostenlos starten →