Nearly Deterministic Abstractions of Markov Decision Processes

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Markov Decision Processes

We examine scaling issues for a restricted class of compactly representable Markov decision process planning problems. For one stochastic mobile robotics package delivery problem it is possible to decouple the stochastic local-navigation problem from the deterministic global-routing one and to solve each with dedicated methods. Careful construction of macro actions allows us to effectively "hide" navigational stochasticity from the global routing problem and to approximate the latter with off-the-shelf combinatorial optimization routines for the traveling salesdroid problem, yielding a net exponential speedup in planning performance. We give analytic conditions on when the macros are close enough to deterministic for the approximation to be good and demonstrate the performance of our method on small and large simulated navigation problems.