Motion Planning via Manifold Samples

Manifold samples used to capture the 3D configuration space
Manifold samples used to capture the 3D configuration space:The left side illustrates two families of manifolds where the decomposed cells are darkly shaded. The right side illustrates their intersection that induces the connections among components.

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.

One Polygonal Robot

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 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. We foresee possible extensions of our framework to solving  high-dimensional problems beyond motion planning.

Scenarios

Flower
Flower

Snake
Snake

Tunnel
Tunnel

Polygonal
Polygonal

Coordinating Two Polygonal Robots

We recursively apply the MMS framework 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 outperforms PRM with over 20-fold speedup in a coordination-tight setting.

Scenarios (files provided in .dae format)

Environment

Robot_a

Robot_b

Theoretical Results

We present a probabilistic completeness proof for the most prevalent case, namely MMS with samples that are affine subspaces. In addition, a subspaces. In addition, a close 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 provoked 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.

Videos & Links

Contacts

Oren Salzman
Dan Halperin
Michael Hemmer
Barak Raveh 
@article{shh-pmsec-12,,
  author       = {Oren Salzman and Michael Hemmer and Dan Halperin},
  title        = {On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages},
  journal      = {CoRR},
  volume       = {abs/1202.5249},
  year         = {2012},
  url          = {http://arxiv.org/abs/1202.5249},
  eprinttype   = {arXiv},
  eprint       = {1202.5249},
  timestamp    = {Mon, 13 Aug 2018 16:46:30 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/abs-1202-5249.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{shh-pmsec-13,
  author = {Oren Salzman and Michael Hemmer, and Dan Halperin},
  editor = {Emilio Frazzoli and Tomas Lozano-Perez and Nicholas Roy and Daniela Rus},
  title = {On the Power of Manifold Samples in Exploring Configuration Spaces and the Dimensionality of Narrow Passages},
  series = {Springer Tracts in Advanced Robotics ({STAR})},
  volume = {86},
  booktitle = {Algorithmic Foundations of Robotics X},
  year = {2013},
  publisher = {Springer},
  pages = {313--329},
}

@masterthesis{s-mpms-11,
  author       = {Oren Salzman},
  title        = {Motion Planning via Manifold Samples},
  type         = {{M}.{S}c. Thesis},
  school       = {The Blavatnik School of Computer Science, Tel-Aviv University},
  year         = {2011}
}

@article{shrh-mpms-11,
  author       = {Oren Salzman and Michael Hemmer and Barak Raveh and Dan Halperin},
  title        = {Motion Planning via Manifold Samples},
  journal      = {CoRR},
  volume       = {abs/1107.0803},
  year         = {2011},
  url          = {http://arxiv.org/abs/1107.0803},
  eprinttype   = {arXiv},
  eprint       = {1107.0803},
  timestamp    = {Mon, 13 Aug 2018 16:45:59 +0200},
  biburl       = {https://dblp.org/rec/journals/corr/abs-1107-0803.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

@inproceedings{shrh-mpms-11,
  author = {Oren Salzman and Michael Hemmer and Barak Raveh and Dan Halperin},
  editor = {Camil Demetrescu and Magn{\'u}s M. Halld{\'o}rsson},
  title = {Motion Planning via Manifold Samples},
  booktitle = {Proceedings of the 19th Annual European Symposium on Algorithms (ESA)},
  series = {Lecture Notes in Computer Science ({LNTCS})},
  volume = {6942},
  year = {2011},
  publisher = {Springer},
  pages = {493--505},
  doi = {10.1007/978-3-642-23719-5_42}
}

@article{shrh-mpms-13,
  year      = {2013},
  journal   = {Algorithmica},
  title     = {Motion Planning via Manifold Samples},
  publisher = {Springer},
  author    = {Oren Salzman and Michael Hemmer and Barak Raveh and Dan Halperin},
  pages     = {1-19}
}

Yair Oz - Webcreator

Contact

Mobile. 052-4703139 | WhatsApp
Email. [email protected]

Skip to content