Abstract | ||
---|---|---|
We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction-the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/ICRA.2013.6631155 | Robotics and Automation |
Keywords | DocType | Volume |
graph theory,path planning,RSEC,average shortest path length,compression,graph,motion-planning roadmaps sparsification,neighboring vertices,roadmap sparsification by edge contraction,vertex | Journal | abs/1209.4463 |
ISSN | ISBN | Citations |
1050-4729 | 978-1-4673-5641-1 | 8 |
PageRank | References | Authors |
0.54 | 17 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Doron Shaharabani | 1 | 8 | 0.54 |
Oren Salzman | 2 | 61 | 15.27 |
Pankaj K. Agarwal | 3 | 5257 | 593.81 |
D. Halperin | 4 | 8 | 0.54 |