EUVIMEDEUVIMED entdecken
Crossref

Parallelizing Classical Planning: Critical Path Heuristics on the GPU

Markus Fritzsche, David Speck, Daniel Gnad, Simon Ståhlberg

Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 219-223

DOI: 10.1609/socs.v19i1.43091 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Markus Fritzsche und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Despite the tremendous capabilities of modern hardware in performing parallel computations, all major classical planners are limited to single-threaded execution on the CPU. We show how the critical path heuristic hm, commonly used in classical planning, can be parallelized and computed on a GPU. To that end, we construct a directed hypergraph, where nodes represent sets of atoms, associated with their reachability costs, and actions define weighted hyperedges. Iteratively performing convolutions on this hypergraph until a fixed point is reached allows us to efficiently compute hm on the GPU. Furthermore, it enables batching, so we can compute the heuristic in parallel for multiple states. Our approach naturally supports multiple cost functions, allowing efficient computation of cost partitioning for hm. We demonstrate experimentally that the GPU-based computation of hm can achieve speedups of several orders of magnitude over the traditional computation on a CPU.

Zitieren

APA

Fritzsche, M., Speck, D., Gnad, D., & Ståhlberg, S. (2026). Parallelizing Classical Planning: Critical Path Heuristics on the GPU. Proceedings of the International Symposium on Combinatorial Search, 19(1), 219-223. https://doi.org/10.1609/socs.v19i1.43091

Vancouver

Fritzsche M, Speck D, Gnad D, Ståhlberg S. Parallelizing Classical Planning: Critical Path Heuristics on the GPU. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):219-223. doi:10.1609/socs.v19i1.43091

BibTeX
@article{Fritzsche2026,
  author = {Fritzsche, Markus and Speck, David and Gnad, Daniel and Ståhlberg, Simon},
  title = {Parallelizing Classical Planning: Critical Path Heuristics on the GPU},
  journal = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2026},
  volume = {19},
  number = {1},
  pages = {219--223},
  doi = {10.1609/socs.v19i1.43091}
}
Kostenlos starten →