Sparsification of motion-planning roadmaps by edge contraction
Published
Journal Article
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%. © 2013 IEEE.
Full Text
Duke Authors
Cited Authors
- Shaharabani, D; Salzman, O; Agarwal, PK; Halperin, D
Published Date
- November 14, 2013
Published In
Start / End Page
- 4098 - 4105
International Standard Serial Number (ISSN)
- 1050-4729
Digital Object Identifier (DOI)
- 10.1109/ICRA.2013.6631155
Citation Source
- Scopus