Cache-Efficient Memory Representation of Markov Decision Processes
lundi, 30 mai 2022·
,,
Jaël Champagne Gareau
Éric Beaudry
Vladimir Makarenkov
Résumé
Research in automated planning typically focuses on the development of new or
improved algorithms. Yet, an equally important but often overlooked topic is
that of how to actually implement these algorithms efficiently. In this study,
we are making an attempt to close this gap in the context of optimal Markov
Decision Process (MDP) planning. Precisely, we present a novel cache-efficient
memory representation of MDPs, which we call CSR-MDP, that takes advantage of
low-level hardware features such as memory hierarchy. We evaluate the speed
improvement provided by our memory representation by comparing the performance
of CSR-MDP with the performance obtained by traditional MDP representation. We
show that by using our CSR-MDP memory representation, existing MDP solvers,
including VI, LRTDP and TVI, are able to find an optimal policy an order of
magnitude faster.
Type
Publication
Proceedings of the Canadian Conference on Artificial Intelligence
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