Sampling-based algorithms for optimal motion planning
Sampling-based algorithms for optimal motion planning
复制标题
DOI：
10.1177/0278364911406761
复制
发表时间：
2011-06-01
影响因子：
9.2
通讯作者：
Frazzoli, Emilio
中科院分区：
文献类型：
--
作者：
Karaman, Sertac;Frazzoli, Emilio
在过去的十年中，基于采样的路径规划算法，如概率路线图（PRM）和快速探索随机树（RRT），已被证明在实践中工作良好，并具有理论保证，如概率完整性。然而，很少有人致力于正式分析的质量的解决方案返回这样的算法，e。G.作为样本数量的函数。本文的目的是填补这一空白，通过严格分析的渐近行为的解决方案的成本返回随机抽样为基础的算法作为样本的数量增加。提供了一些负面的结果，现有的算法，e。G.表明，在温和的技术条件下，广泛使用的基于采样的算法返回的解决方案的成本几乎肯定收敛到一个非最优值。本文的主要贡献是引入了新的算法，即PRM* 和RRT*，这是可证明的渐近最优的，即这样的返回的解决方案的成本几乎肯定收敛到最优。此外，它表明，新算法的计算复杂性是在一个常数因子的概率完全（但不是渐近最优）的同行。本文的分析基于随机采样路径规划算法和随机几何图理论之间的新联系。
During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e. g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e. g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.