Efficient dynamic programming for high-dimensional, optimal motion planning by spectral learning of approximate value function symmetries
Paul Vernaza, Daniel D. Lee · 2011
We demonstrate how to find high-quality motion plans for high-dimensional holonomic systems efficiently using dynamic programming in a learned subspace of vastly reduced dimension. Our approach (SLASHDP) learns the low dimensional cost structure of an optimal control problem via an efficient spectral method. This structure results in a symmetric value function that serves as a an efficiently-computable surrogate for the true value function. High-quality feedback motion plans can then be obtained from the symmetric value function. Experimental results show that SLASHDP yields higher-quality plans than can be obtained by post-processing plans generated by a sampling-based motion planner, and with less computational effort for very high-dimensional problems. We demonstrate high-quality dynamic programming plans for an arm planning problem of up to 144 dimensions without using any domain-specific knowledge aside from that learned automatically by SLASHDP. Positive results are also shown for a high-dimensional deformable robot planning problem.