A Parallel Solver for Markov Decision Process in Crowd Simulations

Sergio Ruiz, Benjamin Hernandez
Computer Sciences Department Tecnologico de Monterrey, CCM, Mexico City, Mexico
14th Mexican International Conference on Artificial Intelligence (MICAI 2015), 2015


   title={A Parallel Solver for Markov Decision Process in Crowd Simulations},

   author={Ruiz, Sergio and Hernandez, Benjamin},



Download Download (PDF)   View View   Source Source   



Classic path finding algorithms are not adequate in real world path planning, where environment information is incomplete or dynamic and Markov Decision Processes have been used as an alternative. The problem with the MDP formalism is that its state space grows exponentially with the number of domain variables, and its inference methods grow with the number of available actions. To overcome this issue, we formula tea MDP solver in terms of matrix multiplications, based on the Value Iteration algorithm; thus we can take advantage of the graphic processor units (GPUs) to produce interactively obstacle-free paths in the form of an Optimal Policy. We also propose a hexagonal grid navigation space, that reduces the cardinality of the MDP state set. We present a performance analysis of our technique using embedded systems, desktop CPU and GPUs and its application in crowd simulation. Our GPU algorithm presents 90x speed up in desktop platforms, and 30x speed up in embedded systems in contrast with its CPU multi-threaded version.
Rating: 2.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: