Learning Sequences of Approximations for Hierarchical Motion Planning

The process of designing hierarchical motion planners typically involves problem-specific intuition and implementations. This process is sub-optimal both in terms of solution space (amount of possibilities for search-space approximations, choice of planner parameters, etc) and amount of human labour. In this paper we show that the design of hierarchical motion planners does not have to be manual. We present a method for parameterizing and then optimizing sequences of problem approximations used in hierarchical motion planning. We define these as a specific kind of graph with intermediate state-spaces and solutions as nodes, and costs and planner parameters as edge properties. These properties become a continuous optimization variable that changes the sequence and parameters of sub-planners in the hierarchy. Using Pareto-front estimation, our method automatically discovers multiple designs of optimal computation-time/motion-cost trade-offs. We evaluate the method on a set of legged robot motion planning problems where hand-designed hierarchies are abundant. Our method discovers sequences of problem approximations which achieve similar—though slightly higher—performance than the best human-designed hierarchies. The performance gain significantly increases on new problems, yielding 12x faster computation times and 10% higher success rates.