/Motion Planning via Manifold Samples

Motion Planning via Manifold Samples

Oren Salzman, Michael Hemmer, Barak Raveh and Dan Halperin
Journal Article, Carnegie Mellon University, Algorithmica, Vol. 67, No. 4, pp. 547-565, 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.


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 practical, considerably simpler sampling-based approaches that are appropriate for higher dimensions. In order to facilitate the transfer of advanced geometric algorithms into practical use, we suggest taking samples that are entire low-dimensional manifolds of the configuration space that capture the connectivity of the configuration space much better than isolated point samples. Geometric algorithms for analysis of low-dimensional manifolds then provide powerful primitive operations. The modular design of the framework enables independent optimization of each modular component. Indeed, we have developed, implemented and optimized a primitive operation for complete and exact combinatorial analysis of a certain set of manifolds, using arrangements of curves of rational functions and concepts of generic programming. This in turn enabled us to implement our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles. We show that this instance of the framework is probabilistically complete. Moreover, we demonstrate that the integration of several carefully engineered components leads to significant speedup over the popular PRM sampling-based algorithm, which represents the more simplistic 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},
journal = {Algorithmica},
year = {2013},
month = {January},
volume = {67},
number = {4},
pages = {547-565},