pcTVI: Parallel MDP Solver Using a Decomposition Into Independent Chains


Markov Decision Processes (MDPs) are useful to solve real-world probabilistic planning problems. However, finding an optimal solution in an MDP can take an unreasonable amount of time when the number of states in the MDP is large. In this paper, we present a way to decompose an MDP into Strongly Connected Components (SCCs) and to find dependency chains for these SCCs. We then propose a variant of the Topological Value Iteration (TVI) algorithm, called parallel chained TVI (pcTVI), which is able to solve independent chains of SCCs in parallel leveraging modern multicore computer architectures. The performance of our algorithm was measured by comparing it to the baseline TVI algorithm on a new probabilistic planning domain introduced in this study. Our pcTVI algorithm led to a speedup factor of 20, compared to traditional TVI (on a computer having 32 cores).

Proceedings of the International Federation of Classification Societies Conference
Jaël Champagne Gareau
Jaël Champagne Gareau
Doctorant en informatique

Mes intérêts de recherche incluent l’intelligence artificielle, les structures de données, les algorithmes et le programmation haute-performance.