Home/Sparsification of motion-planning roadmaps by edge contraction

Sparsification of motion-planning roadmaps by edge contraction

Doron Shaharabani, Oren Salzman, Pankaj K. Agarwal and Dan Halperin
Carnegie Mellon University, IEEE International Conference on Robotics and Automation (ICRA), pp. 4098-4105, January, 2013

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.

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

BibTeX Reference
@conference{Shaharabani-2013-7664,
title = {Sparsification of motion-planning roadmaps by edge contraction},
author = {Doron Shaharabani and Oren Salzman and Pankaj K. Agarwal and Dan Halperin},
booktitle = {IEEE International Conference on Robotics and Automation (ICRA)},
school = {Robotics Institute , Carnegie Mellon University},
month = {January},
year = {2013},
pages = {4098-4105},
address = {Pittsburgh, PA},
}
2017-09-13T10:39:32+00:00