Cache-Efficient Memory Representation of Markov Decision Processes
Abstract
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
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