Home/On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages

On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages

Oren Salzman, Michael Hemmer and Dan Halperin
Carnegie Mellon University, IEEE Trans. Automation Science and Engineering (TASE), Vol. 12, No. 2, pp. 529-538, April, 2015

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 extend our study of Motion Planning via Manifold Samples (MMS), a general algorithmic framework that combines geometric methods for the exact and complete analysis of low-dimensional configuration spaces with sampling-based approaches that are appropriate for higher dimensions. The framework explores the configuration space by taking samples that are low-dimensional manifolds of the configuration space capturing its connectivity much better than isolated point samples. The scheme is particularly suitable for applications in manufacturing, such as assembly planning, where typically motion planning needs to be carried out in very tight quarters. The contributions of this paper are as follows: (i) We present a recursive application of MMS in a six-dimensional configuration space, enabling the coordination of two polygonal robots translating and rotating amidst polygonal obstacles. In the adduced experiments for the more demanding test cases MMS clearly outperforms Probabilistic Roadmaps (PRM), with over 40-fold speedup in a six-dimensional coordination-tight setting. (ii) A probabilistic completeness proof for the case of MMS with samples that are affine subspaces. (iii) A closer examination of the test cases reveals that MMS has, in comparison to standard sampling-based algorithms, a significant advantage in scenarios containing high-dimensional narrow passages. This provokes a novel characterization of narrow passages, which attempts to capture their dimensionality, an attribute that had been (to a large extent) unattended in previous definitions.

BibTeX Reference
@conference{Salzman-2015-5938,
title = {On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages},
author = {Oren Salzman and Michael Hemmer and Dan Halperin},
booktitle = {IEEE Trans. Automation Science and Engineering (TASE)},
school = {Robotics Institute , Carnegie Mellon University},
month = {April},
year = {2015},
volume = {12},
number = {2},
pages = {529-538},
address = {Pittsburgh, PA},
}
2017-09-13T10:38:44+00:00