Personal tools
You are here: Home Projects Improving Path Quality by a Simple Path Merging Algorithm
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

Improving Path Quality by a Path Merging Algorithm

— filed under: ,

Hybridization-Graph
rod_becnhmark_B
An improved path (magenta) 
generated from multiple paths
When allocated more running time
the quality of H-Graphs converges to
the optimal (dashed line) whereas
PRM remains in a plateau.
For more experiments and examples,
see Raveh et al. [link].
Wrench Experiments
H-Graphs perform particularly well in high-dimensional settings

Abstract

Sampling-based motion planners are an effective means for generating 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 for merging 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 sub-paths within each solution may be higher than the quality of the entire path. A dynamic-programming algorithm, which we recently developed for comparing and clustering 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. 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.

Links

  • Barak Raveh, Angela Enosh, and Dan Halperin
    A Little More, a Lot Better: Improving Path Quality by a Path Merging Algorithm
    IEEE Transactions on Robotics, 27(2): 365-371, 2011 [link] [bibtex]
    arXiv
    [link]

Contacts

Barak Raveh hompage contact
Angela Enosh hompage contact
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions