Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning
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.
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}
}
EUVIMED