Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract)
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 296-297
DOI: 10.1609/socs.v19i1.43104 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Valerio Borelli und 3 weiteren Autor:innen.
Abstract (Originalsprache)
In this paper, we introduce Adaptive Width Best-First Search (AWBFS), a search algorithm designed to better exploit batched heuristic evaluation while preserving the guidance of Greedy Best-First Search (GBFS) when using learning-based heuristics on GPU architectures. The method targets domains in which learned heuristics are effective, but standard GBFS can stagnate on heuristic plateaus, a situation that is common in numeric planning. AWBFS addresses this issue by dynamically adjusting the number of frontier nodes expanded at each step. Starting from standard GBFS behavior, the algorithm increases the expansion width when no improvement in heuristic value is observed. For the use with learning-based heuristics, AWBFS tracks GPU memory usage to ensure it never exceeds the input limit. Experimental results show that AWBFS yields better performance than standard GBFS when paired with GNN-based heuristics.
Zitieren
APA
Borelli, V., Gerevini, A. E., Scala, E., & Serina, I. (2026). Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract). Proceedings of the International Symposium on Combinatorial Search, 19(1), 296-297. https://doi.org/10.1609/socs.v19i1.43104
Vancouver
Borelli V, Gerevini AE, Scala E, Serina I. Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract). Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):296-297. doi:10.1609/socs.v19i1.43104
BibTeX
@article{Borelli2026,
author = {Borelli, Valerio and Gerevini, Alfonso Emilio and Scala, Enrico and Serina, Ivan},
title = {Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract)},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {296--297},
doi = {10.1609/socs.v19i1.43104}
}
EUVIMED