Sparsification of motion-planning roadmaps by edge contraction

Journal Article (Journal Article)

Roadmaps constructed by the recently introduced PRM∗ algorithm for asymptotically-optimal motion planning encode high-quality paths yet can be extremely dense. We consider the problem of sparsifying the roadmap, i.e. reducing its size, while minimizing the degradation of the quality of paths that can be extracted from the resulting roadmap. We present a simple, effective sparsifying algorithm, called roadmap sparsificationby edgecontraction (RSEC). The primitive operation used by RSEC is edgecontraction - the contraction of a roadmap edge (v',v'') to a new vertex v' and the connection of the new vertex v to the neighboring vertices of the contracted edge's vertices (i.e. to all neighbors of v' and v'). For certain scenarios, we compress more than 97% of the edges and vertices of a given roadmap at the cost of degradation of average shortest path length by at most 4%.

Full Text

Duke Authors

Cited Authors

  • Salzman, O; Shaharabani, D; Agarwal, PK; Halperin, D

Published Date

  • January 1, 2014

Published In

Volume / Issue

  • 33 / 14

Start / End Page

  • 1711 - 1725

Electronic International Standard Serial Number (EISSN)

  • 1741-3176

International Standard Serial Number (ISSN)

  • 0278-3649

Digital Object Identifier (DOI)

  • 10.1177/0278364914556517

Citation Source

  • Scopus