英文题目：Bidirectional region expansion guided sampling-based RRT*: achieving high stability and ultra-high planning efficiency

中文题目： 双向区域扩展引导的采样RRT*：实现高稳定性和超高效规划

作者：Jianxing Yang, Kuijie He, Jiahao Wu, Huahan Ruan, Sipei Cai, Yong Zhang

作者单位： 华侨大学机电及自动化学院

期刊：Expert Systems With Applications（IF 7.5 中科院一区，JCR一区）

发表时间：2026年5月10日

链接：

https://doi.org/10.1016/j.eswa.2026.131326

引文格式：Yang J, He K, Wu J, et al. Bidirectional region expansion guided sampling-based RRT*: achieving high stability and ultra-high planning efficiency[J]. Expert Systems With Applications, 2026, 310: 131326.

RRT（快速探索随机树）系列算法是机器人路径规划的经典方法，优点是不需要对环境建模、适用范围广。但它的老毛病也很明显：随机采样太盲目——在全空间里乱撒点，导致搜索效率低、路径质量不稳定、窄通道还容易卡住。

华侨大学团队这次提出的 BR-RRT*（Bidirectional Region Expansion Guided RRT*）把这个问题解决得挺彻底。核心思路听起来很符合直觉：与其在全空间乱找，不如先找出一个“大概率包含最优路径”的区域，然后只在这个区域里采样。

怎么找这个区域？他们用了一个双向区域扩展的策略：从起点和终点同时出发，一层层向外扩展出一个个矩形的“通行区域”，直到两个方向的区域相遇。这个过程中，区域之间有明确的父子关系，形成了一个树状结构。然后采样时，根据当前节点所在的区域，引导采样方向——70%的概率往子区域或父区域走，30%的概率在全区域随机采样，保持探索性。

结果很惊人：在窄通道地图上，RRT*平均要花28.66秒才能找到路径，BR-RRT*只用了0.17秒，时间缩短了99.4%；在迷宫里，RRT*成功率只有77%，BR-RRT*是100%。路径长度也普遍缩短了14%到25%。

核心亮点：

✅区域预构：双向扩展出无障碍连通区域，把采样空间压缩到1%以下

✅引导采样：利用区域间的父子关系指导采样方向，避免盲目探索

✅超高效率：窄通道地图规划时间从28秒降到0.17秒（-99.4%）

✅100%成功率：在窄通道和迷宫里，100次试验全部成功

✅高稳定性：路径长度波动极小，重复使用可靠

✅实车验证：在真实环境中成功导航

🧩问题：RRT的随机采样有多盲目？

RRT的基本流程很简单：随机撒点q，找树上最近的点q，朝q方向走一步生成q，如果路径没撞墙就加入树。重复直到树碰到终点。

这个“随机撒点”是问题所在——它在整个自由空间里均匀采样，而真正有用的区域可能只占1%。剩下的99%的采样都在做无用功，导致：

- 收敛慢（尤其窄通道）

- 路径质量不稳定（每次结果不一样）

- 容易被困在局部

🧠核心思想：先找路，再走路

BR-RRT*的思路很直接：不着急采样，先找出一个“无障碍连通区域”，保证这个区域连接起点和终点，然后只在这个区域里采样。

这个区域怎么找？他们用了一个双向区域扩展的策略：

Figure 1：双向区域扩展和简化过程

图2a-h一步步展示了这个过程：

- Step 1（图1a）：把环境栅格化，起点S和终点G所在的格子分别标为浅蓝和浅绿。

- Step 2（图1b）：从这两个格子开始，沿X轴正负方向一层层扩展，直到碰到障碍或边界，得到“引导区域”（虚线）。

- Step 3（图1c）：沿Y轴同样扩展，得到四个边界，围成一个矩形——这是第0代主区域。

- Step 4（图1d-e）：继续向外扩展，得到第1代、第2代主区域，并用类似族谱的方式命名（如PRS.0.0、PRG.0.1），记录下父子关系。

- Step 5（图1f）：一旦某个起点侧区域和终点侧区域重叠，就找到了一个“重叠主区域”OPR。

- Step 6（图1g-h）：选择离起点-终点连线最近的那个OPR，用它连接两侧区域，然后回溯父区域，最后得到完整的无障碍连通区域（图2h中的浅黄色区域）。

这个过程有几个关键点：

1.  严格无障碍：每次扩展只取没有障碍的格子

2.  连通性保证：重叠区域确保两侧连通

3.  层次关系：父子区域关系被记录下来，后面采样要用

伪代码：双向区域扩展

🎯 采样引导：利用区域关系指导生长

有了这个连通区域，采样就不是乱撒了。他们设计了一个采样引导策略，用到了前面记录的区域父子关系。

Figure 2：采样逻辑示意图

图2展示了这个逻辑：

- 当前节点在起点侧的第0代区域PRS.0 → 采样点选在它的子区域PRS.0.0（图2b）

- 当前节点在起点侧最深区域PRS.0.0 → 切换到终点侧最深区域PRG.0.1采样（图2c）

- 当前节点在终点侧区域PRG.0.1 → 采样点选在它的父区域PRG.0（图2d）

- 两个树的节点落到同一个区域 → 直接连接（图2f）

为了保留一定的探索性，30%的概率在全连通区域内随机采样。

伪代码：区域引导采样

📏 自适应步长

采样点有了，怎么生成新节点？他们用了自适应步长策略：

- 如果q和q之间没障碍，直接用欧氏距离作为步长，一步到位

- 如果有障碍，根据周围障碍的密集程度动态调整步长

步长计算公式：

其中Os是局部障碍面积占比， O_n是局部障碍数量占比。障碍越密，步长越小，保证安全性。

🧱 三层碰撞检测

为了平衡安全性和计算效率，他们用了三层递进检测：

1. 栅格粗筛（Bresenham算法）：快速判断线段是否经过障碍栅格

2. AABB树中筛：用轴对齐包围盒快速排除明显不相交的障碍

3. 精确几何检测：最后做精确的几何相交判断

✂️路径后处理

找到初始路径后，还有两步优化：

1. 全局贪心剪枝：尝试跳过中间节点，直接连接非相邻节点，前提是线段不撞墙且比原路径短

2. 局部优化：把中间节点向它前后节点连线的垂足方向移动，让路径更平滑

🖥️ 仿真实验

他们在四种地图上做了测试：

- Simple：稀疏障碍

- Messy：随机分布的大小障碍

- Narrow：有三个宽度仅10米（机器人宽5米）的窄通道

- Maze：迷宫，有死胡同和急转弯

Figure 3：四种测试环境地图

图3展示了这四种地图的布局，灰色是障碍，蓝色和绿色矩形是起点和终点。

Table 1：各算法成功率

在窄通道和迷宫里，好几个算法成功率惨不忍睹，BR-RRT*依然是100%。

Table 2：各算法规划时间对比

窄通道地图上，RRT*要28.66秒，BR-RRT*只要0.17秒，快了168倍（时间减少99.4%）。迷宫地图上，RRT*要52.78秒，BR-RRT*只要1.28秒，快了41倍。

Figure 4. 简单地图模拟结果

Figure 5. 凌乱地图模拟结果

Figure 6：窄地图模拟结果

Figure 7：迷宫图模拟结果

图4-7直观展示了各个算法在不同地图上的路径。BR-RRT*的路径更直、转折更少、节点更稀疏。

Table 3：各算法路径长度对比

路径长度上，BR-RRT*也比其他算法短：比RRT*短14%-25%，比RRT-Connect*短13%-23%。

🤖实车实验

最后他们在真实环境里用阿克曼转向的小车做了验证。为了验证所提出的用于移动机器人导航的BR-RRT*算法的实际功效和可靠性，本工作开展了真实世界的实验。如图8所示，移动机器人平台运行在Ubuntu 20.04上，并利用ROS Noetic框架。这种基于ROS的架构提供了对RVIZ等全套软件包的访问，确保高质量环境数据的稳定获取，并为机器人的控制模块提供强大的支持。对于导航，全局规划器是所提出的BR-RRT*算法的简化版本，它保留了核心区域扩展和采样偏差逻辑，并辅以路径平滑步骤。局部规划器采用定时弹性带（TEB）算法。硬件平台为阿克曼转向几何的小型汽车，尺寸为0.28 m × 0.19 m，最大角速度为0.3 rad/s，最大线速度为0.5 m/s。主要计算单元是NVIDIA Jetson Nano 4 GB开发套件。

Figure 8：实验平台

Figure 9：真实环境地图的路径规划

图8是实验平台，图9是两个实景地图：一个窄通道（宽度刚好两倍车宽），一个弯曲路径。小车成功沿着BR-RRT*规划的路径走完全程，无碰撞。

Video S1：实车实验导航全过程

①区域预构，而不是边采边找

大多数RRT改进是在采样过程中加启发式，但采样空间还是整个自由空间。BR-RRT*先花一点时间（在复杂地图上也就零点几秒）把有效区域找出来，然后只在这个区域里采样。这种“先看再走”的思路比“边走边看”效率高得多。

②双向扩展+区域层次关系

双向扩展不新鲜，但把扩展出来的区域按代数建立起父子关系，并用这个关系指导采样，这个想法很妙。它相当于给采样过程加了一个拓扑地图：你知道当前在哪个区，就知道下一步该往哪个区走。

③自适应步长策略

公式里用了局部障碍面积比 (Os) 和数量比 (On) 来动态调整步长，而不是简单地“有障碍就缩步长”。这种更精细的调整保证了在开阔地带大步快跑、在复杂地带小心慢行。

④三层碰撞检测

栅格筛、AABB树、精确几何，三层递进。平时用前两层快速排除，只有真正可能撞的时候才做精确计算。这是工程上的优化，不是理论创新，但对实际运行效率提升很大。

⑤稳定性提升

RRT系列一直有个问题：每次跑出来的路径不一样，长度波动大。BR-RRT*因为采样区域固定，路径长度波动极小（Table 3里窄通道地图上最大最小只差16米，RRT*差了191米）。这对工业应用很关键——你不知道这次规划的路径会不会比上次长50%。

BR-RRT*给人的感觉是：把RRT从“随机搜索”变成了“引导搜索”。它没有改变RRT的树结构，也没有改变渐近最优性，只是加了一个预处理步骤，把采样空间压缩到有效区域，然后在这个区域里用区域关系指导采样。

这个思路的价值在于：它把“找到有效区域”和“在有效区域里找路”两个问题解耦了。前者是拓扑问题，后者是几何问题。拓扑问题用区域扩展解决，几何问题用RRT*解决。各司其职，互不干扰。

未来研究将聚焦于以下几个方向：

🔸高维空间扩展：现在只做了二维，如果扩展到机械臂的C空间或无人机的三维空间，区域扩展的计算量会爆炸。需要用降维投影或分层扩展的方法。

🔸动态环境：如果障碍物移动，之前扩展的区域可能失效。需要做增量式区域更新，只局部更新受影响的部分。

🔸运动学约束：现在的路径是几何的，没考虑车的转弯半径、加速度限制。可以把这些约束加到后处理阶段，或者直接加到规划器里。

🔸栅格分辨率自适应：窄通道里可能需要更细的栅格，开阔地带可以粗一些。动态调整栅格大小可以平衡精度和效率。

🔸与学习方法结合：A*给的初值有时绕远，如果能用学习的方法（比如从历史数据中学习典型路径）直接给一个更好的初值，可以进一步减少迭代次数。

🔸多机协同：如果多台机器人在同一片区域运行，路径规划还要考虑彼此避让。这需要在区域扩展阶段就考虑多机的空间分布。

从仿真到实车，从窄通道到迷宫，BR-RRT*用数据证明了一件事：RRT还能更快，而且可以快两个数量级。

声明：本文仅供学术交流，版权归原作者所有。如有错误或侵权，请联系更正或删除，欢迎留言探讨。