Hierarchical dynamic programming for robot path planning

This paper addresses the question how robot planning (e.g. for navigation) can be done with hierarchical maps. We present an algorithm for hierarchical path planning for stochastic tasks, based on Markov decision processes (MDPs) and dynamic programming. It is more efficient than standard dynamic programming for "flat" MDPs, because it reduces the state space for all levels in its hierarchy and it allows reuse of previously computed partial policies. This computational advantage comes at the cost of some extra memory and overhead to represent and coordinate the hierarchical system, and in some cases somewhat longer paths to target locations. We demonstrate the method on artificially generated MDP data, and on real robot data from our vision-controlled robot navigating in an office environment.