pcTVI: Parallel MDP Solver Using a Decomposition Into Independent Chains
mardi, 19 juil. 2022·
,,
Jaël Champagne Gareau
Éric Beaudry
Vladimir Makarenkov
Résumé
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
Auteurs
Chercheur postdoctoral en informatique
Je suis actuellement chercheur postdoctoral en informatique à l’Université
TÉLUQ, où mes travaux portent sur l’accélération de la conversion de nombres
entiers et flottants en chaînes de caractères décimales. Au cours de mon
doctorat, j’ai conçu des algorithmes et des structures de données exploitant
l’architecture moderne des ordinateurs afin de résoudre de grandes instances
de processus décisionnels de Markov (MDP). Durant ma maîtrise, j’ai développé
des algorithmes de planification d’itinéraires pour véhicules électriques,
visant à déterminer le chemin optimal entre deux points tout en minimisant
le temps total du trajet (déplacement, recharge et attente aux bornes).
Auteurs
Auteurs