提出RRT-Rope方法，10秒内生成高效路径，适合无人机在大型矿洞快速导航。
RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments
- 用改进的RRT-connect快速生成可行路径，再通过确定性缩短加速优化。
- 路径成本更低，计算速度比同类算法快70%，在典型矿洞环境中表现最优。
- 适合需要实时路径规划的无人机、无人车等移动机器人应用。
针对大型无遮挡3D环境（如无人机探测的地下矿洞）中的路径规划问题，现有许多算法存在路径代价高、计算耗时长的问题。虽然快速探索随机树（RRT）算法因概率完备性和快速找到可行路径而广受欢迎，但其变体（如Informed RRT*、RRT#）在大环境下收敛缓慢。已有研究表明路径缩短技术优于传统RRT变体。本文提出一种新方法RRT-Rope，通过改进的RRT-connect快速生成初始路径，并利用树分支中已添加的中间节点，采用确定性缩短策略进行高效后处理，显著提升求解速度。实验表明，RRT-Rope在所有仿真环境中均优于主流RRT变体与缩短技术，在代表性矿洞场景中比次优算法快70%以上，同时获得更优路径成本。
原文摘要 · Abstract (English)
Many path planning algorithms have been introduced so far, but most are costly, in path cost and in processing time, in large-scale uncluttered 3D environments such as underground mining stopes explored by an unmanned aerial vehicle (UAV). Rapidly-exploring Random Tree (RRT) algorithms are popular because of their probabilistic completeness and rapidity in finding a feasible path in single-query problems. Many of the algorithms (e.g. Informed RRT*, RRT#) developed to improve RRT need considerable time to converge in large environments. Shortcutting an RRT is an old idea that has been proven to outperform RRT variants. This paper introduces a new method, RRT-Rope, that aims at finding a near-optimal solution in a drastically shorter amount of time. The proposed approach benefits from fast computation of a feasible path with an altered version of RRT-connect, and post-processes it quickly with a deterministic shortcutting technique, taking advantage of intermediate nodes added to each branch of the tree. This paper presents simulations and statistics carried out to show the efficiency of RRT-Rope, which gives better results in terms of path cost and computation time than other popular RRT variations and shortening techniques in all our simulation environments, and is up to 70% faster than the next best algorithm in a representative stope.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。