融合贪婪剪枝的RRT*−DWA无人艇动态路径规划方法

Improved RRT*−DWA with greedy pruning for USV in dynamic obstacle path planning

  • 摘要:
    目的 针对无人艇(USV)在含动态障碍物的复杂海洋环境中航行时,现有快速探索随机树星算法(RRT*)与动态窗口法(DWA)融合框架存在的路径节点冗余度高、局部重规划频繁、路径平滑性差等问题,开展路径规划方法改进研究,以提升USV的动态避障实时性与航行经济性。
    方法 首先,建立考虑海流干扰的USV三自由度运动学模型,并构建包含智能体行为模型的动态障碍物仿真环境。随后,在RRT*−DWA融合框架基础上,针对USV动态场景,对经典的贪婪剪枝后处理方法进行适应性改进,引入最大连接距离约束以保障狭窄通道安全,并系统验证其对于解决RRT*−DWA框架路径冗余核心难题的有效性。最后,设计多组仿真实验,将改进算法与原始RRT*−DWA、纯局部DWA以及其他主流动态规划算法进行综合对比验证。
    结果 结果表明:在动态场景路径规划中,改进后的RRT*算法运行时间均值降低82.21%,路径长度均值降低5.66%,路径节点数减少81.67%,路径平均曲率降低40.2%;融合改进RRT*的导航系统使USV实际航行距离平均缩短1.78%。与原始RRT*−DWA相比,改进算法在相同场景下的局部重规划次数减少约65%,单控制周期平均计算耗时降低70%,且能始终保持与动态障碍物的安全距离。
    结论 所提出的基于贪婪剪枝的改进RRT*−DWA算法,能有效解决原始框架因路径冗余所导致的实时性与平滑度问题,显著提升USV在动态不确定环境中的避障能力、规划效率与航行经济性,为复杂海洋环境下的USV自主导航提供有效解决方案。

     

    Abstract:
    Objective Unmanned surface vehicles (USVs) operating in complex marine environments face significant challenges due to the presence of both static and dynamic obstacles. The integration of global path planning algorithms such as the rapidly-exploring random tree star (RRT) with local reactive planners like the dynamic window approach (DWA) has been widely adopted to achieve reliable navigation. However, existing RRT*−DWA fusion frameworks often suffer from high path node redundancy, which leads to frequent local replanning, poor path smoothness, and compromised real-time performance and energy efficiency. This study aims to address these limitations by proposing an improved path planning method that enhances the dynamic obstacle avoidance capability and navigation economy of USVs.
    Method To realistically simulate USV motion, a three-degree-of-freedom kinematic model incorporating ocean current disturbances is first established. The simulation environment is enriched with dynamic obstacles modeled as intelligent agents capable of trajectory prediction and collision avoidance behaviors, reflecting realistic maritime scenarios. Building upon the conventional RRT*−DWA fusion framework, we introduce an adaptive improvement to the classic greedy pruning post-processing technique tailored for USV dynamic environments. Specifically, a maximum connection distance constraint is incorporated to ensure safe navigation through narrow channels while preserving path connectivity. This constraint prevents the pruning process from generating unsafe direct connections between distant nodes, thereby reducing path redundancy without compromising safety. The effectiveness of the proposed method in mitigating the core issue of path redundancy is systematically verified through comparative simulations. Furthermore, extensive experiments are designed to benchmark the improved algorithm against the original RRT*−DWA, pure local DWA, and other mainstream dynamic planning algorithms such as A* with DWA and artificial potential field methods. Evaluation metrics include computational efficiency, path quality, local replanning frequency, and obstacle avoidance performance.
    Results Quantitative results demonstrate that the improved RRT* algorithm significantly outperforms the original version in dynamic scenario path planning. Specifically, it reduces the average runtime by 82.21%, the average path length by 5.66%, the number of path nodes by 81.67%, and the average path curvature by 40.2%. When integrated into the navigation system, these improvements lead to a 1.78% reduction in the actual USV navigation distance for typical missions, indicating enhanced fuel economy. Compared with the original RRT*−DWA framework, the proposed method reduces the frequency of local replanning by approximately 65% and the average computation time per control cycle by 70% under identical scenarios. Importantly, the USV consistently maintains a safe distance from dynamic obstacles, demonstrating robust collision avoidance. Additional comparisons with APF−DWA and Informed RRT*−DWA reveal that the improved algorithm achieves a superior balance between global optimality and local reactivity.
    Conclusion The proposed improved RRT*−DWA algorithm based on adaptive greedy pruning effectively resolves the real-time and smoothness issues caused by path redundancy in the original framework. It significantly enhances the obstacle avoidance capability, planning efficiency, and navigation economy of USVs in dynamic and uncertain marine environments. The incorporation of the maximum connection distance constraint ensures safety in complex scenarios, making the algorithm a practical and effective solution for autonomous USV navigation. This work provides a solid foundation for future research on multi-objective path planning and real-world deployment of USVs in challenging ocean conditions.

     

/

返回文章
返回