基于改进乌鸦搜索算法的无人艇新型路径规划策略

林蔚青，林秀芳，陈国童，黄惠; LIN Weiqing; LIN Xiufang; CHEN Guotong; HUANG Hui

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

基于改进乌鸦搜索算法的无人艇新型路径规划策略 PDF

- ORCID：
林蔚青 ¹
✉
- ORCID：
林秀芳 ²
✉
- ORCID：
陈国童 ¹
- ORCID：
黄惠 ³

1. 宁德师范学院信息与机电工程学院，福建宁德 352000； 2. 闽江学院物理与电子信息工程学院，福州 350108； 3. 福州大学机械工程及自动化学院，福州 350108

中图分类号： TP273

最近更新：2024-05-31

DOI：10.11835/j.issn.1000-582X.2023.216

摘要

鉴于无人艇的实际航行需求，所规划的路径应满足顺滑性和经济性要求，为此提出一种基于改进乌鸦搜索算法和新型路径拟合方法的路径规划策略。文中提出一种新型路径拟合方法，用于优化转向点的数量并对转向点进行圆弧过渡处理，从而缩短路径长度，并保证无人艇在航速稳定的情况下实现转向，在此基础上提出一种改进的乌鸦搜索算法，用于优化路径转向点的位置。算法的改进主要体现在3个方面：采用反向学习策略以提高初始种群质量及多样性；提出一种动态变化的意识概率以提高算法局部和全局的搜索能力；采用莱维飞行策略以改善搜索的方向性和有效性。仿真结果表明，所提出的新型路径拟合方法优于B样条曲线拟合方法和直线段拟合方法。迭代计算和方差分析结果表明：在优化新型拟合路径方面，所提出的改进乌鸦搜索算法相较于标准乌鸦搜索算法、差分进化算法和遗传算法具有更高的收敛精度和鲁棒性，能更高效地处理无人艇路径规划的实际问题。

关键词

无人艇; 路径规划; 乌鸦搜索算法; 反向学习; 意识概率

近年来，无人艇在科学考察、海洋监测和国防维权等方面的应用日渐广泛，无人艇的相关技术也越来越受到重视。无人艇的自动驾驶技术是无人艇核心技术之一，它主要包含信息采集、信息处理、自主决策、底层控制和船岸通信等方面内容。自主决策主要体现在路径规划上，通过信息处理和各种数学算法生成一条自动航行路线，包括路径信息和航速信息，路径规划不仅关系到无人艇的运行效率，还影响到无人艇的航行安全。路径规划已经成为无人艇自动驾驶的关键技术之一，受到了海内外众多学者的关注^[

1]。无人艇的路径规划主要涉及路径拟合和路径点位置的全局规划2个方面的技术问题。

目前无人艇路径基本采用直线段拟合方案^[

2]和B样条曲线拟合方案^{[参考文献 3

百度学术}3]，这2种方案的路径点分别是直线段转向点和曲线采样点，其中直线段拟合路径方案存在折角转弯的问题，即无人艇在转向点处进行转向时，需提前将航速降为零，再进行转向，这无疑影响无人艇航行的顺滑性和经济性；而基于B样条曲线的航行路径，则需要无人艇在航行过程中不停地调整行驶方向，对无人艇的方向定位仪器和自动航行装备的灵敏度和可靠度要求非常高。

对于路径点的全局规划，传统算法主要包括可视图法^[

4-5]、格栅法^{[参考文献 6

百度学术}6]、A*算法^{[参考文献 7

百度学术}7]等。可视图法由于需要不断重构可视图，存在搜索效率低和组合爆炸等问题^{[参考文献 8

百度学术}8]。格栅法中的网格大小影响搜索精度，网格太大则精度不足，网格太小则需要比较大的存储空间，搜索时间较长。A*算法可以处理复杂环境下的路径规划问题，但存在大量绕弯路径是该算法的一个主要问题。随着智能优化算法的提出和广泛应用，有部分学者已将智能优化算法应用到无人艇路径规划中，如粒子群算法^{[参考文献 9-11}9-11]、遗传算法^{[参考文献 12-14}12-14]、灰狼算法^{[参考文献 15

百度学术}15]等。

乌鸦搜索算法（crow search algorithm，CSA）是由Askarzadeh^[

16]提出的一种受乌鸦智能行为启示而产生的群体智能优化算法，该算法具有结构简单、参数少和收敛速度快等特点。实验仿真结果表明在解决多种工程问题方面，CSA的优化结果优于遗传算法、粒子群算法与和声搜索算法，已经在一些领域取得了较好的应用成果。Askarzadeh等^{[参考文献 17

百度学术}17]使用CSA精确预测火力发电厂的输入-输出特性，研究结果表明CSA的性能优于粒子群算法、遗传算法、蜂群算法和最小二乘法。王丽婷等^{[参考文献 18

百度学术}18]利用CSA对支持向量机进行参数优化，仿真结果表明，与遗传算法和粒子群算法相比，CSA具有更佳的寻优能力和更快的寻优速度。然而，由于标准CSA搜索方式过于简单，导致有时搜索出现算法早熟和收敛精度不足等问题。因此，不少学者相继提出了一些CSA的改进措施。例如，Lin等^{[参考文献 19

百度学术}19]针对建筑物减震控制中的模糊控制器设计问题，提出一种实值和虚值混合编码的带变异操作的CSA，证明了这种改进CSA的收敛精度和鲁棒性都优于遗传算法；刘雪静等^{[参考文献 20

百度学术}20]提出了一种二次贪心变异型CSA，并证明了这种改进的CSA比二进制人工蜂群算法更适合求解联盟背包问题；樊英等^{[参考文献 21

百度学术}21]利用改进的二进制CSA对车载网络频谱分配问题进行优化，结果表明二进制CSA解决了原始CSA收敛速度慢、不稳定和易陷入局部最优等问题。

虽然CSA及其改进算法已在多领域得到成功应用，但鲜有将该算法用于无人艇路径优化方面的研究。文中基于优化设计的思想，在选中某种优化指标的基础上，对CSA进行算法改进，用于优化无人艇路径点的全局规划，此外，针对上述无人艇路径拟合方案的缺陷，提出采用直线与圆弧转弯结合的新型拟合路径方法，最终形成了一种基于改进CSA的无人艇新型路径规划策略，以期能高效处理无人艇航行路径的实际规划问题。

1 新型路径拟合方法

针对直线段拟合路径方案与B样条曲线拟合路径方案的缺陷，文中所提出的新型拟合路径拟合方法在转向点处将采用圆弧转向路径，以解决折角转弯造成的速度损失问题；在非转向部分路径则采用直线段拟合，以解决曲线路径带来的频繁转向问题；对转向点进行优化处理，以减少无人艇变向次数。

步骤1：按路径点形成初始路径(S, P₁, P₂, …, P_n_-1, G)。黑色区域为障碍物，如图1所示，P₁、P₂、P₃、P₄、P₅、P₆、P₇为路径转向点。

图1 初始路径

Fig. 1 Initial path

步骤2：优化路径转向点。由于存在部分多余的转向点，故需从起始点开始依次与后续转向点进行连线，直至与障碍物干涉。如图2中的线段SP₄与障碍物干涉了，此时应将前一点P₃作为新的第二个转向点 $P_{1}^{'}$ ，如图3所示；接下来将 $P_{1}^{'}$ 作为新的起点，重新与后续转向点进行连线，直至与障碍物干涉，如图4中的线段 $P_{1}^{'} P_{6}$ ，此时则将前一点P₅作为新第二个转向点 $P_{2}^{'}$ 所示，以此类推，最后得到新的路径，见图5所示。

图2 路径与障碍物干涉

Fig. 2 Path and obstacle interference

图3 用新的转向点替代

Fig. 3 Replacement by a new turning point

图4 第二段连接线与障碍物干涉

Fig. 4 Interference of the second connecting line with an obstacle

图5 形成最终的转向点

Fig. 5 Final turning point formed

步骤3：将新的转向点进行圆弧过渡，依据推荐的无人艇的转弯半径r，将转向点改成圆弧过渡，圆弧半径为r，圆弧转化结果见图6所示。

图6 对转向点进行圆弧过渡处理

Fig. 6 Arc transition processing for turning points

为了验证所提出的新型路径拟合方案的效果，将其与直线段拟合路径方案和B样条曲线拟合路径方案进行比较，结果如图7所示。由图可见，新型拟合路径的长度最短，路径比较顺滑，因此可以减少路径转弯带来的速度损失，如果无人艇转弯半径足够大，则不需要对航速进行调整即可实现无人艇的平稳转向，从而保证航行的经济性。

图7 路径拟合方法对比

Fig. 7 Comparison of path fitting schemes

2 基于改进乌鸦搜索算法的无人艇路径规划

鉴于新型路径拟合方法只是优化路径点数量并处理转向点圆弧过渡的问题，而全局路径点的位置也是决定路径优劣的关键因素之一，为此在新型路径拟合方法的基础上提出一种改进的CSA（improved CSA,ICSA），用于解决路径点位置的优化问题。

2.1 标准CSA

标准CSA是依据乌鸦的智能觅食行为启发提出来的。算法中的乌鸦会记住自己储藏食物的位置，同时会跟踪其余乌鸦，并偷取它们的食物，而被跟踪的乌鸦有一定的概率发现自己被跟踪了，一旦发现，则将跟踪自己的乌鸦带到其他随机位置。依据乌鸦的觅食原理，将每一只乌鸦位置作为一个解，假设种群规模为N，初代乌鸦群的位置（初始解）用 $P (t = 1) = (x_{1}^{1}, x_{2}^{1}, \dots, x_{N}^{1})$ 表示， $M (t = 1) = (m_{1}^{1}, m_{2}^{1}, \dots, m_{N}^{1})$ 表示初代乌鸦记住的藏匿食物最佳位置，且 $P (t = 1) = M (t = 1)$ 。乌鸦i在第t次迭代时的位置为 $x_{i}^{t}$ ，食物的储藏位置为 $m_{i}^{t}$ ，跟踪被发现的意识概率为P_A，假设乌鸦i随机选择乌鸦j进行跟踪，根据意识概率可将位置分为以下2种情况：

1）乌鸦j未发现被跟踪，则乌鸦i找到乌鸦j的食物储藏点 $m_{j}^{t}$ ；

2）乌鸦j发现被跟踪，则乌鸦j将乌鸦i带到随机位置。

乌鸦i的位置更新方法见式（1）和式（2）。

x_{i}^{t + 1} = x_{i}^{t} + r_{i} \times l_{f}_{i}^{t} \times (m_{j}^{t} - x_{i}^{t}) ， r_{j} \geq P_{A}

；

（1）

x_{i}^{t + 1} = 位置 随机 ， r_{j} < P_{A}

。

（2）

式中：r_i、r_j为[0,1]之间的随机数； $l_{f}_{i}^{t}$ 为乌鸦i在第t次迭代中的飞行长度。l_f一般取为2，依据文献[

16-20]，当l_f=2时搜索边界涵盖了

m_{j}^{t}

所有的相邻区域；当l_f<2时，搜索边界则较小，增加了乌鸦i停在乌鸦i和乌鸦j之间的概率；当l_f>2时，搜索边界则较大，增加了乌鸦i越过乌鸦j的概率，故将参数l设定为2；P_A为乌鸦j发现被跟踪的概率，

f (x_{i}^{t})

为解

x_{i}^{t}

的适应度。

依据标准CSA的原理，将CSA的优化步骤如下。

步骤1：随机产生初始种群 $P (t = 1)$ ，及初始记忆中的储藏位置 $M (t = 1) 。$

步骤2：依据式（1）和式（2）对乌鸦位置 $x_{i}^{t}$ 进行更新。

步骤3：判断 $x_{i}^{t + 1}$ 是否在可行域范围内，如果是，则允许更新位置，否则保持位置不变。

步骤4：计算解 $x_{i}^{t + 1}$ 对应的适应度值 $f (x_{i}^{t + 1}) 。$

步骤5：更新记忆中的食物储藏位置 $m_{i}^{t + 1}$ ， $f (m_{i}^{t})$ 表示第t次迭代中第i只乌鸦的记忆中储藏位置对应的适应度函数值，具体更新策略为

m_{i}^{t + 1} = \{\begin{matrix} x_{i}^{t + 1} ， f (x_{i}^{t + 1}) > f (m_{i}^{t}) ； \\ m_{i}^{t} ， f (x_{i}^{t + 1}) \leq f (m_{i}^{t}) 。 \end{matrix}

（3）

步骤6：判断是否满足算法收敛条件，如果不满足，则重复执行步骤2~步骤5，直至达到收敛条件。

2.2 改进的CSA

由于CSA调节参数少，易陷入局部解和收敛精度低。故从以下3个方面提出改进方案。

1）利用反向学习算法^[

22]优化初始种群。初始种群的优劣对算法的优化精度和收敛速度影响较大，多样性较好的初始种群对提升算法性能有很大帮助，而通过随机方式产生种群可能会造成初始种群分布不均，影响种群的多样性，通过反向学习对初始种群进行优化，能有效提高初始种群的有效性。下面为具体的反向学习优化方法。

假设随机初始种群 $P (t = 1) = \{x_{i, j}\}$ ， $i = 1, 2, \dots, n; j = 1, 2, \dots, D$ ，n为种群数量，D为解向量的维度， $V_{m a x}^{j} = M a x (x_{i, j})$ ， $V_{m i n}^{j} = M i n (x_{i, j})$ ， $i = 1,2, \dots, n$ 则按式（4）计算反向种群：

P' (t = 1) = (x_{i, j}^{'}) ， x_{i, j}^{'} = V_{m i n}^{j} + V_{m a x}^{j} - x_{i, j} ， i = 1,2, \dots, n; j = 1,2, \dots, D

。

（4）

通过组合种群 $\{P (t = 1) ⋃ P' (t = 1)\}$ 选择n个适应度较大的乌鸦位置作为新的初始种群。

2）采用动态意识概率替代固定意识概率。由于标准CSA的意识概率P_A是按固定概率50%来设定，故搜索过程比较僵化，考虑到初期搜索时需要保证样本的多样性，需增加全局搜索能力，故需减小P_A值；后期搜索时需保证收敛速度，故要增大P_A值。基于以上考虑，所提出的动态意识概率需满足以下3个条件。

条件1：动态意识概率必须在规定的最大和最小概率之间变化。

条件2：动态意识概率须随着迭代次数的增加而减小。

条件3：在搜索初始阶段P_A值应大于50%，在搜索后期P_A值应小于50%。

基于以上的3个条件，提出了一种动态意识概率公式，为

P_{A} = \frac{P_{A m i n} \times e^{π} - P_{A m a x} + (P_{A m a x} - P_{A m i n}) \times e x p \{[1 - {(\frac{t - 1}{T - 1})}^{2}] \times π\}}{e^{π} - 1}

。

（5）

根据式（1）和式（2）可知，P_A值越大越倾向于全局搜索，越小则越倾向于局部搜索，但考虑到搜索初始阶段也要有一定的局部搜索能力，故将P_Amax设定为0.7~0.9；同时也要保证搜索后期也有一定的全局搜索能力，故将P_Amin设定为0.1~0.3。由于文中仅是验证所提出的动态意识概率的有效性，则初步选定P_Amax=0.8，P_Amin=0.2。为了验证式（5）的有效性，将P_A与迭代次数t的函数关系表达如图8所示。

图8 P_A变化曲线图

Fig. 8 P_A variation curve

从图8中的曲线变化规律可知，迭代次数t=1时，P_A为最大值0.8，t=100时，P_A为最小值0.2；P_A随迭代次数增加而减小；迭代次数t<46，P_A均小于0.5，按式（2）进行搜索的概率提高了，从而提高了全局搜索能力；当迭代次数t≥46，P_A则开始超过0.5，按式（1）进行搜索的概率提高了，从而提高了收敛速度，增强了局部搜索能力。依据以上分析，该动态意识概率满足了上述的3个条件要求，对CSA的改进有一定的可行性。

3）采用莱维飞行改进随机搜索。莱维飞行是服从莱维分布的随机搜索路径，是一种短距离搜索和偶尔长距离的跳变相间的随机搜索方式，它能够增加种群多样性和扩大搜索范围，常用于改进粒子群、布谷鸟算法等。

莱维飞行位置更新公式为

x_{i}^{t + 1} = x_{i}^{t} + α \otimes s

，

（6）

式中： $α$ 为步长因子，通常根据式（7）来计算； $\otimes$ 表示点对点的乘积；s为步长。

α = α_{0} \times (x_{b e s t} - x_{i}^{t})

，

（7）

式中： $x_{b e s t}$ 为当前最优解位置； $α_{0}$ 为常数，通常取0.1，随机步长s借助Levy飞行的生成过程，满足

s = \frac{μ}{{|v|}^{\frac{1}{β}}}

，

（8）

式中，μ、v服从参数为 $σ_{μ}$ 、 $σ_{ν}$ 的正态分布

μ \sim N (0, σ_{μ}^{2})

，

（9）

ν \sim N (0, σ_{ν}^{2})

，

（10）

σ_{μ} = \{\frac{Γ (1 + β) \times s i n (\frac{π β}{2})}{Γ (\frac{1 + β}{2}) \times 2^{\frac{β - 1}{2}}}\}

。

(11)

式中： $β$ 取常数1.5； $σ_{ν}$ 为常数1。

2.3 基于ICSA的路径规划优化步骤

在新型路径拟合方法的基础上，ICSA对路径规划的优化按以下步骤进行。

步骤1：随机产生初始种群。

1）在起始点S与终点G之间产生m个纵向等间距分布的随机路径点，与起始点S和终点G组合成为一条初始路径 $x_{i}^{1}$ =(S,P₁,P₂,…,P_m_-1,G)=(p₁,p₂,…,p_n)，依次产生N条随机路径，进而产生初始种群 $P (t = 1) = (x_{1}^{1}, x_{2}^{1}, \dots, x_{N}^{1})$ 。

2）依据新型路径拟合方法对路径 $x_{i}^{1}$ 上的路径点进行优化，形成新型拟合路径 $y_{i}^{1}$ 。

3）基于新型拟合路径计算路径长度 $l_{i}^{1}$ ，直接将路径长度 $l_{i}^{1}$ 作为适应度值f( $x_{i}^{1}$ )使用， $x_{i}^{t}$ 的适应度值f( $x_{i}^{t}$ )的计算见式（12），其中 $l_{i}^{t}$ 为

f (x_{i}^{t}) = l_{i}^{t} = \sum_{j = 2}^{n} |x_{i, j}^{t} x_{i, j - 1}^{t}| + ρ \times \sum_{j = 1}^{n - 1} L_{i, j}^{t}

，

（12）

式中： $x_{i}^{t}$ 为第t次迭代中的第i条路径； $x_{i, j}^{t}$ 为第t次迭代中的第i条路径中的第j个转向点；ρ为惩罚因子； $L_{i, j}^{t}$ 为两相邻转向点 $x_{i, j}^{t}$ 与 $x_{i, j - 1}^{t}$ 之间的障碍物长度。

步骤2：利用反向学习算法对初始种群进行优化，对初始种群P(t=1)、对应的适应度值f( $x_{i}^{1}$ )和储藏位置M(t=1)进行更新。

步骤3：设定迭代次数t=1。

步骤4：依据式（5）计算动态意识概率P_A。

步骤5：根据式（1）和式（6）将乌鸦位置 $x_{i}^{t}$ 更新为 $x_{i}^{t + 1} 。$

步骤6：判断 $x_{i}^{t + 1}$ 是否在可行域范围内，如果是，则允许更新位置，否则保持位置不变。

步骤7：依据步骤1中的式（2）和式（3）产生新型拟合路径 $y_{i}^{t + 1}$ ，再依据式（12）计算适应度值f( $x_{i}^{t + 1}$ )。

步骤8：依据式（3）更新乌鸦的食物储藏位置 $m_{i}^{t + 1} 。$

步骤9：迭代次数增加1，即t=t+1。

步骤10：判断t是否大于总迭代次数T，如果否，则转入步骤4继续进行优化，反之，则输出最优路径（最优的食物储藏位置）和相应结果。

依据上述步骤，基于ICSA的路径规划优化流程如图9所示。

图9 基于ICSA的路径规划流程图

Fig. 9 ICSA based path planning flowchart

3 仿真实验与分析

为了验证文中所提出的ICSA的性能和新型路径拟合方法的可行性，选择在Matlab仿真环境下进行仿真实验，采用2个场景进行验证，实验的仿真区域尺寸为500×500，起点坐标为[10, 10]，终点坐标为[490, 490]，单位均为km。假设无人艇航速为60 km/h，且转弯半径为40 km，在这种前提下即可保证无人艇在转向时速度仍然维持不变。为了验证所提出的改进乌鸦搜索算法及其动态意识概率的有效性，将ICSA分为ICSA1和ICSA2，其中ICSA1的改进方面包括采用反向学习算法优化初始种群，以及采用莱维飞行策略改进随机搜索；ICSA2则在ICSA1的基础上，增加了动态意识概率以替换标准CSA的固定意识概率。同时还采用了差分进化算法（difference methods，DE）、遗传算法（genetic algorithm，GA）和标准乌鸦搜索算法（CSA）进行仿真实验。在这些优化算法中均令式（12）中的惩罚因子ρ=200、种群数N=100、最大迭代次数T=200，算法的其余参数见表1所示。由于这些算法都属于随机优化算法，因此对每个算法都进行了20次实验。

表1 优化算法初始参数

Table 1 Initial parameters of optimization algorithms

算法	参数
GA	交叉概率P_c=0.7，变异概率P_m=0.02，选择机制：轮盘赌
DE	变异缩放因子F=0.4，交叉概率P_c=0.1
CSA	飞行长度l_f=2，意识概率P_A=0.5
ICSA1	飞行长度l_f=2，意识概率P_A=0.5
ICSA2	飞行长度l_f=2，动态意识概率P_A范围（0.2~0.8）

针对ICSA2优化得到的最优路径点，分别采用新型路径拟合方法、B样条曲线路径拟合方法、直线段路径拟合方法进行路径拟合，结果如图10所示。由图可见，相较于另外2种拟合方案，利用新型路径拟合方法得到的路径长度明显更短，转向点数量更少，同时也能保证路径的顺滑性，更能满足无人艇航行的实际需求。

图10 基于ICSA的路径拟合方法对比图

Fig. 10 Comparison of path fitting strategies based on ICSA

20次实验中各算法优化得到的最佳无人艇路径见图11所示。从图11（a）中可知，ICSA1和DE优化的路径包含有4个转向点，其余3个算法的路径都只有3个转向点；从图11（b）中可知，ICSA1、ICSA2和GA优化的路径包含2个转向点，CSA和DE优化的路径则有3个转向点。

图11 4种优化算法下的路径规划对比图

Fig. 11 Comparison of path planning under four optimization algorithms

为了进一步进行比较，将不同算法优化得到的路径长度的最优值、平均值、最差值和标准差列入表2中，并利用箱线图（见图12）确定最有效的算法。由表2可见，ICSA2对应的4个指标都是最小值，尤其是路径长度的平均值明显小于另外4种算法。另外在图12中，ICSA2的箱线图最小值和中间值明显小于其余4种算法。这说明与另外4种算法相比，ICSA2的鲁棒性和收敛精度最高，证明了ICSA2在优化无人艇新型拟合路径方面的性能最好，同时也验证了所提出的动态意识概率的有效性。

表2 优化算法性能指标比较

Table 2 Comparison of performance indicators of optimization algorithms

优化算法	场景一					场景二
优化算法	最优值	平均值	最差值	标准差	最小航行时间/h	最优值	平均值	最差值	标准差	最小航行时间/h
ICSA2	709.730	714.213	719.132	2.882 71	11.83	714.521	718.503	725.182	3.074 8	11.91
ICSA1	719.728	730.149	739.654	5.587 60	12.00	728.089	740.236	754.237	7.497 2	12.13
GA	728.014	748.123	771.423	14.178 70	12.13	730.278	752.502	775.211	12.761 2	12.17
CSA	733.478	741.262	760.926	7.719 33	12.22	743.553	755.344	774.231	8.293 6	12.39
DE	770.136	790.274	820.854	15.799 80	12.84	751.334	779.184	802.232	13.943 5	12.52

图12 4种优化算法箱线图比较

Fig. 12 Comparison of four optimization algorithms for box graph

为了验证ICSA2与另外4种算法是否在性能方面存在显著的差异，采用了方差分析法，设定显著性水平 $α = 0.05$ ，分析结果见表3所示。表中S_S表示离均平方和，d_f表示自由度，M_S表示均方，F值等于组内M_S除以组间M_S。在分析结果中如果P值小于显著水平 $α$ ，则证明确实存在显著差异。表3中ICSA与另外3种算法比较的P值远小于0.05，表明ICSA2与ICSA1、CSA、GA、DE这4个算法之间都存在着统计学意义上的显著差异。

表3 方差分析结果

Table 3 Analysis of variance results

差异源	场景一					场景二
差异源	S_S	d_f	M_S	F	P	S_S	d_f	M_S	F	P
ICSA2/CSA	7 289.46	1	7 289.46	214.72	3.22×10^-17	13 572.60	1	13 572.60	346.96	1.06×10^-20
ICSA2/CSA1	2 523.78	1	2 523.78	127.68	1.03×10^-13	39 407.10	1	9 851.78	100.18	3.27×10³³
ICSA/GA	11 465.00	1	11 465.00	109.53	9.49×10^-13	11 559.60	1	11 559.60	134.18	4.93×10^-14
ICSA/DE	67 422.20	1	67 422.20	522.77	8.18×10^-24	36 822.40	1	36 822.40	361.22	5.28×10^-21

图13为ICSA2、ICSA1、CSA、GA和DE这5种算法的优化迭代图。由图可知：ICSA2优化的路径最短；ICSA1相较于ICSA，采用反向学习算法对初始种群进行优化后，提高了种群质量，同时采用了莱维飞行策略对随机搜索进行改进，提高了随机搜索的方向性，进而提高了搜索精度；与CSA1相比，ICSA2由于利用了动态意识概率，提高了搜索初始阶段的全局搜索能力和搜索末段的局部搜索能力，从而提高了搜索的效率和精度。

图13 4种优化算法的迭代图比较

Fig. 13 Comparison of iterative graphs for four optimization algorithms

4 结论

为了解决无人艇路径规划中的2个关键技术问题，实现路径的拟合和路径点位置的全局规划，提出了一种基于改进乌鸦搜索算法的无人艇新型路径规划策略。

1）提出了一种直线与圆弧转弯相结合的新型无人艇路径拟合方法，对路径点数量进行优化，精简了多余的转向点，依据无人艇转弯半径要求，对转向点进行圆弧过渡处理，从而形成了一条短而顺滑的路径。

2）在无人艇新型路径拟合方法的基础上，提出了一种改进的乌鸦搜索算法，实现了转向点位置的全局优化。主要从3个方面进行了优化算法改进：首先，引入了反向学习策略对初始种群进行优化；然后，提出了一种随迭代次数而动态变化的意识概率，以提升迭代初期的全局搜索能力和后期的局部搜索能力；最后，采用了莱维飞行策略对随机搜索进行改进。

3）仿真结果表明：所提出的新型路径拟合方法优于传统的B样条曲线路径拟合方法和直线段路径拟合方案，提高了航行路径的经济性和顺滑性。方差分析结果表明所提出的改进乌鸦搜索算法相较于标准乌鸦搜索算法、遗传算法和差分进化算法，在优化新型拟合路径方面有更强的鲁棒性和更高的收敛精度，能进一步缩短无人艇的航行距离，可进一步改善无人艇自动航行的稳定性和经济性，为无人艇自动航行路径中的关键问题提供了一种有效的解决方案。

所设定的意识概率的最大值P_Amax和最小值P_Amin对动态意识概率值有直接影响，故下一步将针对意识概率的最大值和最小值对乌鸦搜索算法性能的影响做进一步研究，同时对乌鸦搜索算法做进一步改进；另外由于海上的障碍物并非都是静止不动的，故后期研究方向将针对具有动态避障要求的全局路径规划。此外，后期研究中还将考虑使用模拟船进一步验证路径规划策略的有效性。

参考文献

吴博, 熊勇, 文元桥. 基于速度障碍原理的无人艇自动避碰算法[J]. 大连海事大学学报, 2014, 40(2): 13-16. [百度学术]

Wu B, Xiong Y, Wen Y Q. Automatic collision avoidance algorithm for unmanned surface vessel based on velocity obstacles[J]. Journal of Dalian Maritime University, 2014, 40(2): 13-16. (in Chinese) [百度学术]

Shah B C, Gupta S K. Long-distance path planning for unmanned surface vehicles in complex marine environment[J]. IEEE Journal of Oceanic Engineering, 2020, 45(3): 813-830. [百度学术]

Wang Z, Li G F, Ren J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm[J]. Computer Communications, 2021, 166(17): 49-56. [百度学术]

Niu H L, Lu Y, Savvaris A, et al. An energy-efficient path planning algorithm for unmanned surface vehicles[J]. Ocean Engineering, 2018, 161: 308-321. [百度学术]

Bertsekas D P. Robust shortest path planning and semicontractive dynamic programming[J]. Naval Research Logistics (NRL), 2019, 66(1): 15-37. [百度学术]

邢博闻, 杨柳, 胡庆松, 等. 无人船全覆盖路径规划算法研究[J]. 兵器装备工程学报, 2022, 43(9): 28-33. [百度学术]

Xing B W, Yang L, Hu Q S, et al. Research of unmanned ship based on artificial bee colony method[J]. Journal of Ordnance Equipment Engineering, 2022, 43(9): 28-33. [百度学术]

Long Y, Zuo Z M, Su Y X, et al. An A*-based bacterial foraging optimisation algorithm for global path planning of unmanned surface vehicles[J]. Journal of Navigation, 2020, 73(6): 1247-1262. [百度学术]

周利坤, 刘宏昭. 自适应人工鱼群算法在清罐移动机器人路径规划中的应用[J]. 机械科学与技术, 2012, 31(7): 1085-1089. [百度学术]

Zhou L K, Liu H Z. An adaptive artificial fish school algorithm for path planning of mobile tank-clearing robot[J]. Mechanical Science and Technology for Aerospace Engineering, 2012, 31(7): 1085-1089. (in Chinese) [百度学术]

Ma Y, Hu M Q, Yan X P. Multi-objective path planning for unmanned surface vehicle with currents effects[J]. ISA Transactions, 2018, 75: 137-156. [百度学术]

Wang C, Mao Y S, Du K J. Simulation on local obstacle avoidance algorithm for unmanned surface vehicle[J]. International Journal of Simulation Modelling, 2016, 15(3): 460-472. [百度学术]

Zhong J B, Li B Y, Li S X, et al. Particle swarm optimization with orientation angle-based grouping for practical unmanned surface vehicle path planning[J]. Applied Ocean Research, 2021, 111: 102658. [百度学术]

谢冲冲, 李莹. 基于改进算法的移动机器人路径规划[J]. 重庆大学学报, 2021, 44(12): 140-148. [百度学术]

Xie C C, Li Y. Path planning of mobile robots based on improved algorithm[J]. Journal of Chongqing University, 2021, 44(12): 140-148. (in Chinese) [百度学术]

Kim H, Kim S H, Jeon M, et al. A study on path optimization method of an unmanned surface vehicle under environmental loads using genetic algorithm[J]. Ocean Engineering, 2017, 142: 616-624. [百度学术]

Guo H, Mao Z Y, Ding W J, et al. Optimal search path planning for unmanned surface vehicle based on an improved genetic algorithm[J]. Computers & Electrical Engineering, 2019, 79: 106467. [百度学术]

刘志强, 何丽, 袁亮, 等. 采用改进灰狼算法的移动机器人路径规划[J]. 西安交通大学学报, 2022, 56(10): 49-60. [百度学术]

Liu Z Q, He L, Yuan L, et al. Path planning of mobile robot based on TGWO algorithm[J]. Journal of Xi’an Jiaotong University, 2022, 56(10): 49-60. (in Chinese) [百度学术]

Askarzadeh A. A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm[J]. Computers & Structures, 2016, 169: 1-12. [百度学术]

Askarzadeh A, Gharibi M. Accurate estimation of cost function parameters for thermal power plants using a novel optimization approach[J]. Energy Sources, Part A: Recovery, Utilization, and Environmental Effects, 2018, 40(19/24): 2986-2999. [百度学术]

王丽婷, 张金鑫, 张金华. 乌鸦搜索算法在SVM参数优化中的应用[J]. 计算机工程与应用, 2019, 55(21): 214-219. [百度学术]

Wang L T, Zhang J X, Zhang J H. Application of crow search algorithm in SVM parameter optimization[J]. Computer Engineering and Applications, 2019, 55(21): 214-219. (in Chinese) [百度学术]

Lin X F, Chen S M, Lin W Q. Modified crow search algorithm-based fuzzy control of adjacent buildings connected by magnetorheological dampers considering soil-structure interaction[J]. Journal of Vibration and Control, 2021, 27(1/2): 57-72. [百度学术]

刘雪静, 贺毅朝, 吴聪聪. 求解集合联盟背包问题的二次贪心变异乌鸦算法[J]. 微电子学与计算机, 2018, 35(11): 13-19. [百度学术]

Liu X J, He Y C, Wu C C. Quadratic greedy mutated crow search algorithm for solving set-union knapsack problem[J]. Microelectronics & Computer, 2018, 35(11): 13-19. (in Chinese) [百度学术]

樊英, 张达敏, 陈忠云, 等. 基于改进乌鸦算法的车载网络频谱分配方案[J]. 计算机科学, 2020, 47(12): 273-278. [百度学术]

Fan Y, Zhang D M, Chen Z Y, et al. Spectrum allocation scheme of vehicular ad hoc networks based on improved crow search algorithm[J]. Computer Science, 2020, 47(12): 273-278. (in Chinese) [百度学术]

Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64-79. [百度学术]

Home