A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36919-36927
DOI: 10.1609/aaai.v40i43.41019 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Ehsan Futuhi und 1 weiteren Autor:innen.
Abstract (Originalsprache)
The rapid advancement of GPU technology has unlocked powerful parallel processing capabilities, creating new opportunities to enhance classic search algorithms. This hardware has been exploited in best-first search algorithms with neural network-based heuristics by creating batched versions of A* and Weighted A* that delay heuristic evaluation until sufficiently many states can be evaluated in parallel on the GPU. But, research has not addressed how depth-first algorithms like IDA* or Budgeted Tree Search (BTS) can have their heuristic computations batched. This is more complicated in a tree search, because progress in the search tree is blocked until heuristic evaluations are complete. In this paper we show that GPU parallelization of heuristics can be effectively performed when the tree search is parallelized on the CPU while heuristic evaluations are parallelized on the GPU. We develop a parallelized cost-bounded depth-first search (CB-DFS) framework that can be applied to both IDA* and BTS, significantly improving their performance. We demonstrate the strength of the approach on the 3x3 Rubik's Cube and the 4x4 sliding tile puzzle (STP) with both classifier-based and regression-based heuristics.
Zitieren
APA
Futuhi, E., & Sturtevant, N. R. (2026). A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36919-36927. https://doi.org/10.1609/aaai.v40i43.41019
Vancouver
Futuhi E, Sturtevant NR. A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36919-36927. doi:10.1609/aaai.v40i43.41019
BibTeX
@article{Futuhi2026,
author = {Futuhi, Ehsan and Sturtevant, Nathan R.},
title = {A Parallel CPU-GPU Framework for Batching Heuristic Operations in Depth-First Heuristic Search},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36919--36927},
doi = {10.1609/aaai.v40i43.41019}
}
EUVIMED