Parallelizing Classical Planning: Critical Path Heuristics on the GPU

Proceedings of the International Symposium on Combinatorial Search, vol. 19, pp. 219–223

Abstract

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.

Authors 4

1. Markus Fritzsche

   Linköping University

   Affiliation as printed

   Linköping University

2. David Speck

   University of Basel

   Affiliation as printed

   University of Basel

3. Daniel Gnad

   Linköping University · Heidelberg University

   Affiliation as printed

   Heidelberg University Linköping University

4. Simon Ståhlberg Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University