<title>Approaches to macro decompositions of large Markov decision process planning problems</title>

摘要

Mobile robot navigation tasks are subject to motion stochasticity arising from the robot's local controllers, which casts the navigational task into a Markov decision process framework. The MDP may, however, be intractably large; in this work we consider the prioritized package delivery problem which yields an exponentially large state space. We demonstrate that the bulk of this state space is tied to a sub-problem that is an instance of the traveling salesdroid problem and that exponential improvements in solution time for the MDP can be achieved by addressing the TSP sub-problem separately. This process produces a suboptimal solution, but we show that the degree of suboptimality can be controlled by employing more effective TSP approximators. The key contribution is the demonstration that MDP solution techniques can substantially benefit from careful application of well-understood deterministic optimization techniques.