Motion Planning via Manifold Samples
Motion Planning via Manifold Samples
复制标题
DOI：
10.1007/s00453-012-9736-1
复制
发表时间：
2013-12-01
期刊：
影响因子：
1.1
通讯作者：
Halperin, Dan
中科院分区：
文献类型：
--
作者：
Salzman, Oren;Hemmer, Michael;Halperin, Dan
我们提出了一种通用的模块化算法框架，用于机器人的路径规划。我们的框架将用于对低维构型空间进行精确和完整分析的几何方法，与适用于高维情况的实用且相当简单的基于采样的方法相结合。为了促进先进几何算法在实际中的应用，我们建议采用构型空间的整个低维流形作为样本，这种样本比孤立的点样本能更好地捕捉构型空间的连通性。然后，用于分析低维流形的几何算法提供了强大的基本操作。该框架的模块化设计使得每个模块组件能够独立优化。实际上，我们已经开发、实现并优化了一种基本操作，用于对某一组流形进行完整和精确的组合分析，使用了有理函数曲线的排列和泛型编程的概念。这进而使我们能够针对多边形机器人在多边形障碍物之间平移和旋转的具体情况实现我们的框架。我们表明该框架的这个实例是概率完备的。此外，我们证明了几个精心设计的组件的集成，相较于流行的基于PRM采样的算法有显著的加速，基于PRM采样的算法代表了在实践中普遍存在的更为简单的方法。
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.