Nearly deterministic abstractions of Markov decision processes
Terran D.R. Lane, Leslie Pack Kaelbling · 2002
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 prob-lem from the deterministic global-routing one and to solve each with dedicated methods. Careful construction of macro actions allows us to effectively “hide ” navigational stochas-ticity 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 exponen-tial speedup in planning performance. We give analytic con-ditions on when the macros are close enough to deterministic for the approximation to be good and demonstrate the perfor-mance of our method on small and large simulated navigation problems.