Sparsification of motion-planning roadmaps by edge contraction
- 1 May 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4098-4105
- https://doi.org/10.1109/icra.2013.6631155
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%.Keywords
This publication has 23 references indexed in Scilit:
- Towards small asymptotically near-optimal roadmapsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Computing spanners of asymptotically optimal probabilistic roadmapsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Approximate Euclidean Shortest Paths amid Convex ObstaclesPublished by Society for Industrial & Applied Mathematics (SIAM) ,2009
- Creating High-quality Paths for Motion PlanningThe International Journal of Robotics Research, 2007
- Geometric Spanner NetworksPublished by Cambridge University Press (CUP) ,2007
- Determining approximate shortest paths on weighted polyhedral surfacesJournal of the ACM, 2005
- Approximating Shortest Paths on a Nonconvex PolyhedronSIAM Journal on Computing, 2000
- Constructing Approximate Shortest Path Maps in Three DimensionsSIAM Journal on Computing, 1999
- Euclidean spannersPublished by Association for Computing Machinery (ACM) ,1995
- Graph spannersJournal of Graph Theory, 1989