Home/Sparsification of motion-planning roadmaps by edge contraction

Sparsification of motion-planning roadmaps by edge contraction

Oren Salzman, Doron Shaharabani, Pankaj K. Agarwal and Dan Halperin
Conference Paper, Carnegie Mellon University, The International Journal of Robotics Research (IJRR), Vol. 33, No. 14, pp. 1711-1725, November, 2014

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


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%.

BibTeX Reference
title = {Sparsification of motion-planning roadmaps by edge contraction},
author = {Oren Salzman and Doron Shaharabani and Pankaj K. Agarwal and Dan Halperin},
booktitle = {The International Journal of Robotics Research (IJRR)},
school = {Robotics Institute , Carnegie Mellon University},
month = {November},
year = {2014},
volume = {33},
number = {14},
pages = {1711-1725},
address = {Pittsburgh, PA},