An efficient retraction-based RRT planner

We present a novel optimization-based retraction algorithm to improve the performance of sample-based planners in narrow passages for 3D rigid robots. The retraction step is formulated as an optimization problem using an appropriate distance metric in the configuration space. Our algorithm computes samples near the boundary of C-obstacle using local contact analysis and uses those samples to improve the performance of RRT planners in narrow passages. We analyze the performance of our planner using Voronoi diagrams and show that the tree can grow closely towards any randomly generated sample. Our algorithm is general and applicable to all polygonal models. In practice, we observe significant speedups over prior RRT planners on challenging scenarios with narrow passages.

Authors

• Liangjun Zhang
• Dinesh Manocha

Keywords

• Orbital robotics
• Performance analysis
• Iterative algorithms
• Algorithm design and analysis
• Robotics and automation
• USA Councils
• Computer science
• Path planning
• Degradation
• Sampling methods
• Rapidly-exploring Random Tree
• Configuration Space
• Voronoi Diagram
• Local Contact
• Optimization-based Algorithm
• Rigid Robots
• Benchmark
• Running Time
• Urban Planning
• Free Space
• Random Method
• Penetration Depth
• Tree Nodes
• Iterative Optimization
• Closest Point
• Constrained Optimization Problem
• Types Of Nodes
• Collision Detection
• Rotated Component
• Collision-free Path
• Planning Algorithm
• Nearest Node
• Scenario Planning