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.
VN:F [1.9.22_1171]
Rating: 5.0/5 (1 vote cast)
A Parallel Solver for Markov Decision Process in Crowd Simulations, 5.0 out of 5 based on 1 rating

* * *

* * *

TwitterAPIExchange Object
    [oauth_access_token:TwitterAPIExchange:private] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
    [oauth_access_token_secret:TwitterAPIExchange:private] => o29ji3VLVmB6jASMqY8G7QZDCrdFmoTvCDNNUlb7s
    [consumer_key:TwitterAPIExchange:private] => TdQb63pho0ak9VevwMWpEgXAE
    [consumer_secret:TwitterAPIExchange:private] => Uq4rWz7nUnH1y6ab6uQ9xMk0KLcDrmckneEMdlq6G5E0jlQCFx
    [postfields:TwitterAPIExchange:private] => 
    [getfield:TwitterAPIExchange:private] => ?cursor=-1&screen_name=hgpu&skip_status=true&include_user_entities=false
    [oauth:protected] => Array
            [oauth_consumer_key] => TdQb63pho0ak9VevwMWpEgXAE
            [oauth_nonce] => 1477587261
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1477587261
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => cfgeqnHcI6Fwek9jB7Az3r0JFhs=

    [url] => https://api.twitter.com/1.1/users/show.json
Follow us on Facebook
Follow us on Twitter

HGPU group

2036 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: