/Motion Planning via Manifold Samples

Motion Planning via Manifold Samples

Oren Salzman, Michael Hemmer, Barak Raveh and Dan Halperin
Conference Paper, European Symposium on Algorithms (ESA), pp. 493-505, September, 2011

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.


We present a general and modular algorithmic framework for path planning of robots. Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with sampling-based approaches that are appropriate for higher dimensions. We suggest taking samples that are entire low-dimensional manifolds of the configuration space. These samples capture the connectivity of the configuration space much better than isolated point samples. Geometric algorithms then provide powerful primitive operations for complete analysis of the low-dimensional manifolds. We have implemented our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles. To this end, we have developed a primitive operation for the analysis of an appropriate set of manifolds using arrangements of curves of rational functions. This modular integration of several carefully engineered components has lead to a significant speedup over the PRM sampling-based algorithm, which represents an approach that is prevalent in practice.

BibTeX Reference
author = {Oren Salzman and Michael Hemmer and Barak Raveh and Dan Halperin},
title = {Motion Planning via Manifold Samples},
booktitle = {European Symposium on Algorithms (ESA)},
year = {2011},
month = {September},
pages = {493-505},