A Little More, a Lot Better: Improving Path Quality by a Path-Merging Algorithm
- 13 January 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 27 (2), 365-371
- https://doi.org/10.1109/tro.2010.2098622
Abstract
Sampling-based motion planners are an effective means to generate collision-free motion paths. However, the quality of these motion paths (with respect to quality measures, such as path length, clearance, smoothness, or energy) is often notoriously low, especially in high-dimensional configuration spaces. We introduce a simple algorithm to merge an arbitrary number of input motion paths into a hybrid output path of superior quality, for a broad and general formulation of path quality. Our approach is based on the observation that the quality of certain subpaths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed to compare and cluster multiple motion paths, reduces the running time of the merging algorithm significantly. We tested our algorithm in motion-planning problems with up to 12 degrees of freedom (DOFs), where our method is shown to be particularly effective. We show that our algorithm is able to merge a handful of input paths produced by several different motion planners to produce output paths of much higher quality.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Generation, Comparison, and Merging of Pathways between Protein Conformations: Gating in K-ChannelsBiophysical Journal, 2008
- Creating High-quality Paths for Motion PlanningThe International Journal of Robotics Research, 2007
- OOPS for Motion Planning: An Online, Open-source, Programming SystemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- The visibility–Voronoi complex and its applicationsComputational Geometry, 2006
- Shortest Paths and NetworksPublished by Taylor & Francis ,2004
- Effective sampling and distance metrics for 3D rigid body path planningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Choosing good distance metrics and local planners for probabilistic roadmap methodsIEEE Transactions on Robotics and Automation, 2000
- An Optimal Algorithm for Euclidean Shortest Paths in the PlaneSIAM Journal on Computing, 1999
- Smooth invariant interpolation of rotationsACM Transactions on Graphics, 1997
- A note on two problems in connexion with graphsNumerische Mathematik, 1959