Speeding up Planning in Multiagent Settings Using CPU-GPU Architectures

Planning under uncertainty in multiagent settings is highly intractable because of history and plan space complexities. Probabilistic graphical models exploit the structure of the problem domain to mitigate the computational burden. In this article, we introduce the first parallelization of planning in multiagent settings on a CPU-GPU heterogeneous system. In particular, we focus on the algorithm for exactly solving interactive dynamic influence diagrams, which is a recognized graphical models for multiagent planning. Beyond parallelizing the standard Bayesian inference and the computation of decisions’ expected utilities, we also solve the other agents behavioral models in a parallel manner. The GPU-based approach provides significant speedup on two benchmark problems.