arrow
返回

Sampling-based algorithms for optimal motion planning

delete2011-06-22
delete3.5K
delete
OA
AI
S
Sertaç Karaman *
E
Emilio Frazzoli
DOI:10.1177/0278364911406761delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
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.
Keyword:
Motion planning
optimal path planning
sampling-based algorithms
random geometric graphs
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

International Journal of Robotics Research 封面图
International Journal of Robotics Research
IF:
5
论文数:
2.4K
被引数:
1.9W

机构

暂无机构信息
引用论文

引用论文

Real-Time Motion Planning With Applications to Autonomous Urban Driving实时运动规划及其在自动城市驾驶中的应用
err2009-09-01
err734
errOAAI
errKuwata, Yoshiaki; Teo, Justin; Fiore, Gaston; Karaman, Sertac; Frazzoli, Emilio; How, Jonathan P.
err分享
err收藏
err分享
err收藏
Anytime search in dynamic graphs动态图中的随时搜索
err2008-09-01
err187
errOAAI
errLikhachev, Maxim; Ferguson, Dave; Gordon, Geoff; Stentz, Anthony; Thrun, Sebastian
err分享
err收藏
学者 查看更多内容