基于双向区域扩展引导的采样RRT*：实现高稳定性和超高规划效率

传统RRT算法存在路径成本高、收敛慢的问题，本文提出BR-RRT*方法通过双向区域扩展和采样指导策略优化路径质量与规划效率，在四类典型环境中路径长度减少14.2%-25.4%，规划时间缩短86.1%-99.4%，成功率达100%。

杨建兴|何魁杰|吴家豪|阮华汉|蔡思培|张勇

华侨大学机械工程与自动化学院，中国厦门361021

摘要

在各种路径规划方法中，基于采样的算法，特别是快速探索随机树（RRT），由于其强大的适应性，在移动机器人领域得到了广泛应用。然而，传统的RRT存在一些局限性，包括较高的路径成本和收敛速度慢的问题，这主要是由于搜索空间过大以及采样过程缺乏指导。为了解决这些问题，本文提出了一种双向区域扩展引导的基于采样的RRT*（BR-RRT*）方法。该方法在优化采样区域的同时确保了空间连通性，从而有效地提高了路径搜索效率和采样质量。此外，通过采用自适应步长策略和双层路径优化策略，该方法能够更好地处理狭窄通道，并加快了在这些受限环境中的规划速度。在四个代表性环境（简单环境、混乱环境、狭窄环境和迷宫环境）中进行了对比实验，结果表明BR-RRT*的性能优于几种先进的RRT变体。具体而言，与RRT*相比，该算法在四个环境中的路径长度分别缩短了25.4%、17.5%、20.7%和14.2%，规划时间分别减少了86.1%、87.9%、99.4%和97.6%。值得注意的是，BR-RRT*在所有测试环境中的成功率均为100%，而RRT*在狭窄环境和迷宫环境中的成功率分别为36%和77%。这些结果共同证明了所提算法在路径质量、规划效率和环境适应性方面的优势。

部分内容摘录

问题定义

本研究主要关注基于RRT的算法中采样区域大小的问题。工作空间定义为$X\subseteq R^2$，其中$X_{\mathrm{obs}}$表示障碍物集合，自由空间由$X_{\mathrm{free}}$表示。拓扑闭包$X_{\mathrm{cl}}(X\setminus X_{\mathrm{obs}})$确保边界点被包含在内，以避免路径规划中的数值问题。本研究的核心目标是通过区域扩展构建一个优化的采样区域，使得采样节点能够有效地覆盖整个自由空间，从而提高路径规划和算法的适应性。

相关算法

本文提出的BR-RRT*算法主要基于RRT-Connect框架。下面将对RRT算法和RRT-Connect算法进行简要介绍。

RRT算法通过构建一棵随机探索树来高效地探索自由空间。其核心过程从起点开始迭代$q_{\mathrm{start}}$。在每次迭代中，会随机选取一个样本点$q_{\mathrm{rand}}$，并确定当前树中该样本点的最近邻居节点。然后生成一个新的节点$q_{\mathrm{new}}$

双向区域扩展

如图2(a)所示，首先建立一个坐标系$O-xy$，并将环境离散化为网格表示（用浅灰色线条表示）。网格的大小根据移动对象（如机器人或车辆）的物理尺寸来确定。包含起点S和终点G的网格分别称为起始网格和目标网格，如图2(a)中的浅蓝色和浅绿色部分所示。

采样

在双向区域扩展的基础上，BR-RRT*算法进一步优化了采样过程。该算法提出了一种采样引导策略，将样本点限制在无障碍物的连通区域内。获取样本节点后，应用自适应步长策略对这些点进行处理并生成树节点，这些节点用于构建起始树和目标树。一旦确定了可行路径，

CRediT作者贡献声明

杨建兴：概念设计、方法论、形式分析、软件开发、监督、审稿与编辑、初稿撰写、资金筹集。何魁杰：概念设计、数据收集、软件开发、验证、可视化、初稿撰写。吴家豪：数据整理、形式分析、软件开发、验证。阮华汉：软件开发、验证、可视化。蔡思培：形式分析、审稿与编辑。张勇：监督、审稿与编辑。

利益冲突声明

作者声明没有已知的财务利益或个人关系可能影响本文的研究结果。

致谢

本研究得到了厦门自然科学基金（资助编号：3502Z202571032）和华侨大学科研经费（资助编号：20241XD035）的支持。