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