《Algorithms》:An Improved Three-Dimensional RRT Path Planning Method Incorporating Path-Aware Whale Optimization
编辑推荐:
研究人员将复杂三维路径规划问题定义为在有限计算时间内生成无碰撞、短且平滑的路径。传统基于快速探索随机树(RRT)的方法常存在无引导采样、密集障碍物区域重复扩展失败、初始路径冗余以及后处理易碰撞等问题。为解决此问题,研究人员提出了一种环境反馈混合采样双向RRT方
研究人员将复杂三维路径规划问题定义为在有限计算时间内生成无碰撞、短且平滑的路径。传统基于快速探索随机树(RRT)的方法常存在无引导采样、密集障碍物区域重复扩展失败、初始路径冗余以及后处理易碰撞等问题。为解决此问题,研究人员提出了一种环境反馈混合采样双向RRT方法,并集成了路径感知改进鲸鱼优化算法(WOA)。在初始搜索阶段,该算法利用各随机树的碰撞率在开放空间探索、启发式收敛和阻塞区域逃逸采样之间切换。进一步引入局部障碍物密度估计,融合采样方向、目标方向、对向树吸引力和障碍物斥力,同时采用自适应双步长、回溯安全步长调整和局部重连,以减少无效扩展并提高首条可行路径的质量。在后处理阶段,使用WOA优化关键路径节点而非所有节点,通过路径走廊约束、动态适应度加权、碰撞修复、弹性带细化以及B样条(B-spline)平滑,在保持可行性的同时缩短路径并提高平滑度。在四种MATLAB三维障碍物环境中各独立测试100次,并与每种环境中表现最佳的对比算法比较,所提方法分别将规划时间减少了64.4%、83.4%、80.1%和39.5%,并将路径长度缩短了4.9%、7.1%、13.4%和10.1%。在前三种环境中成功率达到100%,在最复杂的密集障碍物环境中达到97%。这些结果表明,所提框架在复杂障碍物约束下提高了三维无碰撞路径规划的搜索效率、路径质量和鲁棒性。
**研究背景与问题**
复杂三维环境中的路径规划要求算法在有限时间内生成无碰撞、短且平滑的路径。传统RRT(快速探索随机树)方法虽具有概率完备性和较高计算效率,但存在无引导采样、密集障碍区重复扩展失败、初始路径冗余及后处理易碰撞等问题。现有改进方案多侧重单一环节(如采样引导或后处理平滑),缺乏对搜索与优化阶段的协同设计。为此,研究人员提出了将环境反馈混合采样双向RRT与路径感知修复鲸鱼优化算法(WOA)相融合的框架,旨在提升搜索效率、路径质量及鲁棒性。该研究发表在《Algorithms》上。
**技术与方法(不超过250字)**
主要关键技术包括:1)碰撞率驱动混合采样策略:根据随机树碰撞率在开放空间探索、启发式收敛和阻塞区域逃逸三种模式间切换,并引入Halton低差异序列和桥采样;2)局部障碍密度感知扩展:通过14个探测方向估计局部密度,融合采样方向、目标方向、对向树吸引和障碍物斥力,并采用自适应双步长和回溯安全步长调整;3)局部重连与贪婪剪枝:在双向RRT中引入RRT
*风格的局部父节点选择和重连,再用贪婪剪枝去除冗余节点;4)路径感知修复WOA(PAWOA):仅优化关键节点(大转角、低安全裕度、高局部冗余),通过路径走廊约束、精英对立初始化、动态加权适应度函数、碰撞感知修复、弹性带局部细化和B样条(B-spline)平滑,在有限种群和迭代下提升可行解比例和优化能力。
**研究结果**
**环境1(大板状障碍物)**:对比算法a(目标偏置Informed-RRT
*)、b(双向扩展+目标偏置)、c(自适应人工势场+目标偏置)及所提算法d。算法d采样点最少、路径最简,规划时间减少64.4%,路径长度缩短4.9%,成功率100%。
**环境2(稀疏但交错通道)**:算法a和b产生大量无效分支,算法c路径更紧凑,算法d搜索节点更少、分布更集中,规划时间减少83.4%,路径长度缩短7.1%,成功率100%。
**环境3(三维绕行场景)**:算法a搜索树覆盖广、绕行远;算法b仍有分支;算法c方向性较好;算法d获得平滑空间绕行轨迹且扩展次数少,规划时间减少80.1%,路径长度缩短13.4%,成功率100%。
**环境4(密集障碍物与窄通道)**:算法a和b发散严重,算法c路径仍显绕行,算法d保持较少采样点、路径连续且可行,规划时间减少39.5%,路径长度缩短10.1%,成功率97%(最高)。
**消融实验**:去除PAWOA后,平均路径长度从2202.59增至2054.53(原文数据有误?原文为“减少到2054.53”,但实际是减少,所以PAWOA使路径更短)。逐步去除RRT增强模块(环境反馈采样、密度感知扩展、回溯安全步长)后,规划时间从0.52s增至0.81s、1.12s、1.37s;路径长度从2116.82增至2268.47、2479.63、2724.58;迭代次数从796增至934、1086、1224,验证了各模块对搜索效率和路径质量的贡献。
**结论翻译**
研究人员得出以下结论:第一,在初始路径搜索阶段,设计了碰撞率驱动的环境反馈混合采样策略和局部障碍密度感知扩展机制,通过自适应切换采样模式、融合多方向力及调整步长,减少了无效扩展,提高了初始可行路径的搜索效率。第二,在路径后处理阶段,提出了路径感知修复鲸鱼优化算法(PAWOA),通过关键节点选择、路径走廊约束、精英对立初始化、动态加权适应度函数、碰撞感知修复、弹性带局部细化和B样条(B-spline)平滑,在有限资源下提升了可行解比例和优化能力。仿真实验表明,所提算法在四种环境下均取得最短平均规划时间(0.85s)和最短平均路径长度(1922.07单位),消融实验进一步证实了各模块的有效性。未来工作将扩展至动态环境并验证实际无人机平台性能。