pcTVI: Parallel MDP Solver Using a Decomposition Into Independent Chains
Abstract
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).
Type
Publication
Proceedings of the International Federation of Classification Societies Conference
Authors
Postdoctoral Researcher in Computer Science
I am currently a postdoctoral researcher in computer science at Université
TÉLUQ, where my research focuses on speeding up the conversion of integer and
floating-point numbers into decimal strings. During my doctoral studies, I
designed algorithms and data structures that leverage modern computer
architectures to solve large instances of Markov decision processes (MDPs). In
my master’s research, I developed routing algorithms for electric vehicles
aimed at determining the optimal path between two points while minimizing
travel time (including driving, charging, and expected waiting time at
charging stations).
Authors
Authors