GPU-Accelerated A* Search with Deep Neural Network Heuristics
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 148-156
DOI: 10.1609/socs.v19i1.43083 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Misagh Soltani und 1 weiteren Autor:innen.
Abstract (Originalsprache)
Heuristic search is a foundational technique in artificial intelligence. Recent work has demonstrated that powerful heuristic functions represented as deep neural networks (DNNs) can be learned with machine learning. This combination of machine learning and heuristic search has been successfully applied to puzzle solving, quantum circuit synthesis, and chemical reaction mechanism pathfinding. This success has been accompanied by batched heuristic search algorithms, such as batch A* search, which take advantage of parallelism provided by graphics processing units (GPUs) for DNNs. However, the rest of the heuristic search algorithm remains on the central processing unit (CPU). This results in the often costly transfer of data from the CPU to the GPU for heuristic computation and leaves other GPU-based acceleration options unexplored. To address this, we investigate the benefit of performing heuristic search entirely on the GPU. Using the Rubik's Cube as our case study, we systematically profile the speedup achieved by each component of batch A* search when moved to the GPU. Our results show that GPU execution yields about 12.03× speedup over the CPU baseline that only uses the GPU for the heuristic function. These findings suggest that fully GPU-native heuristic search with DNNs is a practical and effective strategy for scaling learned heuristics to demanding combinatorial search tasks.
Zitieren
APA
Soltani, M., & Agostinelli, F. (2026). GPU-Accelerated A* Search with Deep Neural Network Heuristics. Proceedings of the International Symposium on Combinatorial Search, 19(1), 148-156. https://doi.org/10.1609/socs.v19i1.43083
Vancouver
Soltani M, Agostinelli F. GPU-Accelerated A* Search with Deep Neural Network Heuristics. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):148-156. doi:10.1609/socs.v19i1.43083
BibTeX
@article{Soltani2026,
author = {Soltani, Misagh and Agostinelli, Forest},
title = {GPU-Accelerated A* Search with Deep Neural Network Heuristics},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {148--156},
doi = {10.1609/socs.v19i1.43083}
}
EUVIMED