Anytime solution optimization for sampling-based motion planning

Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shortening techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.

Authors

• Ryan Luna
• Ioan Alexandru Sucan
• Mark Moll
• Lydia E. Kavraki

Keywords

• Planning
• Optimization
• Robots
• Heuristic algorithms
• Bridges
• Time factors
• Three-dimensional displays
• Path Planning
• Sampling-based Motion
• Sampling-based Motion Planning
• Solution Path
• Heuristic
• Path Length
• Time Constraints
• Rigid Body
• GB Memory
• Goal State
• Optimal Path
• Homotopy
• Planning Time
• Cubicle
• Pair Of States
• Dynamic Programming Algorithm
• 3rd Quartile
• Post-processing Methods
• Time Budget
• Sampling-based Methods
• Path Segment
• Valid Path
• Improvement In Length