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.
Jaël Champagne Gareau
PhD Student in Computer Science
My research interests include AI, data structures, algorithms and HPC.