船舶力学

		RRT*	Informed–RRT*	RRT*–smart	本文算法
地图（a）	长度/m	140.98	122.43	123.68	119.55
时间/s	1.80	2.12	2.09	1.07
地图（b）	长度/m	154.25	148.96	134.96	123.32
时间/s	2.72	3.21	3.74	1.14

		RRT*	Informed–RRT*	RRT*–smart	本文算法
地图（a）	长度/m	140.98	122.43	123.68	119.55
时间/s	1.80	2.12	2.09	1.07
地图（b）	长度/m	154.25	148.96	134.96	123.32
时间/s	2.72	3.21	3.74	1.14

北方苍鹰算法优化快速扩展随机树的无人艇路径规划研究

PDF下载

辜慧岚 , 马国军 , 张龙 , 程理泽 , 王亚军

船舶力学 | 流体力学 2025,29(12): 1885-1894

收起

船舶力学 |流体力学 2025 , 29 (12) : 1885 -1894

北方苍鹰算法优化快速扩展随机树的无人艇路径规划研究

全屏

[Author(id=1281326881060401906, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1281326881148482292, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326881060401906, language=EN, stringName=Hui-lan GU, firstName=Hui-lan, middleName=null, lastName=GU, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1281326881223979765, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326881060401906, language=CN, stringName=辜慧岚, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=江苏科技大学海洋学院，江苏镇江 212003, bio={"content":"

辜慧岚（2000–），女，硕士研究生

"}, bioImg=null, bioContent=

辜慧岚（2000–），女，硕士研究生

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1281326880959738606, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, xref=null, ext=[AuthorCompanyExt(id=1281326880980710127, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China), AuthorCompanyExt(id=1281326880993293040, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=江苏科技大学海洋学院，江苏镇江 212003)])]), Author(id=1281326881295282935, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=2013mgj@sina.com, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1281326881370780409, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326881295282935, language=EN, stringName=Guo-jun MA, firstName=Guo-jun, middleName=null, lastName=MA, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1281326881437889274, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326881295282935, language=CN, stringName=马国军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=江苏科技大学海洋学院，江苏镇江 212003, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1281326880959738606, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, xref=null, ext=[AuthorCompanyExt(id=1281326880980710127, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China), AuthorCompanyExt(id=1281326880993293040, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=江苏科技大学海洋学院，江苏镇江 212003)])]), Author(id=1281326882641654524, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1281326882733929214, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326882641654524, language=EN, stringName=Long ZHANG, firstName=Long, middleName=null, lastName=ZHANG, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1281326882796843775, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326882641654524, language=CN, stringName=张龙, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=江苏科技大学海洋学院，江苏镇江 212003, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1281326880959738606, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, xref=null, ext=[AuthorCompanyExt(id=1281326880980710127, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China), AuthorCompanyExt(id=1281326880993293040, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=江苏科技大学海洋学院，江苏镇江 212003)])]), Author(id=1281326882876535553, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1281326882952033027, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326882876535553, language=EN, stringName=Li-ze CHENG, firstName=Li-ze, middleName=null, lastName=CHENG, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1281326883014947588, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326882876535553, language=CN, stringName=程理泽, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=江苏科技大学海洋学院，江苏镇江 212003, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1281326880959738606, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, xref=null, ext=[AuthorCompanyExt(id=1281326880980710127, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China), AuthorCompanyExt(id=1281326880993293040, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=江苏科技大学海洋学院，江苏镇江 212003)])]), Author(id=1281326883111416582, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1281326883195302664, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326883111416582, language=EN, stringName=Ya-jun WANG, firstName=Ya-jun, middleName=null, lastName=WANG, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null), CN=AuthorExt(id=1281326883270800137, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, authorId=1281326883111416582, language=CN, stringName=王亚军, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=江苏科技大学海洋学院，江苏镇江 212003, bio=null, bioImg=null, bioContent=null, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1281326880959738606, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, xref=null, ext=[AuthorCompanyExt(id=1281326880980710127, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China), AuthorCompanyExt(id=1281326880993293040, tenantId=1146029695717560320, journalId=1240685776644648972, articleId=1281326870805328533, companyId=1281326880959738606, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=江苏科技大学海洋学院，江苏镇江 212003)])])]

辜慧岚, 马国军, 张龙, 程理泽, 王亚军

作者信息

江苏科技大学海洋学院，江苏镇江 212003

通讯作者:

马国军（1976–），男，博士，副教授，通讯作者，E-mail：2013mgj@sina.com

作者简介:

辜慧岚（2000–），女，硕士研究生

Path planning for USVs based on improved NGO-RRT*

Hui-lan GU, Guo-jun MA, Long ZHANG, Li-ze CHENG, Ya-jun WANG

Affiliations

Ocean College, Jiangsu University of Science and Technology, Zhenjiang 212003, China

出版时间: 2025-12-15 doi: 10.3969/j.issn.1007-7294.2025.12.006

文章导航

摘要

收起

针对无人艇路径规划中的路径冗余及算法执行时间长的问题，本文提出了一种融合北方苍鹰优化算法（NGO）与改进快速扩展随机树（RRT*）的路径规划方法。首先，设计具有避障及目标导向的适应度函数，并用该函数优化NGO初始种群，根据该适应度函数设计RRT*算法的自适应采样步长，提高在地图中的搜索效率；然后，设计最佳邻节点采样机制，该机制模拟北方苍鹰向最近同伴传递信息行为，结合无人艇航向角约束进行RRT*节点采样；最后，为提高路径平滑度，引入模拟退火算法中的Metropolis准则，并结合具有平滑度和最小路径曲率信息的适应度函数用于判断父节点优劣，设计动态重布线策略，该策略能够重新选择更合适的父节点进行动态重布线。实验结果表明，与RRT*、Informed–RRT*和RRT*–smart算法相比，本文改进算法在路径长度上分别缩短19.36%、3.36%和5.98%，搜索时间上分别减少49.33%、57.01%和59.16%，同时路径曲率也明显减小。

关键词

水面无人艇 / 路径规划 / RRT*算法 / 北方苍鹰优化算法 / 动态重布线

Abstract

收起

In order to solve the problem of path redundancy and long algorithm execution time, this paper proposed a path planning method that combines the Northern Goshawk Optimization (NGO) algorithm with the improved rapidly-exploring random tree (RRT*). First, a fitness function with obstacle avoidance and goal orientation was designed to optimize the initial NGO population. Additionally, the adaptive sampling step size of the RRT* algorithm was designed according to the fitness function to improve the search efficiency in a large-scale map. Then, the optimal neighbor node sampling mechanism was designed to simulate behavior of the northern goshawk transmitting information to its nearest companions, while also the RRT* node sampling was constrained by considering the USV’s (unmanned surface vehicle) heading angle. Finally, in order to improve path smoothness, the Metropolis criterion was introduced and the smoothness and minimum rudder angle design fitness function were combined to select a more suitable parent node for dynamic rerouting. The experimental results show that compared with RRT*, Informed-RRT* and RRT*-smart algorithms, the improved algorithm reduces the path length by 19.36%, 3.36% and 5.98%, and decreases the search time by 49.33%, 57.01% and 59.16%, respectively. At the same time, the curvature of the path also decreases significantly.

Key words

unmanned surface vehicle / path planning / RRT* algorithm / NGO algorithm / dynamic rewiring

引用本文

辜慧岚, 马国军, 张龙, 程理泽, 王亚军. 北方苍鹰算法优化快速扩展随机树的无人艇路径规划研究. 船舶力学, 2025 , 29 (12) : 1885 -1894 . DOI: 10.3969/j.issn.1007-7294.2025.12.006

Hui-lan GU, Guo-jun MA, Long ZHANG, Li-ze CHENG, Ya-jun WANG. Path planning for USVs based on improved NGO-RRT*[J]. Journal of Ship Mechanics, 2025 , 29 (12) : 1885 -1894 . DOI: 10.3969/j.issn.1007-7294.2025.12.006

正文

收起

0　引言

收起

近年来，海洋资源的进一步开发和海上作战的需求推动了水面无人艇（Unmanned Surface Vehicle，USV）的研究^[1]。无人艇因其体积小、灵活且执行力强等优点，被广泛应用于日常及军事活动中^[2]。路径规划是保障无人艇自主、安全航行的一项关键技术。由于无人艇有其自身的运动特性和航行特点，且容易受到风浪、水流等环境因素的影响，水面和水下的障碍物都可能危及到无人艇的航行安全。因此，在无人艇路径规划中必须充分考虑其操纵特性以及环境因素对航行带来的挑战。文献[3]考虑了无人艇航行特点和动态操纵特性，设计了与障碍物相对的方位角信息和动态转艏限制角，进行路径规划。文献[4]利用无人艇运动学特性，使无人艇远离障碍物较多的区域，同时引入偏流角减少水流环境对路径规划的影响。

改进的快速扩展随机树算法（Improved Rapidly–exploring Random Tree, RRT*）^[5-6]在全局路径规划中随机生成节点形成路径，通过多次迭代得到一条渐近最优的路径，但该算法在无人艇路径规划中存在对密集障碍物的处理复杂、运行时间较长以及平滑连接难度大等问题。文献[7-8]针对随机树收敛速度慢的问题，提出了改进的双向RRT的无人艇路径规划算法，对延伸节点增加转向角约束，使两棵随机树平滑连接。姜兆祯等^[9]提出了改进的人工势场法结合RRT*方法，考虑无人艇四个方向所受合力避免陷入局部最优以此获得初始路径，根据初始路径限制RRT*的采样区域，提高算法鲁棒性。Lin等^[10]针对电子海图环境下无人艇采用RRT*算法采样效率低等问题，提出了Informed–RRT*算法，设置了目标采样区域，增强了目标区域内随机树的探索能力，提高了整体性能。Wen等^[11]针对RRT*算法在路径规划时产生高碰撞率、易受水流干扰等问题，提出了基于双采样域的启发式RRT*算法，设置了椭圆区域采样空间，并通过基于安全距离的碰撞检测，使无人艇可以更加安全地避开障碍物区域。

虽然以上改进方法在缩短路径长度方面取得了显著进展，但采样效率无明显提高。近年来，群智能算法已经广泛应用于工程优化问题中。文献[12-13]提出了蚁群算法结合RRT*的路径规划方法，通过蚁群算法进行分区采样，限制RRT*采样区域。Huynh等^[14]提出了粒子群算法结合RRT*的路径规划算法，利用粒子群将随机树扩展以调整和增强算法性能。然而以上算法并未充分考虑无人艇在路径规划中的运动和操纵特性，本文利用2021年首次提出的北方苍鹰优化算法（Northern Goshawk Optimization，NGO）^[15]，设计了基于改进北方苍鹰优化的RRT*算法。首先，针对RRT*算法采样范围过大的问题，提出了两个适应度函数来约束NGO初始种群，限制RRT*的采样范围。对于避障能力不足的问题，模拟了北方苍鹰的捕猎行为，并提出了结合无人艇动力学约束的适应度函数计算方法，以此调整RRT*算法自适应步长；其次，设计了动态重布线机制，并重新选择了更优的RRT*父节点，以此得到较优初始路径；最后引入Metropolis准则并结合约束条件，提高路径平滑度。仿真结果表明，采用改进算法规划的路径，其运行时间明显缩短，路径更加平滑，更有利于无人艇的航行。

1　传统RRT*算法

收起

RRT*算法旨在生成一条从初始节点Q_init到目标节点Q_goal的无碰撞路径。图1为随机树生成新节点Q_new示意图，以Q_init为根节点，每次采样中随机选择Q_rand，并在整个树中找到距离最近的节点Q_nearest。然后，根据预定义的步长，在Q_nearest到Q_rand方向根据障碍物信息确定新节点Q_new。

RRT*算法通过重新选择父节点和重布线两个关键步骤优化随机树，使其趋向于生成最优路径。如图2（a）所示，Q_new初始父节点为Q_nearest，在以Q_new为圆心，半径为r的圆域内，所有节点都被视为候选父节点，选择路径代价最小的节点作为Q_new的最新父节点。如图2（b）所示，重新选择Q₁作为Q_new的父节点。

图3为RRT*算法重布线示意图，在Q_new找到其最新父节点后进行重布线，在圆域范围内计算节点之间路径代价，去除高代价路径。如图3（b）中去除Q₃和Q_nearest之间的连线，连接Q₃与Q_new，更新随机树的结构，减少冗余路径。

2　北方苍鹰优化算法

收起

北方苍鹰优化算法是一种受北方苍鹰的自然行为启发的基于群的优化算法^[15]，它模拟鹰群捕获猎物的行为，将捕猎策略分为识别猎物和逃生追逐两个阶段。

在识别猎物的第一阶段，北方苍鹰随机选择一只猎物并且对其发起攻击，通过全局搜索来识别最优区域。第i只北方苍鹰所要捕获的猎物位置为

$ {P_i} = {X_k}\quad i = 1,2,\cdots N,\quad k = 1,2,\cdots ,i - 1,i + 1,\cdots ,N $

(1)

第一阶段后第i只北方苍鹰第j维的新位置为

$ x_{i,j}^{{\mathrm{new}},P1} = \left\{\begin{aligned}& {{x_{i,j}} + \delta ({p_{i,j}} - I*{x_{i,j}}),\quad {F_{{p_i}}} \leqslant {F_i}} \\ & {{x_{i,j}} + \delta ({x_{i,j}} - {p_{i,j}}),\quad {F_{{p_i}}} \geqslant F} \end{aligned} \right. $

(2)

式中：$ {F_{{P_i}}} $

为目标函数值，${X_k}$

表示第k只北方苍鹰的位置，参数δ和I是用于在搜索和更新中生成NGO行为的随机数，其中δ∈[0, 1]，I为1或2。北方苍鹰种群的新位置为

$ {X_i} = \left\{\begin{aligned}& {X_i^{{\mathrm{new}},P1},\quad F_i^{{\mathrm{new}},P1} \lt {F_i}} \\ & {{X_i},\quad F_i^{{\mathrm{new}},P1} \geqslant {F_i}} \end{aligned} \right. $

(3)

式中：$F_i^{\text{new},P1}$

代表第一阶段更新后第i只北方苍鹰的目标函数值，$X_i^{\text{new},P1}$

代表第一阶段后第i只北方苍鹰的新位置。

在逃生追逐的第二阶段，猎物试图逃跑，因此北方苍鹰会继续追逐猎物并完成猎杀，从而提高NGO算法局部探索能力。此时，北方苍鹰位置为

$ x_{i,j}^{\text{new},P2} = {x_{i,j}} + Z \cdot (2\delta - 1) \cdot {x_{i,j}} $

(4)

$ Z = 0.02\left(1 - \frac{t}{T}\right) $

(5)

式中：Z表示北方苍鹰狩猎范围的半径，$x_{i,j}^{\text{new},P2}$

表示第二阶段后第i只北方苍鹰第j维的新位置，${X_k}$

表示第二阶段中第k只北方苍鹰的位置，t表示当前迭代的次数，T表示最大迭代次数。第二阶段北方苍鹰种群新位置为

$ {X_i} = \left\{\begin{aligned}& {X_i^{\text{new},P2},\quad F_i^{\text{new},P2} \lt {F_i}} \\ & {{X_i},\quad F_i^{\text{new},P2} \geqslant {F_i}} \end{aligned} \right. $

(6)

式中：$F_i^{\text{new},P2}$

表示第二阶段更新后第i只北方苍鹰的目标函数值。$X_i^{\text{new},P2}$

表示第二阶段中第i只北方苍鹰的新位置。

3　NGO–RRT*算法

收起

3.1　改进的NGO种群初始化

传统NGO算法随机生成初始种群，容易出现种群分布不均匀的问题，导致算法性能较低且收敛速度慢，如式（7）所示的Tent混沌映射常作为种群初始化的一种方法。

$ {x_{i + 1}} = \left\{\begin{aligned}&\frac{{{x_i}}}{{{u}}},\quad 0 \leqslant {x_i} \lt {{u}} \\ & {\frac{{1 - {x_i}}}{{{u}}},\quad {{u}} \leqslant {x_i} \lt 1} \end{aligned}\right. $

(7)

在无人艇路径规划中，为使初始种群能朝着靠近目标点位置延伸，从而减少对无效空间的搜索，本文设计包含障碍物与目标点信息的第一类适应度函数f₁，结合Tent混沌映射优化北方苍鹰初始种群，初始化北方苍鹰个体位置为

$ {x_{i + 1}} = \left\{\begin{aligned}&\frac{{{x_i}}}{{{f_1}}},\quad 0 \leqslant {x_i} \lt {f_1} \\ & {\frac{{1 - {x_i}}}{{1 - {f_1}}},\quad {f_1} \leqslant {x_i} \lt 1} \end{aligned} \right. $

(8)

式中：f₁为包含障碍物与终点信息的第一类适应度函数，且f₁∈（0,1），其定义为

$ {f_1} = \alpha \left(1 - \frac{{{d_{{\mathrm{obs}}}}}}{{{d_{{\mathrm{obs}}}} + {d_{{\mathrm{goal}}}}}}\right) $

(9)

式中：α表示扰动因子，d_goal和d_obs分别表示当前点到目标点和最近障碍物的欧氏距离。

3.2　RRT*自适应步长

在传统RRT*算法中，采样步长为固定值，难以适应不同复杂度的地图。当采样步长过大时，难以精细探索空间，易错过最佳路径甚至碰撞障碍物；若步长过小，则需要更多迭代次数，从而导致路径冗余，增加计算成本^[16]。为避免固定步长产生的问题，本文在随机树采样时设计动态自适应步长，使无人艇根据环境信息动态改变采样步长。

如图4所示，以无人艇中心点为圆心，T为半径，设置无人艇安全阈值，若当前节点Q_i与障碍物之间距离大于T，则将当前所处环境定义为安全区域，此时与障碍物碰撞概率较小；反之，则定义为风险区域。在规划无人艇路径时，在未达到目标采样区域且距离障碍物较远时，ρ取较小值，无人艇采用小步长；当障碍物相对较少时，ρ取值较大，无人艇采用大步长以减少搜索时间。

自适应采样步长为

$ \rho = \left\{ \begin{aligned}& {{\rho _{\max }},\quad d({Q_i},{Q_\text{obs}}) \geqslant T} \\ & {\mu [({f_1} \cdot {d_\text{goal}}) + (1 - {f_1}){d_\text{obs}}]{\rho _{\max }},\quad d({Q_i},{Q_\text{obs}}) \lt T} \end{aligned}\right. $

(10)

式中：μ为比例权重，${\rho _{\max }}$

为最大步长，ρ为采样步长，根据所处环境适应度函数f₁动态调整。

3.3　采样机制改进策略

3.3.1　最佳邻节点采样机制

无人艇在行驶过程中易受到风与海流等外界因素的干扰，增加能量消耗，导致偏离航向，增加了无人艇与障碍物碰撞概率^[16]。为减少外界因素对无人艇的影响，本文在邻节点选取过程中添加航向角偏差。图5为无人艇运动模型示意图，图5（a）为静水环境中无人艇航向图，$ \mathop {OA}\limits^{\rightharpoonup} $

为当前无人艇前进方向；图5（b）为外界因素影响下无人艇航向图，$ \stackrel{\rightharpoonup }{OA} $

为无人艇初始航向，$ \stackrel{\rightharpoonup }{OB} $

为实际航向，$ \stackrel{\rightharpoonup }{OC} $

为外界因素对无人艇阻力方向，θ_act为航向角度，且θ_act∈（0, π/4），定义为

$ {\theta _\text{act}} = \arctan (\sin ({\theta _\text{goal}} - {\theta _\text{current}}),\cos ({\theta _\text{goal}} - {\theta _\text{current}}) + {F_\text{res}}) $

(11)

其中，θ_current表示当前艇体朝向角度，F_res表示阻力影响。

$ {F_\text{res}} = - D.{V_\text{act}}.\cos ({\theta _\text{res}} - {\theta _\text{act}}) $

(12)

其中，D为阻尼系数，表示外界因素对无人艇航行速度的衰减程度，V_act为无人艇实际航速。

RRT*采样过程中随机选取采样节点，导致算法鲁棒性差，采样效率低。NGO算法中北方苍鹰探索空间时，选择其附近最合适的对象传递猎物信息。本文模拟其行为，并结合无人艇航向角偏差，设计了最佳邻节点采样机制，如图6所示。首先，定义无人艇初始位置Q_init为当前北方苍鹰所处位置，将随机树采样节点视为潜在的猎物。其次，在无人艇初始位置附近随机生成一个节点Q_rand。接着，以无人艇所处位置为圆心、安全阈值T为半径的圆域边缘设置采样节点，作为候选邻节点。然后根据自适应采样步长范围结合适应度函数值评估所有候选邻节点，选出相对较优的节点作为最佳邻节点${Q_\text{nei}}$

并加入随机树中。最佳邻节点位置为

$ {Q_\text{nei}} = {\left( {\left| {{Q_{{\mathrm{rand}}}} - {Q_{{\mathrm{init}}}}} \right| + \left| {{Q_{{\mathrm{rand}}}} - {Q_\text{goal}}} \right| + \left| {{Q_{{\mathrm{rand}}}} - {Q_\text{obs}}} \right|} \right)_{\min }} $

(13)

其中，Q_rand表示随机节点位置，Q_init表示初始点位置。在最佳邻节点Q_nei与随机点Q_rand连线方向上，以Q_nei为起点，确定新节点Q_new。此时，采样的新节点坐标为

$ \left\{\begin{aligned}& {{x_{{\mathrm{new}}}} = {x_{{\mathrm{nei}}}} + \rho \cos {\theta _\text{act}}} \\ & {{y_{{\mathrm{new}}}} = {y_{{\mathrm{nei}}}} + \rho \sin {\theta _\text{act}}} \end{aligned}\right. $

(14)

式中：θ_act表示航向角度，（x_nei，y_nei）表示最佳邻节点坐标。

3.3.2　动态重布线

RRT*随机树在选择Q_new父节点时，其选择范围受限于固定圆域，如图7（a）所示。为了适应不同复杂度的地图，优化路径的同时降低时间成本，本文提出模拟北方苍鹰动态追击过程的动态重布线策略，设计满足无人艇最小曲率约束和路径平滑度最大化的适应度函数f₂，并结合模拟退火算法Metropolis准则，改进重选Q_new父节点机制并进行动态重布线减少路径冗余。

定义Q_new的候选父节点集合V_near为一半径为r_near的圆域。动态选择父节点的具体步骤如下

（1）以Q_new为圆心、r_near为半径计算出V_near集合范围；

（2）引入Metropolis准则判断是否需要更换父节点，概率计算公式为

$ p = \left\{\begin{aligned}&1,\quad {f_{{\mathrm{new}}}} \gt {f_\text{current}} \\ & {{e^{\frac{{ - ({f_\text{current}} - {f_{{\mathrm{new}}}})}}{T}}},\quad {f_{{\mathrm{new}}}} \leqslant {f_\text{current}}} \end{aligned} \right. $

(15)

式中：f_new和f_current分别代表新节点和当前节点代入适应度函数f₂中所得的适应度值，f₂函数定义为

$ {f_2} = {\omega _1}{C_{\min }} + {\omega _2}S $

(16)

式中：C_min为无人艇最小路径曲率，S为平滑度值，ω₁和ω₂为权重系数。

（3）根据式（10）计算当前Q_new的步长ρ。

（4）确定父节点更换区域，比较ρ和半径r_near的大小。如果ρ ≤ r_near，如图7（a）所示，则以r_near为半径，Q_new为圆心，RRT*算法在此范围内寻找最合适的父节点。遍历集合V_near中所有节点，根据式（15）判断是否替换Q_new父节点。

（5）若ρ > r_near，如图7（b），则以ρ为半径重新作圆，重新划分父节点集合范围，遍历新区域内所有节点，根据路径代价选出Q_new新的父节点。

（6）若父节点产生变化，则重新计算范围内节点代价，如图7（b），去除点Q_nearest及其与Q_new的连线。

综上所述，NGO–RRT*算法具体流程如图8所示。首先，设置无人艇最大步长ρ_max，最大速度限制V_max，北方苍鹰种群数量N和最大迭代次数M。接着，利用Tent混沌映射结合第一类适应度函数f₁进行北方苍鹰种群初始化。然后，根据适应度函数f₁公式计算当前节点采样步长。其次，模拟NGO捕食策略设计最佳邻节点机制，结合无人艇动力学约束，确定相对较优的随机树新节点位置；接着，进行碰撞检测，若新节点落在安全可行域则将新节点加入随机树，继续执行节点采样，否则去除该节点重新采样；采样成功后回溯路径得到基本路径；最后，通过引入Metropolis准则和适应度函数f₂，设计动态重布线策略，以确定Q_new的相对较优父节点Q_parent，从而得到平滑的路径。

4　仿真实验

收起

本文实验计算机为Intel（R） Core i5–12500H CPU@2.5 GHz，16 GB内存；操作系统为Windows 11，编程语言为Python 3.9，编程环境为Visual Studio 2021。为了验证本文所提出的无人艇路径规划算法的性能，我们设计了两种地图：一种是狭窄障碍物环境，另一种是障碍物较多的复杂环境，如图9所示。地图大小均为100 m×100 m，灰色区域为障碍物，白色区域为无人艇可行域，无人艇初始位置设置为[6 m, 10 m]，目标点位置为[90 m, 90 m]。

将NGO–RRT*算法与RRT*、Informed–RRT*和RRT*–smart^[17]分别进行50次仿真实验，通过路径长度、算法搜索时间和路径平滑度三个指标评价算法性能。其中，路径平滑度利用路径曲率判断，每隔十个采样节点计算一次路径曲率，曲率越小，路径越平滑。本文实验中设计最大步长为3 m，无人艇长度为2 m，最大转向角为π/4，安全距离为1 m，NGO种群大小为20，最大迭代次数为1500。

四种算法规划路径的实验结果如图10所示。在狭窄地图中，RRT*算法具有随机性，随机树生长路线不具备倾向性，只能遍历全区域才能找到路径，路径曲折且较长，路径质量不高。Informed–RRT*算法采用目标偏置采样策略，使其采样范围具有目标引导性，能够减少采样范围，但仍存在大量重复的无效采样且路径曲折；RRT*–smart算法优化了路径曲折度，但在狭窄地图中采样范围没有得到限制，增加了无效采样。本文算法利用障碍物信息，结合Tent混沌映射和适应度函数，生成偏离障碍物并偏向目标点的初始种群，减少无效采样区域。设计自适应步长，根据无人艇与障碍物和目标点的距离动态调整采样步长，路径曲折度和路径采样效率均得到明显改善，且整体路径不存在过大转向角。

为了观察局部路径质量，我们分别取图10中区域1和区域2两处位置的局部放大图进行对比。结果显示，RRT*算法路径具有较强的随机性，在区域1和区域2的路径均出现较多不必要的拐点；Informed–RRT*路径质量提高，但仍存在明显拐点；而RRT*–smart转向角数量相对减少，但弯曲处转向角过于尖锐。相比之下，本文算法模拟北方苍鹰择优选择消息传递对象行为，由无人艇航向角约束的最佳邻节点进行节点采样，确定新节点位置。在动态重布线中，我们根据路径最小曲率和平滑度最大化的适应度函数，通过动态重布线改进了RRT*随机树的父节点选取，限制并及时调整路径转向角度，因此几乎不存在较大转向角。这可以看出，在狭窄地图中，本文算法更有利于无人艇航行。

在障碍物较多的复杂地图中，如图11所示，RRT*算法形成的最终路径是由多条短路径组成的。Informed–RRT*算法在复杂地图中搜索时，目标导向性能降低，采样范围增大至几乎全地图，目标采样率降低且路径长度无明显改善；RRT*–smart算法路径曲折度和采样效率都得到明显提高；在路径质量方面，与RRT*算法和Informed–RRT*算法相比，本文算法的适应度函数包含了障碍物和目标点信息，确保采样过程中能在远离障碍物的前提下最大程度接近目标点，通过最佳邻节点机制提高随机树采样效率，减少无效采样次数。本文算法利用模拟退火算法的Metropolis准则判断是否需要更换采样节点的父节点，实现动态重布线，使路径质量明显提高，采样范围更小。

本文算法与其他三种算法在两种地图中寻找最优路径的平均搜索时间和路径长度如表1所示。RRT*算法中路径长度最长且算法搜索时间相对较长；Informed–RRT*算法和RRT*–smart算法中路径长度明显改善，但是搜索时间也明显增加；本文算法通过结合目标导向适应度函数和Tent混沌映射优化北方苍鹰初始种群，使随机树朝向目标点生长，从而减少随机性并缩短探索时间。同时，为了判断新节点位置是否需要更换，设计动态重布线缩短路径长度。本文算法生成的路径在保障无人艇与障碍物无碰撞行驶的前提下，路径长度最短且搜索速度最快，相比于RRT*算法、RRT*–smart算法和Informed–RRT*算法，在狭窄障碍物地图中，本文算法平均路径长度分别缩短15.20%、2.35%和3.34%，搜索时间分别减少40.56%、49.53%和48.80%。在复杂地图中，平均路径长度分别缩短23.52%、4.37%和8.62%，搜索速度分别提升58.09%、64.49%和69.52%。这表明本文算法在两种地图中均具有较高的路径质量和搜索效率。

在两种地图中，对四种算法在路径质量方面进行实验，图12为算法在狭窄地图中的对比图。图12（a）为路径曲率盒线图，图12（b）为路径长度收敛时间折线图。由图12（a）可知，在无其他平滑策略前提下，RRT*算法路径曲率的最大值、最小值以及平均值都明显大于其他算法，说明RRT*算法路径最曲折；Informed–RRT*和RRT*–smart曲率数值接近，整体曲率略大于本文算法。本文算法路径曲率值较为集中，大部分曲率小于0.1，说明本文算法稳定且路径平滑。由图12（b）可知，所有算法均具有最优收敛的性质，其中本文算法收敛到最优路径时长为1.25 s，仅为RRT*算法（2.60 s）的48.08%，Informed–RRT*算法（2.99 s）的41.67%和RRT*–smart算法（3.40 s）的36.76%。

图13为算法在复杂地图中的对比图，图13（a）为路径曲率盒线图，图13（b）为路径长度收敛时间折线图。RRT*算法和Informed–RRT*路径曲率明显大于其他算法。本文算法相对RRT*–smart，在纵轴上跨度和曲率均较小。与RRT*、Informed–RRT*和RRT*–smart相比，本文算法路径曲率无论在平均值还是离散度上均明显较优，表明本文算法路径更加平滑。由图13（b）可知，本文算法收敛到最优路径时长为1.40 s，仅为RRT*算法（2.59 s）的53.85%，Informed–RRT*算法（3.01 s）的46.47%和RRT*–smart算法（3.40 s）的41.18%。综上所述，本文算法在收敛时间、路径长度和路径平滑度三个方面均具有明显优势。

5　结论

收起

本文针对无人艇采用RRT*算法在狭窄地图和复杂地图中进行路径规划时产生过多冗余节点、搜索时间过长的问题，提出了一种基于NGO优化的RRT*算法。仿真实验结果表明：

（1）根据无人艇航行环境障碍物信息，本文设计避障与目标导向结合的适应度函数用以优化北方苍鹰初始种群，快速收敛到较优解，这不仅减少了算法的搜索空间和收敛时间，还使得算法更具鲁棒性，提高了算法的效率。

（2）基于北方苍鹰捕食猎物行为设计的自适应步长，可以根据环境的复杂程度动态调整。本文针对复杂地图和狭窄障碍物地图，通过评估当前解的适应度，无人艇可以智能地调整步长，以适应不同类型地图的需求。

（3）根据北方苍鹰全局搜索时的行为和无人艇操纵特性，本文提出了结合无人艇航向角约束的最佳邻节点机制，通过衡量最近点的优劣，选择相对较优的采样节点，提高了算法的运行效率，并能够灵活地调整采样方向。

（4）针对路径冗长及不平滑问题，本文提出了满足第二类适应度函数约束的动态重布线机制。该机制通过重新选择父节点使路径更平滑，同时算法能快速收敛到相对较优路径，进一步提高路径规划的质量和效率。

在仿真验证中，改进的NGO–RRT*算法运行时间更短，路径更加平滑，更利于无人艇的航行。与其他三种算法相比，本文算法在路径长度和搜索时间等方面均取得了明显改善。

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

高霄鹏, 刘冬雨, 霍聪. 水面无人艇运动规划研究综述[J]. 舰船科学技术, 2023, 45(16): 1‒6.

Gao Xiaopeng, Liu Dongyu, Huo Cong. Research review on motion planning of surface unmanned boat[J]. Ship Science and Technology, 2023, 45(16): 1‒6. (in Chinese)

郑华荣, 魏艳, 瞿逢重. 水面无人艇研究现状[J]. 中国造船, 2020, 61(S1): 228‒240.

Zheng Huarong, Wei Yan, Qu Fengzhong. Research status of surface unmanned boat[J]. Shipbuilding of China, 2020, 61(S1): 228‒240. (in Chinese)

汪咏, 徐海祥, 冯辉, 等. 考虑船舶操纵性的无人艇路径规划方法[J]. 华中科技大学学报(自然科学版), 2024, 52(3): 91‒96.

Wang Yong, Xu Haiyang, Feng Hui, et al. Path planning method of unmanned surface vehicle considering ship maneuverability[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2024, 52(3): 91‒96. (in Chinese)

徐鹏飞, 丁延旭, 曹清波. 基于环境优化的无人艇全局路径规划研究[J]. 中国造船, 2022, 63(5): 206‒220.

Xu Pengfei, Ding Yanxu, Cao Qingbo. Research on global path planning of unmanned surface vehicle based on environmental optimization[J]. Shipbuilding of China, 2022, 63(5): 206‒220. (in Chinese)

Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning[J]. The International Journal of Robotics Research, 2011, 30(7): 846‒894.

Qi J, Yang H. MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment[J]. IEEE Transactions on Industrial Electronics, 2021, 68(8): 7244‒7251.

向金林, 王鸿东, 欧阳子路, 等. 基于改进双向RRT的无人艇局部路径规划算法研究[J]. 中国造船, 2020, 61(1): 157−166.

Xiang Jinlin, Wang Hongdong, Ouyang Zilu, et al. Research on local path planning algorithm for unmanned craft based on improved bidirectional RRT[J]. Shipbuilding of China, 2020, 61(1): 157−166. (in Chinese)

Wang Jiankun, Li Baopu, Meng Max Q H. Kinematic constrained bi-directional RRT with efficient branch pruning for robot path planning[J]. Expert Systems with Applications, 2021, 170: 114541.

姜兆祯, 王文龙, 孙文祺. 基于改进RRT*算法的无人艇路径规划快速求解算法[J]. 系统仿真学报, 2024, 36(4): 888.

Jiang Zhaozhen, Wang Wenlong, Sun Wenqi. Path planning rapid algorithm based on modified RRT* for unmanned surface vessel[J]. Journal of System Simulation, 2024, 36(4): 888. (in Chinese)

Lin X, Zhao E, Wang X. Unmanned surface vehicle path planning based on improved informed–RRT* algorithm[C]//2023 IEEE International Conference on Mechatronics and Automation (ICMA). Harbin, China, 2023.

Wen N, Zhang R, Wu J, et al. Online planning for relative optimal and safe paths for USVs using a dual sampling domain reduction-based RRT* method[J]. International Journal of Machine Learning and Cybernetics, 2020, 11: 2665‒2687.

Viseras A, Losada R O, Merino L. Planning with ants: Efficient path planning with rapidly exploring random trees and ant colony optimization[J]. International Journal of Advanced Robotic Systems, 2016, 13(5): 1729881416664078.

刘挺, 王晓燕, 康智强. 基于蚁群的环境分区目标偏置RRT算法路径规划[J]. Journal of Measurement Science and Instrumentation, 2023, 14(1): 55‒65.

Liu Ting, Wang Xiaoyan, Kang Zhiqiang. Environmental zoning target bias RRT algorithm path planning based on ant colony[J]. Journal of Measurement Science and Instrumentation, 2023, 14(1): 55‒65. (in Chinese)

Huynh L Q, Tran L V, Phan P N K, et al. Intermediary RRT*-PSO: A multi-directional hybrid fast convergence sampling-based path planning algorithm[J]. Computers, Materials & Continua, 2023, 76(2): 2282–2300.

Dehghani M, Hubálovský Š, Trojovský P. Northern goshawk optimization: A new swarm-based algorithm for solving optimization problems[J]. IEEE Access, 2021, 9: 162059‒162080.

刘正锋, 张隆辉, 魏纳新, 等. 限制区域水面无人艇路径规划与跟踪控制研究[J]. 船舶力学, 2021, 25(9): 1127‒1136.

Liu Zhengfeng, Zhang Longhui, Wei Naxin, et al. Research on path planning and tracking control of surface unmanned craft in restricted area[J]. Journal of Ship Mechanics, 2021, 25(9): 1127‒1136. (in Chinese)

Nasir J, Islam F, Malik U, et al. RRT*-SMART: A rapid convergence implementation of RRT*[J]. International Journal of Advanced Robotic Systems, 2013, 10(7): 1‒12.

2025年第29卷第12期

PDF下载

162

引用本文

BibTeX

文章信息

doi: 10.3969/j.issn.1007-7294.2025.12.006

接收时间：2025-05-28
首发时间：2026-07-07
出版时间：2025-12-15

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2025-05-28

基金

作者信息

江苏科技大学海洋学院，江苏镇江 212003

通讯作者:

马国军（1976–），男，博士，副教授，通讯作者，E-mail：2013mgj@sina.com

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/cblx/CN/10.3969/j.issn.1007-7294.2025.12.006

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT