EUVIMEDEUVIMED entdecken
Crossref

Adaptive Width Best-First Search: Dynamic Frontier Expansion for GNN-based Heuristics (Extended Abstract)

Valerio Borelli, Alfonso Emilio Gerevini, Enrico Scala, Ivan Serina

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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