基于自适应步长布谷鸟搜索和粒子群融合算法的AUV水下三维路径规划

AUV Underwater 3D Path Planning Based on Adaptive Step-Size Cuckoo Search-Particle Swarm Optimization Algorithm

摘要

针对传统布谷鸟算法在处理自主式水下机器人（AUV）于复杂水下的三维路径规划研究时存在搜索目标不可达、寻径和避障能力弱和算法收敛速度慢等问题，提出AUV路径规划算法PSO-ASCS（particle swarm optimization-adaptive step-size cuckoo search），将粒子群算法引入改进的自适应步长布谷鸟搜索，对布谷鸟算法进行优化。利用空间分层思想建立复杂水下三维模型对PSO-ASCS算法进行路径规划和避障实验；通过考虑路径长度、路径平滑性和路径危险性三个要素构造适应度函数，对PSO-ASCS算法进行测试并与自适应步长布谷鸟算法、标准布谷鸟算法和粒子群算法进行比较。实验表明，本文算法具有较强的全局搜索能力和寻优性能、算法收敛较好，使AUV具备高效的避障和路径规划的能力。

Abstract

Addressing challenges such as unreachable search targets, weak path finding, limited obstacle avoidance ability, and slow algorithm convergence speed encountered in the 3D path planning of autonomous underwater vehicles (AUV) using the traditional cuckoo algorithm in complex waters, this paper proposes an AUV path planning algorithm, denoted as PSO-ASCS (particle swarm optimization-adaptive step-size cuckoo search algorithm). This algorithm integrates the improved adaptive step-size cuckoo Search and Particle Swarm Optimization. This research employs the conception of spatial layering to construct a three-dimensional model of complex waters for conducting path planning and obstacle avoidance experiments on the PSO-ASCS algorithm. The PSO-ASCS algorithm is tested and compared with the adaptive step size cuckoo search algorithm, standard cuckoo algorithm, and particle swarm optimization.This evaluation is carried out by constructing a fitness function that considers the three factors of path length, path smoothness, and path hazard. The experiments demonstrate that the enhanced algorithm exhibits robust global search capability and optimization performance. Moreover, the algorithm converges effectively, endowing the autonomous underwater vehicle (AUV) with the capacity to avoid obstacles and plan paths efficiently.

Graphical abstract

关键词

改进布谷鸟算法 / 粒子群算法 / 自主水下航行器 / 三维路径规划

Key words

improved cuckoo algorithm / particle swarm optimization / autonomous underwater vehicle / 3D path planning

0　 引 言

近年来，随着水声通信技术在海洋资源的开发勘探、水下救援、海底电缆检查等领域的广泛应用，自主式水下航行器(autonomous underwater vehicle,AUV)在海洋作业中的作用越来越重要，AUV技术受到国内外学者的关注。AUV可通过在工作区域内移动完成指定的工作，它搭载了供能装置，并且没有电缆的连接^[1，2]。由于AUV在水下作业的整个过程中无法补能，因此利用路径规划和避障技术对AUV进行导航，是其能否精准、安全地完成水下作业的关键^[3]。国内外学者关于AUV水下路径规划做了大量的研究工作，提出了多种群智能算法。相对于经典算法，智能算法收敛速度快、搜索精度更高，采用群智能优化算法求解AUV路径规划问题是目前的研究热点^[4]，常用的智能算法有：粒子群算法^[5]、蚁群算法^[6]、灰狼算法^[7]等。Wang等^[8]提出了一种基于改进的量子粒子群优化算法，对量子粒子群算法中的扩张-收缩因子\alpha和平均最优位置进行改进，提高了原算法的收敛性能，对AUV多目标路径规划问题进行优化，得到了更精确的路径。但是其针对海洋全域复杂环境下AUV路径规划问题采用的局部球形建模方法还有进一步的提升空间；高云龙等^[9]将布谷鸟算法引入粒子群算法中，采用中位数聚类算法将整个种群划分为若干小种群，通过PSO（particle swarm optimization）算法对各个小种群筛选出最优粒子，由CS(cuckoo search)算法对最优粒子进行再优化，这种改进提高了CS算法的效率，增强了全局搜索最优解的能力，但是该算法对于AUV在大型海域里的最优路径的选择易陷入局部最优的情况；黄鹤等^[10]针对水下复杂环境和所建立威胁源模型提出了改进的蝠鲼觅食优化算法，通过在初始化过程中加入局部反向学习机制和在蝠鲼螺旋觅食过程中融合Lévy飞行-柯西变异策略，优化了种群的位置、提高了种群的多样性，并且可实现自适应翻滚，有利于跳出局部最优，改进算法虽然扩大了种群搜索范围并且缩短了搜索路径的长度，但是该算法对AUV在水下避障之后所规划路径更新的效果有待提高。

AUV路径规划与安全避障技术快速发展的同时，仍存在一些问题。一是降维处理，现有的AUV水下路径规划研究多数未考虑水下的海拔因素，简单地将三维海洋环境转化为二维平面模型进行模拟实验，无法满足AUV水下作业的实际要求；二是现有AUV三维路径规划算法在解决复杂水下环境的情况下存在计算复杂、路径规划效果不理想、路径搜索不稳定等问题^[11]。针对这些问题，本文引入粒子群算法对改进的自适应步长布谷鸟搜索进行优化，用PSO-ASCS（particle swarm optimization-adaptive step-size cuckoo search)算法研究AUV三维水下路径规划问题；构建复杂水下环境模型来对PSO-ASCS算法进行实验，找出一条从给定起点到终点的最优或近似最优的无碰撞路径，并且通过将路径长度、平滑性和障碍物危险性三个指标建立评价函数来验证本研究的合理性。

1　 算法优化

1.1　布谷鸟算法

布谷鸟算法受布谷鸟繁衍的启发，通过引入鸟类Lévy飞行机制模拟布谷鸟从寻找鸟窝到产卵的整个过程，该算法的思想是将随机游走和Lévy飞行机制相结合，以一定概率调整步长的大小搜索解，可以同时实现小范围精细搜索与大范围全面搜索，既可以大范围寻找最优解，又可以避免局部最优，通过发现概率P_a来淘汰劣质解从而逐步获得优质解，从而有效保证算法的搜索性能。这样的算法特性符合AUV路径规划的需求^[12]。

标准CS算法中布谷鸟寻找最佳鸟窝的模拟过程是通过产生候选种群、择优选择和随机迁移三个基本过程来实现的。Yang等^[13]提出算法设计主要遵守三个规则：1) 布谷鸟在每一代繁衍过程中只产一枚鸟蛋，并且孵化在随机选择的目标鸟窝；2) 在找到更优的鸟窝之前，将当前鸟窝作为下一代的宿主进行下一次繁衍；3) 每一代可供选择的鸟窝总数是固定的。

基于上述三个规则，布谷鸟寻找线路和鸟窝位置通过(1)式产生候选种群：

x_i^{t+\mathrm{1}}=x_i^t+\alpha \mathrm{}L(\beta )(1)

(1)式中：x_i^t,x_i^{t+\mathrm{1}}分别指的是第i(i=\mathrm{1,2},\cdots n)个鸟窝在第t代、第t+\mathrm{1}代中的位置，x_i^t=x_{i,\mathrm{1}}^t,x_{i,\mathrm{2}}^t,\cdots ,x_{i,j}^t,x_{i,d}^t，j=\mathrm{1,2},\cdots ,d；t为算法迭代数，t=\mathrm{1,2},\cdots ,t_c；\alpha是控制随机搜索范围的步长因子，\alpha取大于0的常数；\mathrm{}表示点对点乘法；L(\beta )是Lévy飞行的随机寻优线路；\alpha \mathrm{}L(\beta )表示所有可行解以Lévy随机分布的方式搜索从第i代的到第i+\mathrm{1}代的距离。Yang等^[13]通过对Lévy分布函数研究，得到其概率密度函数：

(2)

由公式(2)可知，布谷鸟的连续位置变化的轨迹表示寻优路径由频繁的短跳跃和偶然的长跳跃组成，这种搜索方式可以使CS算法扩大搜索空间，从而更易跳出局部最优^[14]。计算L\left(\beta \right)随机数的公式为：

L\left(\beta \right)~\frac{\varphi \cdot \mu }{|v{|}^{\mathrm{1}/\beta }}(3)

其中，\mu和v服从标准正态分布，这里设定\beta =\mathrm{1.5}。

\varphi ={\left(\frac{\mathrm{\Gamma }\left(\mathrm{1}+\beta \right)\cdot \mathrm{s}\mathrm{i}\mathrm{n}(\frac{\mathrm{\pi }}{\mathrm{2}}\times \beta )}{\mathrm{\Gamma }\left(\frac{\mathrm{1}+\beta }{\mathrm{2}}\right)\cdot \beta \cdot {\mathrm{2}}^{\frac{(\beta -\mathrm{1})}{\mathrm{2}}}}\right)}^{\mathrm{1}/\beta }(4)

多数文献中都采用文献[13]的方法设置步长因子参数，以便Lévy飞行中的计算：

\alpha ={\alpha }_{\mathrm{0}}\cdot (X_i^t-X_b)(5)

其中，{\alpha }_{\mathrm{0}}=\mathrm{0.01},X_b表示当前最优解。结合公式(1)~(5)，通过Lévy飞行生成的解更新为：

X_i^{t+\mathrm{1}}=X_i^t+\mathrm{0.01}\mathrm{}L(\beta )X_i^t-X_b(6)

发现概率P_a(P_a\in [\mathrm{0,1}])表示宿主鸟识别巢中外来鸟蛋的概率，大部分的研究者将P_a设为固定值0.25^[15]。算法过程中，通过Lévy飞行更新鸟巢位置，生成一个随机数r\in (\mathrm{0,1})，将r与P_a进行比较，当r>P_a时，即发现外来布谷鸟蛋，算法进入随机游走环节，丢弃这个解，并在附近创建一个新的解。新解的公式更新为：

X_i^{t+\mathrm{1}}=X_i^t+v\cdot (X_i^t-X_k^t)(7)

其中，v是服从[0,1]区间内均匀分布的适应度因子；X_i^t和X_k^t表示第t代可行解的随机值。

但标准的CS算法在寻优过程中，若发现概率P_a一直较小并且步长因子\alpha一直较大，虽然算法局部搜索能力强，但难以获得精度较高的全局最优解；反之，若发现概率P_a一直较大且\alpha一直较小，则算法会经历更多次的迭代才能达到目标精度，所以本文对标准的CS算法进行改进。同时，研究发现改进算法在AUV全局路径规划中的效果较好，但是加入了障碍物之后，对路径的搜索较慢，并且算法收敛效果不理想，这将对本研究中第二个重点AUV的避障能力造成影响。所以针对此问题，本研究在改进算法中引入了粒子群算法对初始搜索种群进行改进。

1.2　改进的自适应步长布谷鸟算法

CS算法的高效性源于特殊的Lévy飞行机制。李荣雨等^[16]通过重新设计Lévy飞行中的步长因子{\alpha }_{\mathrm{0}}=\mathrm{0.001}\cdot t\cdot \mathrm{e}\mathrm{x}\mathrm{p}(-t_i/t_{\mathrm{m}\mathrm{a}\mathrm{x}})使其不再固定；并且利用动态惯性权重的偏好随机游走方式，极大地优化了标准CS算法的易陷入局部最优的问题。本文在其基础上做出了如下改进：

1)　自适应参数调整

将步长因子\alpha的值取为固定值会在算法计算过程中导致无法动态调整全局搜索和局部搜索，从而严重影响改进算法在AUV水下路径寻优时的效果。本文为实现\alpha的动态调整，基于上一代和当前代最优值之间的差值，提出了一种新的步长自适应策略。

设上一代和当前代可行解中最优值分别为f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t-\mathrm{1}}，f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t差值∆f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t=|f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t-f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t-\mathrm{1}}|，步长的衰减量计算公式为：

∆{\alpha }^t=\lambda \cdot t\cdot {\mathrm{e}}^{-∆f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t}(8)

分别将\lambda =\mathrm{0.1},\lambda =\mathrm{0.01},\lambda =\mathrm{0.001},\lambda =\mathrm{0.000}\mathrm{1}这几个不同量级的权值进行多次预实验，通过参考Valian等^[17]提出的实验方法（由图1可看出,当\lambda =\mathrm{0.001}时算法收敛的速度更快并且波动更小，会使算法收敛前期和后期的∆f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t更为平衡，相对来说更加符合在三维水下模型中的实验），设衰减率\lambda =\mathrm{0.001}。

更新步长因子的计算公式：

{\alpha }^t={\alpha }_{\mathrm{0}}-\mathrm{\Delta }{\alpha }^t(9)

Yang等^[13]设定的标准步长值{\alpha }_{\mathrm{0}}=\mathrm{0.25}。

算法搜索前期，∆f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t越大，\mathrm{\Delta }{\alpha }^t值越小，从而{\alpha }^t的值越大。较大的步长避免过早收敛，有利于提高全局搜索能力。算法搜索后期，前后两代的最优值越来越接近，所以∆f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t的值逐渐接近为0。从公式(9)可知步长变化量\mathrm{\Delta }{\alpha }^t逐渐增大，{\alpha }^t取值逐渐减小，从而提高了搜索精度。

2) 引入适应度权值因子

CS算法更新解的位置是通过个体的Lévy飞行和随机游走结合的方式淘汰可行解，由于群体之间缺乏信息交流，所以优质的个体应该具有一定的权重来更新解的位置。当公式(7)中v的取值较小时，被淘汰的解的位置X_i^t与其偏移量v\mathrm{*}(X_i^t-X_k^t)将相差多个数量级，从而导致局部路径搜索效果较差^[14]。所以引入布谷鸟算法适应度权值的概念。第i个布谷鸟个体的适应度权值计算公式为：

{\omega }_i=\left|\frac{f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t-f_i}{f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t-f_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^{t-\mathrm{1}}}\right|(10)

适应度因子{\omega }_i的权重增加能够加强CS算法中的群体交流，其中f_i表示第i个可行解。所以可行解的位置公式更新为：

\begin{array}{l}{X}_i^{t+\mathrm{1}}=X_i^t+{\alpha }^t\mathrm{}L\left(\beta \right)\mathrm{}\left(X_i^t-X_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t\right)+\\ r\cdot {\omega }_i(X_i^t-X_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}^t)\end{array}(11)

其中，参数r是CS算法在进行Lévy飞行时与发现概率P_a进行比较的在(0,1)区间上的随机数。

采用自适应搜索策略改进标准布谷鸟算法，通过领域和候选集的相互配合，在寻优过程中Lévy分布可以实现在小范围精细搜索但不局限于小范围，在小范围精细搜索过后可以大范围寻找下一个精细搜索的点，能够动态地调整候选集中分别用于集中性搜索与多样性搜索的元素个数，较好地解决了搜索过程中集中性和多样性的冲突问题。通过引入适应度权值因子加强群体信息交流，从而更快地向最优解收敛。但是由于初始种群搜索能力有限，通过实验表明该算法的收敛性与改进之前比并无优势，所以引入PSO算法对初始种群进行处理，进一步提高改进算法的收敛性。

1.3　引入PSO算法对自适应步长布谷鸟算法进行优化

PSO算法思想是鸟群在觅食行为过程中通过集体的信息交流来不断更新个体的位置从而使群体找到全局最优解。粒子仅具有两个属性：速度和位置。粒子的速度、移动的方向和距离都由适应度值决定，并且随着集体的信息交流进行动态调整，从而实现粒子群算法搜索全局最优解的过程^[18]。

假设在D维的搜索空间中，有N个粒子，每个粒子的位置为(x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_d)，相应的速度表示为(v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_d)，粒子的速度和位置迭代公式为：

\begin{array}{l}{V}_{id}^{k+\mathrm{1}}=\omega V_{id}^k+c_{\mathrm{1}}{r}_{\mathrm{1}}\left(G_{id\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id}\right)+\\ c_{\mathrm{2}}{r}_{\mathrm{2}}\left(G_{d\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id}\right)\end{array}(12)

X_{id}^{k+\mathrm{1}}=X_{id}^k+V_{id}^{k+\mathrm{1}}(13)

其中，D为粒子维度，d为粒子维度序号，d=\mathrm{1,2},\cdots ,D;N为粒子群规模，i为粒子序号，i=\mathrm{1,2},\cdots ,N;\omega为惯性权重因子，c_{\mathrm{1}}为个体学习因子，c_{\mathrm{2}}为种群学习因子，r_{\mathrm{1}}和r_{\mathrm{2}}为[0,1]区间内的随机数。G_{id\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}为第i个粒子在第d维空间的最优解，G_{d\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}为整个粒子群在第d维空间的最优解，X_{id}^k为第i个粒子在第d维空间分量的第k次迭代位置，V_{id}^k为第i个粒子在第d维空间分量的第k次迭代的速度值。

单一粒子群算法对参数设置较为敏感，且算法易陷入局部最优，不适用于本实验所建立的三维水下环境这样的三维多峰值的复杂优化问题，由于粒子群算法的收敛速度是非常优秀的，所以本研究将其引入算法模型中，对自适应步长布谷鸟算法进行优化，目的在于保证算法搜索精度的同时提高算法收敛速度。在进行自适应步长布谷鸟算法与粒子群算法的结合过程中，速度和位置迭代公式更新如下：

\begin{array}{l}{V}_{id}^{k+\mathrm{1}}=\omega V_{id}^k+k_{i,\mathrm{1}}{r}_{\mathrm{1}d}\left(G_{id\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id}\right)+\\ k_{i,\mathrm{2}}{r}_{\mathrm{2}d}\left(G_{d\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id}\right)\end{array}(14)

X_{id}^{k+\mathrm{1}}=X_{id}^k+V_{id}^{k+\mathrm{1}}+r_{\mathrm{3}}\left(X_{id}^k-X_{id}^{k-\mathrm{1}}\right)\mathrm{}L(r_{\mathrm{3}}\left(G_{d\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id}^k\right),\lambda )(15)

因为本实验都是在三维模型环境中的计算，所以d=\mathrm{3}；\omega为惯性权重。速度计算公式(14)的等式包括三部分，分别是粒子的当前速度、粒子的自我学习能力和种群学习能力；位置计算公式(15)表示的是当前的位移以及速度改变的矢量和；r_{\mathrm{3}}\in [\mathrm{0,1}]，设置它的目的在于增加初始种群的位置的随机性。将Lévy飞行的计算公式更新为：

L\left(\alpha ,\lambda \right)=\frac{\lambda \mathrm{\Gamma }(\lambda )\mathrm{s}\mathrm{i}\mathrm{n}(\frac{\lambda \mathrm{\pi }}{\mathrm{2}})}{\pi }\cdot \frac{\mathrm{1}}{{\alpha }^{\lambda +\mathrm{1}}}(16)

（16）式表示Lévy随机搜索。\lambda \in [\mathrm{1,2}]为Lévy飞行参数，设\lambda =\mathrm{1.5}，\mathrm{\Gamma }(z)服从正态分布，\mathrm{\Gamma }\left(z\right)={\int }_{\mathrm{0}}^{\mathrm{\infty }}{t}^{z-\mathrm{1}}{\mathrm{e}}^{-t}\mathrm{d}t。

本研究对速度迭代公式(14)中的自我学习因子k_{i,\mathrm{1}}和社会学习因子k_{i,\mathrm{2}}做了如下调整：

\left\{\begin{array}{c}{k}_{i,\mathrm{1}}=k_{\mathrm{1},\mathrm{m}\mathrm{i}\mathrm{n}}+\frac{(k_{\mathrm{1},\mathrm{m}\mathrm{a}\mathrm{x}}-k_{\mathrm{1},\mathrm{m}\mathrm{i}\mathrm{n}})(G_{id\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id})}{r_{\mathrm{1}}}\\ k_{i,\mathrm{2}}=k_{\mathrm{2},\mathrm{m}\mathrm{i}\mathrm{n}}+\frac{(k_{\mathrm{2},\mathrm{m}\mathrm{a}\mathrm{x}}-k_{\mathrm{2},\mathrm{m}\mathrm{i}\mathrm{n}})(G_{id\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}-X_{id})}{r_{\mathrm{2}}}\end{array}\right.(17)

其中，r_{\mathrm{1}}和r_{\mathrm{2}}是PSO-ASCS算法在进行Lévy飞行时与发现概率P_a进行比较的在(0,1)区间上的随机数。k_{i,\mathrm{m}\mathrm{a}\mathrm{x}},k_{i,\mathrm{m}\mathrm{i}\mathrm{n}}(i=\mathrm{1,2})为算法的最大和最小迭代次数。

由以上所设计的算法公式可以看出，PSO算法应用于自适应步长布谷鸟算法中的粒子位置更新，增强了算法的局部搜索能力。与此同时，算法参数可以通过每个粒子个体与最优个体之间的距离进行自适应调整，即当距离较远时，算法参数增大，加快粒子移动速度，从而起到加快收敛的作用；当距离较近时，算法参数减小，减缓粒子移动速度，从而起到充分局部寻优的作用，避免过早进入局部最优。该算法的伪代码如下所示。

1.4　路径评价函数模型建立

为搜寻最优路径，AUV后台会运用算法程序对局部最小值到多个虚拟子目标的航行线路进行评价，从所有的路径中择取最优的子目标点。本文对AUV的航行路径长度、路径平滑性和路径危险性做相应的研究，其中涉及的评价函数算法如下：AUV的航行从给定起点P_{\mathrm{1}}出发，经过若干路径点P_{\mathrm{2}},\cdots ,P_{n-\mathrm{1}}，到达给定终点P_n结束。该过程中经过的路径点连成一条完整路径path，即为一个可行解，解的形式如下：

\left\{\begin{array}{l}\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}=\left\{P_{\mathrm{1}},P_{\mathrm{2}},\cdots ,P_n\right\}\\ P_i=(x_i,y_i,z_i)\end{array}\right.(18)

对于所有可行解，本文综合考虑路径长度、路径平滑性和路径危险性三个因素建立路径评价模型来评估该算法所搜索路径的效果。

1.4.1　路径长度

路径长度是解决路径规划问题的首要因素，其计算方式如下：

F_{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)={\displaystyle \sum _{i=\mathrm{1}}^{n-\mathrm{1}}}‖P_{i+\mathrm{1}}-P_i‖(19)

其中，||P_{i+\mathrm{1}}-P_i||表示P_i与下一个路径点P_{i+\mathrm{1}}之间的距离。总的路径长度值是由所有路径段距离求和得到，该值越小说明路径越短。

1.4.2　路径平滑性

由于AUV内置能量有限，如果规划的路径出现过多的曲折则会导致能量的快速消耗，因此希望路径尽可能平滑。路径平滑性通过下式计算：

F_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)={\displaystyle \sum _{i=\mathrm{1}}^{n-\mathrm{1}}}|z_{i+\mathrm{1}}-z_i|(20)

其中，|z_{i+\mathrm{1}}-z_i|表示P_i到下一个路径点P_{i+\mathrm{1}}水域深度方向的位移，为近似表示路径的平滑程度，将所有位移求和，该值越小表示路径越平缓，即表示AUV的能耗越小。

1.4.3　路径危险性

由于AUV在实际的航行过程中，规划的路径不可避免地会出现误差。路径越接近障碍物，潜在风险就越大，因此路径周围的危险性也被视一个评价因素。假定其余较远的障碍物不会威胁到AUV的航行，主要筛选距离路径两个栅格范围内的障碍物情况。路径危险性的计算公式为：

F_{\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)=\frac{{\displaystyle \sum _{i=\mathrm{2}}^{n-\mathrm{1}}}\mathrm{O}\mathrm{b}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{c}\mathrm{l}\mathrm{e}\_\mathrm{N}\mathrm{u}\mathrm{m}(P_i)}{n-\mathrm{2}}(21)

其中，\mathrm{O}\mathrm{b}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{c}\mathrm{l}\mathrm{e}\_\mathrm{N}\mathrm{u}\mathrm{m}(P_i)表示筛选范围内的障碍物总数；F_{\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)表示一条路径上每个路径点周围障碍物的平均数量，该值越小表示路径越安全。

针对上述三个评价指标，为了将多目标的优化问题转化为单目标问题进行求解，首先分别对得到的三个函数值取均值，然后对三个指标进行加权求和得到总的路径评价值，将其作为路径评价函数，并求其最小化，该值越小表示规划出来的路径越优。具体计算如下式：

F\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)={\omega }_{\mathrm{1}}{\overline{F}}_{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)+{\omega }_{\mathrm{2}}{\overline{F}}_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)+{\omega }_{\mathrm{3}}{\overline{F}}_{\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)(22)

其中，{\overline{F}}_{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)、{\overline{F}}_{\mathrm{r}\mathrm{o}\mathrm{u}\mathrm{g}\mathrm{h}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)和{\overline{F}}_{\mathrm{d}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{e}\mathrm{r}}\left(\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}\right)表示均值；{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}}分别表示这三部分的权重，并且{\omega }_{\mathrm{1}}+{\omega }_{\mathrm{2}}+{\omega }_{\mathrm{3}}=\mathrm{1}；本文通过多次实验发现，设置权重参数为{\omega }_{\mathrm{1}}=\mathrm{0.6},{\omega }_{\mathrm{2}}=\mathrm{0.2},{\omega }_{\mathrm{3}}=\mathrm{0.2}，能使所规划的路径在三个指标上都满足本文研究对象AUV对航行路线的需要。

2　 实验分析

为验证优化算法的有效性，需从以下两个方面搭建水下仿真环境。一是针对AUV海洋环境建模将水下环境信息转化为计算机可识别的表达方式；二是将PSO-ASCS算法应用在所建立路径评价函数来衡量路径的优劣，也可以看作本文优化问题的目标函数。为验证所改进的算法在解决AUV三维路径规划问题上的可行性，本文选取了较复杂的海洋环境进行建模实验。

2.1　三维复杂水下环境建模

本文从GEBCO(general bathymetric chart of the oceans)全球海陆卫星数据库中选取太平洋海域海底地形数据，利用栅格法和空间分层思想采样得到的海洋环境建立三维空间坐标系以来建立三维水下模型。其中，X轴、Y轴分别表示水域的长度和宽度，Z轴表示海拔高度，OABC表示AUV在水下的工作区域。如图2所示。

水下路径规划问题主要是在复杂海洋环境中寻找起点和终点之间的最优或次优路径。水下环境由于具有敌对性和动态性，对AUV的路径规划仍然是一个巨大的挑战。路径规划在海洋环境中受到一系列具有挑战性的因素的影响，包括大气、洋流和重力。在路径规划控制问题上，AUV必须考虑到这些因素。本文所建立的三维海洋模型图如图3所示。

本文在建立水下模型时加入了洋流的影响因素，定义了强洋流区域；在水下航行时，为了保证航行的安全和有效性，AUV要尽量避免和利用强洋流区域。考虑了这些因素，为AUV所作的路径规划不仅可以避免航行时由于逆流所造成的能量损耗，甚至可以利用洋流的推力来提高AUV的航行速度，节省能耗。

实验选用Lamb涡流模型，其速度矢量可以用{\stackrel{⃑}{V}}_c表示，则：

{\stackrel{⃑}{V}}_c=(v_x,v_y,v_z)(23)

式中，v_x,v_y,v_z分别表示在X轴、Y轴和Z轴方向的速度分量，本文所建立的水下模型中的强洋流地带可以用下式表示：

\left\{\begin{array}{l}{S}_{\mathrm{0}}=\frac{\partial \omega }{\partial t}+{\stackrel{⃑}{V}}_c\nabla \omega \\ \omega =\left|\frac{\partial v_x}{\partial x}-\frac{\partial v_y}{\partial y}-\frac{\partial v_z}{\partial z}\right|\end{array}\right.(24)

其中,S_{\mathrm{0}}表示的是洋流强度，\omega表示涡流的涡度；\nabla表示拉普拉斯运算符。从公式(24)可看出S_{\mathrm{0}}的值与坐标值以及X轴、Y轴、Z轴上的速度密切相关，计算所得到的具体数据以供后文设计的评价函数的求解。AUV起点和终点数据参数如表1所示；粗略导航点6个；导航点总数100；距障碍物的最近距离0.01 km。为计算简便，都取近似整数。

海洋环境对AUV的探测和路径规划有着极大的影响。在路径规划之前要对水下环境进行建模，建模过程中要尽可能多地考虑实际海洋环境中的复杂性。通过对环境进行精确、详细的建模，所设计的算法才能为AUV规划出更优的路线，同时也会降低所设计的算法的时间和空间复杂性。

因为本文重点研究AUV的水下路径规划，其避障能力也是其中很重要的一项，所以首先需要在已建立好的三维模型中加入障碍物。常见的海底障碍物建模方法有圆形建模、球形建模等^[8]，本文为了更好地模拟海底不规则障碍物，考虑到障碍物长宽高上的不一致，采用的是暂未使用过的圆柱形建模方法，实验表明圆柱形建模能够更好地模拟海底无规则障碍物，表2为在该模型中添加的5个圆柱形障碍物的坐标参数。

图4模拟了AUV在航行过程中的受力情况，AUV在水下受到目标点的牵引力F_{\mathrm{引}}，从而朝着目标点航行；当AUV在航行过程中检测到前面的障碍物时，障碍物所形成的斥力势场会给AUV斥力F_{\mathrm{斥}\mathrm{1}},F_{\mathrm{斥}\mathrm{2}},\cdots，斥力在AUV越来越靠近障碍物时达到最大值，斥力剧烈增加致使AUV驶离障碍物，斥力与引力对AUV形成了一个新的合力F_{\mathrm{合}}，全部的合力最后合成一个力F_{\mathrm{航向}}朝着目标点航行。最后按照更新后的全局路径进行航行，循环至AUV安全抵达终点结束。

2.2　PSO-ASCS算法在路径规划中的实验过程

采用PSO-ASCS算法进行复杂水下环境中的AUV路径规划流程如下所述。首先，使用PSO-ASCS算法寻找一条全局路径。用鸟窝表示可行解，每条路径由每个可行解表示。起初，鸟窝被初始化为一组随机解，每个鸟窝都有两个属性：速度和位置。在每一轮迭代中，通过计算每条路径的评价值来更新个体最优解和全局最优解，然后根据这两个变量不断更新个体的速度和位置。通过多轮迭代，最终可行解将聚集在最优路径周围，实现路径预搜索任务。AUV将会沿着这条全局路径行驶，如图5所示，AUV随着决策航向航行。

算法执行流程如图6。

2.3　仿真实验

为了验证改进的算法是否能适应三维复杂海域环境，这里采用2.1节所建立的海域模型进行实验仿真。软件环境为MATLAB R2021a，对PSO-ASCS算法在AUV三维水下路径规划进行仿真实验。并且通过评价函数来说明算法的可行性。

三维路径规划，参数：障碍物d_j,j\in \{\mathrm{1,2},\cdots ,\mathrm{5}\}的影响范围设置为\left[-\mathrm{15,15}\right]；AUV的引力常数k_{\mathrm{a}\mathrm{t}\mathrm{t}}=\mathrm{30}，斥力常数k_{\mathrm{r}\mathrm{e}\mathrm{p}}=\mathrm{300}，洋流影响系数k_c=\mathrm{2}。通过参考这些参数，了解障碍物的阻碍空间方位以及斥力和斥力系数。当AUV遇到障碍物时，产生引力和斥力；了解海洋洋流影响系数，以提前做好预防或者覆盖海洋洋流力的作用。

PSO-ASCS算法的设置参数如下：初始种群规模200，退化率0.99，c_{\mathrm{1}}=c_{\mathrm{2}}=\mathrm{2},v_{\mathrm{m}\mathrm{i}\mathrm{n}}=-\mathrm{20},v_{\mathrm{m}\mathrm{a}\mathrm{x}}=\mathrm{20}。通过实验发现，惯性权值因子\omega =\mathrm{0.6}可以使PSO算法预搜索得到较好的初始信息素分布；同时由于仿真实验环境较复杂，PSO-ASCS算法总能在300次迭代之前收敛完成，因此，将最大迭代次数调整为300。

2.4　算法对比实验

为验证实际规划路径效果的优异性，实验将本文算法与ASCS算法、CS算法和PSO算法进行比较。具体模拟仿真数据如表3所示。本文通过多次实验确定了路径评价函数模型中的三个权重值，分别为：{\omega }_{\mathrm{1}}=\mathrm{0.6},{\omega }_{\mathrm{2}}={\omega }_{\mathrm{3}}=\mathrm{0.2}。

由表3可知，与其他智能算法相比，PSO-ASCS算法在本实验中表现突出，算法稳定；从路径长度、路径平滑性和路径危险物个数三个指标上看均是最优；评价函数F值最小，说明其规划的路径最优，并且耗时最短。

PSO-ASCS算法函数收敛速度随着随迭代次数t变化的曲线如图7所示。由图7可知，4种算法达到相同目标时，PSO-ASCS算法的迭代次数最少，因此PSO-ASCS算法迭代效果最好。

图8（a）为4个算法分别在该水下(三维)模型中的路径规划。从图8（a）可看出，PSO-ASCS算法在该水下模型中对AUV所规划的路径是最优的。

为突出4个算法实验的对比，本文还构建了二维平面模型图。如图8（b）所示，PSO-ASCS优化算法在路径长度、路径平滑性和与障碍物切合程度上都更为优异。

Fig.8 Complex sea experiments with four intelligent algorithms for path planning

3　 结 语

本文研究了复杂水下环境下的AUV路径规划问题，提出改进的自适应步长布谷鸟算法与粒子群算法相融合的新型路径规划算法，将布谷鸟算法中Lévy飞行和粒子群算法随机游走的解更新方式结合，实现了CS算法精确搜索能力与PSO算法高效迭代能力的有机结合，提升了算法的搜索能力。最后综合考虑路径长度、路径平滑性、路径障碍物危险个数三个评判标准建立路径评价模型来判定搜索路径的优劣。实验结果表明，在有障碍物的复杂水下三维路径规划问题中PSO-ASCS算法相较于ASCS算法、PSO算法和CS算法具有更优秀的寻径精度和避障能力，并且算法的收敛和寻径更快，得到的路径更优。

由于所搭建的三维水下模型是基于空间分层思想，需要在每个二维平面选取一个中间路径点；在实际避障过程中，由于规划得到的路径拐点较多，将导致增加路径长度，增加AUV的能耗。在未来的研究中可以进一步优化算法，解决AUV能耗问题，同时，可以对水下环境模型进一步优化，使其更大程度上接近真实海洋模型。

参考文献

[1] 孙玉山，冉祥瑞，张国成，等. 智能水下机器人路径规划研究现状与展望［J］. 哈尔滨工程大学学报，2020，41（8）：1111-1116. DOI： 10.11990 /jheu.201906048 .

[2] SUN Y S， RAN X R， ZHANG G C， et al. Research status and prospect of path planning for autonomous underwater vehicles［J］. Journal of Harbin Engineering University，2020，41（8）：1111-1116. DOI： 10.11990 /jheu.201906048（Ch ）.

[3] GUO J， HE B， SHA Q X. Shallow-sea application of an intelligent fusion module for low-cost sensors in AUV［J］. Ocean Engineering，2018，148：386-400. DOI： 10.1016/j.oceaneng.2017.11.015 .

[4] SUN K Y， LIU X Y. Path planning for an autonomous underwater vehicle in a cluttered underwater environment based on the heat method［J］. International Journal of Applied Mathematics and Computer Science， 2021，31（2）： 289-301. DOI： 10.34768/amcs-2021-0020 .

[5] PANDA M， DAS B， SUBUDHI B， et al. A comprehensive review of path planning algorithms for autonomous underwater vehicles［J］. International Journal of Automation and Computing，2020，17（3）：321-352. DOI： 10.1007/s11633-019-1204-9 .

[6] LIU X H， ZHANG D G， ZHANG J， et al. A path planning method based on the particle swarm optimization trained fuzzy neural network algorithm［J］. Cluster Computing， 2021， 24（3）： 1901-1915. DOI： 10.1007/s10586-021-03235-1 .

[7] 刘雨青，向军，曹守启. 基于改进蚁群算法的水下自主航行机器人路径规划［J］. 计算机工程与科学，2022，44（3）：536-544. DOI： 10.3969/j.issn.1007-130X.2022.03.021 .

[8] LIU Y Q， XIANG J， CAO S Q. AUV path planning based on improved ant colony algorithm［J］. Computer Engineering and Science， 2022， 44（3）： 536-544. DOI： 10.3969/j.issn.1007-130X.2022.03.021（Ch ）.

[9] 王永琦，江潇潇. 基于混合灰狼算法的机器人路径规划［J］. 计算机工程与科学，2020，42（7）：1294-1301. DOI： 10.3969/j.issn.1007-130X.2020.07.019 .

[10] WANG Y Q， JIANG X X. Robot path planning using a hybrid grey wolf optimization algorithm［J］. Computer Engineering and Science，2020，42（7）：1294-1301. DOI： 10.3969/j.issn.1007-130X.2020.07.019（Ch ）.

[11] WANG L， LIU L L， QI J Y，et al. Improved quantum particle swarm optimization algorithm for offline path planning in AUVs［J］. IEEE Access，2020，8：143397-143411. DOI： 10.1109/ACCESS.2020.3013953 .

[12] 高云龙，闫鹏. 基于多种群粒子群算法和布谷鸟搜索的联合寻优算法［J］.控制与决策，2016，31（4）：601-608.DOI： 10.13195/j.kzyjc.2015.0352 .

[13] GAO Y L， YAN P. Unified optimization based on multi-swarm PSO algorithm and cuckoo search algorithm［J］. Control and Decision，2016，31（4）：601-608. DOI： 10.13195/j.kzyjc.2015.0352（Ch ）.

[14] 黄鹤，李潇磊，杨澜，等.引入改进蝠鲼觅食优化算法的水下无人航行器三维路径规划［J］. 西安交通大学学报， 2022，56（7）： 9-18. DOI： 61.1069/T.20220407. 1639.002 .

[15] HANG H， LI X L， YANG H， et al. Three-dimensional path planning of underwater unmanned vehicle by improved manta ray foraging optimization algorithm［J］. Journal of Xi’an Jiaotong University， 2022，56（7）： 9-18. DOI： 61.1069/T.20220407. 1639.002（Ch ）.

[16] SHEHAB M， KHADER A T， AL-BETAR M A. A survey on applications and variants of the cuckoo search algorithm［J］. Applied Soft Computing，2017，61：1041-1059. DOI： 10.1016/j.asoc.2017.02.034 .

[17] JOSHI A S， KULKARNI O， KAKANDIKAR G M， et al. Cuckoo search optimization―A review［J］. Materials Today： Proceedings，2017， 4（8）： 7262-7269. DOI： 10.1016/j.matpr. 2017.07.055 .

[18] YANG X S， DEB S. Cuckoo search： Recent advances and applications［J］. Neural Computing and Applications， 2014， 24（1）： 169-174. DOI： 10.1007/s00521-013-1367-1 .

[19] 胡章芳，冯淳一，罗元. 改进粒子群优化算法的移动机器人路径规划［J］.计算机应用研究， 2021，38（10）：3089-3092.DOI： 10.19734/j.issn.1001-3695.2021.01.0061 .

[20] HU Z F， FENG C Y， LUO Y. Improved particle swarm optimization algorithm for mobile robot path planning［J］. Application Research of Computers， 2021，38（10）：3089-3092. DOI： 10.19734/j.issn.1001-3695.2021.01.0061 .

[21] 傅文渊. 均衡单进化布谷鸟算法［J］. 电子学报，2019，47（2）：282-288. DOI： 10.3969/j.issn.0372-2112.2019.02.004 .

[22] FU W Y. Equilibrium single evolution based cuckoo search algorithm［J］. Acta Electronica Sinica，2019，47（2）：282-288. DOI： 10.3969/j.issn.0372-2112.2019.02.004（Ch ）.

[23] 李荣雨，戴睿闻.自适应步长布谷鸟搜索算法［J］.计算机科学，2017，44（5）：235-240. DOI： 10.11896/j.issn.1002-137X.2017.05.042 .

[24] LI R Y， DAI R W. Adaptive step-size cuckoo search algorithm［J］. Computer Science， 2017， 44（5）： 235-240. DOI： 10.11896/j.issn.1002-137X.2017.05.042（Ch ）.

[25] VALIAN E， MOHANNA S， TAVAKOLI S. Improved cuckoo search algorithm for global optimization ［J］. International Journal of Communications and Information Technology， 2011，1（1）：31-44. DOI： 10.22111/CIT.2011.91 .

[26] 郝琨，邓晁硕，赵璐，等.基于区域搜索粒子群算法的机器人路径规划［J］.电子测量与仪器学报，2022，36（12）：126-135. DOI：10.13382/j.jemi.B2205754 .

[27] HAO K， DENG C S， ZHAO L， et al. Robot path planning based on region search particle swarm optimization［J］. Journal of Electronic Measurement and Instrumentation， 2022，36（12）：126-135. DOI： 10.13382/j.jemi.B2205754（Ch ）.

基金资助

国家自然科学基金资助项目(52174109)

河南省科技攻关项目(212102210092)

河南省高校重点研究基金(20A520015)