期刊
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH
卷 35, 期 7, 页码 767-796出版社
SAGE PUBLICATIONS LTD
DOI: 10.1177/0278364915625345
关键词
Sampling-based motion planning; collision checking; safety certificate; robotics; autonomous systems
类别
资金
- Office of Naval Research (MURI) [N00014-09-1-1051]
- Army Research Office (MURI) [W911NF-11-1-0046]
- Air Force Office of Scientific Research [FA-8650-07-2-3744]
- National Science Foundation [IIP-1161029]
- Control Science Center of Excellence at the Air Force Research Laboratory (AFRL)
- AFRL
Collision checking is considered to be the most expensive computational bottleneck in sampling-based motion planning algorithms. We introduce a simple procedure that theoretically eliminates this bottleneck and significantly reduces collision-checking time in practice in several test scenarios. Whenever a point is collision checked in the normal (expensive) way, we store a lower bound on that point's distance to the nearest obstacle. The latter is called a safety certificate and defines a region of the search space that is guaranteed to be collision-free. New points may forgo collision checking whenever they are located within a safety certificate of an old point. Testing the latter condition is accomplished during the nearest-neighbor search that is already part of most sampling-based motion planning algorithms. As more and more points are sampled, safety certificates asymptotically cover the search space and the amortized complexity of (normal, expensive) collision checking becomes negligible with respect to the overall runtime of sampling-based motion planning algorithms. Indeed, the expected fraction of points requiring a normal collision check approaches zero, in the limit, as the total number of points approaches infinity. A number of extensions to the basic idea are presented. Experiments with a number of proof-of-concept implementations demonstrate that using safety certificates can improve the performance of sampling-based motion planning algorithms in practice.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据