改进RRT*算法，用椭球和凸包近似最优路径搜索区域，提速收敛。
Asymptotically Optimal Path Planning With an Approximation of the Omniscient Set
- 用超椭球和凸包近似最优路径候选区域
- 在3D与6D空间中收敛速度显著提升
- 适用于高维空间的渐近最优路径规划
渐近最优的快速探索随机树（RRT*）常用于高维配置空间中的最优路径规划。其主要问题是收敛速度慢。一种解决方案是仅从已知能改善路径代价的配置子集（全知集）中采样。本文提出两种方法近似全知集并实现高效采样：第一种利用当前最优解的若干小超椭球逼近全知集；第二种通过当前解计算凸包来近似。两种方法均保证渐近最优性，适用于一般n维配置空间。实验表明，在3D和6D配置空间的多种场景下，所提方法性能优于传统RRT*。
原文摘要 · Abstract (English)
The asymptotically optimal version of Rapidly-exploring Random Tree (RRT*) is often used to find optimal paths in a high-dimensional configuration space. The well-known issue of RRT* is its slow convergence towards the optimal solution. A possible solution is to draw random samples only from a subset of the configuration space that is known to contain configurations that can improve the cost of the path (omniscient set). A fast convergence rate may be achieved by approximating the omniscient with a low-volume set. In this letter, we propose new methods to approximate the omniscient set and methods for their effective sampling. First, we propose to approximate the omniscient set using several (small) hyperellipsoids defined by sections of the current best solution. The second approach approximates the omniscient set by a convex hull computed from the current solution. Both approaches ensure asymptotical optimality and work in a general n-dimensional configuration space. The experiments have shown superior performance of our approaches in multiple scenarios in 3D and 6D configuration spaces.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。