Learning an Optimal Sampling Distribution for Efficient Motion Planning

Sampling-based motion planners (SBMP) are commonly used to generate motion plans by incrementally constructing a search tree through a robot's configuration space. For high degree-of-freedom systems, sampling is often done in a lower-dimensional space, with a steering function responsible for local planning in the higher-dimensional configuration space. However, for highly-redundant systems with complex kinematics, this approach is problematic due to the high computational cost of evaluating the steering function, especially in cluttered environments. Therefore, having an efficient, informed sampler becomes critical to online robot operation. In this study, we develop a learning-based approach with policy improvement to compute an optimal sampling distribution for use in SBMPs. Motivated by the challenge of whole-body planning for a 31 degree-of-freedom mobile robot built by the Toyota Research Institute, we combine our learning-based approach with classical graph-search to obtain a constrained sampling distribution. Over multiple learning iterations, the algorithm learns a probability distribution weighting areas of low-cost and high probability of success, which a graph search algorithm then uses to obtain an optimal sampling distribution for the robot. On challenging motion planning tasks for the robot, we observe significant computational speed-up, fewer edge evaluations, and more efficient paths with minimal computational overhead. We show the efficacy of our approach with a number of experiments in whole-body motion planning.

Authors

• Richard Cheng
• Krishna Shankar
• Joel W. Burdick

Keywords

• Kinematics
• Manipulators
• Probability distribution
• Planning
• Computational efficiency
• Mobile robots
• Task analysis
• Sample Distribution
• Path Planning
• Optimal Sample
• Optimal Distribution
• Optimal Sampling Distribution
• Low-dimensional Space
• Mobile Robot
• Tree Search
• Policy Improvement
• High Probability Of Success
• Neural Network
• Computation Time
• Cost Function
• Feature Maps
• Search Space
• Local Optimum
• Regions Of Space
• Quadratic Programming
• Cartesian Space
• Robot Motion
• Successful Path
• Random Environment
• End-effector Position
• Occupancy Grid
• Valid Path
• Search Speed
• Continuous Domain
• Robot State
• Approaches Infinity
• High Redundancy