郭银景，孟庆良，孔 芳，吕文红

1.山东科技大学电子信息工程学院，山东青岛266590

2.青岛智海牧洋科技有限公司，山东青岛266590

3.山东科技大学交通学院，山东青岛266590

1 引言

21世纪以来，随着人类科学技术的不断进步，人们对海洋资源的开发和投入也随之增大。海洋拥有丰富的矿产资源、海洋生物资源、可再生能源，是人类社会可持续发展的重要资产。因此，海上技术的发展和相关竞争已成为许多发达国家的战略要点。自主水下航行器（autonomous underwater vehicle，AUV）作为海洋作业的重要工具，非常适合海上搜索、调查、识别和打捞作业。因此，AUV路径规划技术的研究与发展就使得海洋开发进入了一个新时代[1]。对于AUV路径规划的研究始于20世纪70年代，至今仍然是各国研究的热点问题。AUV导航技术中的路径规划问题是AUV研究的核心问题之一，而路径规划的核心就是算法的设计[2]。本文将AUV路径规划算法划分为环境建模和路径搜索两类。合理的环境建模方法有利于减少路径搜索次数，不同的路径搜索算法基于不同的环境模型。常用环境建模方法主要有：栅格法、可视图法、维诺图法等。路径搜索算法主要包括人工势场法、快速步进法、A*算法、粒子群优化算法等。AUV路径规划技术的核心就是算法的设计。目前，AUV路径规划算法的研究已经引起了广泛的关注。从传统算法到后来结合仿生学发展起来的智能算法，AUV路径规划算法的发展已经取得了很大的进步[3]。不同的路径规划算法特点不同，适用范围和领域也就不同。本文从路径规划算法自身特点出发，对路径规划算法的应用领域和发展状况进行综述，阐述各算法的优缺点以及后人的改进算法，对路径规划技术的发展具有重要意义。

2 基于环境建模的路径规划算法

路径规划具体实现时需要分成环境建模和路径搜索两个步骤进行。首先需要处理环境信息，构建相应的数学模型，依据不同的策略处理环境信息，以便于对环境进行分析和计算，对路径进行搜索和优化。合理的建模方法有利于减少路径规划的计算量，从而加快运算速度，减少存储空间。不同路径搜索算法基于不同的环境建模方法。目前应用于环境建模的主要方法有可视图法、栅格法、维诺图法等。

2.1 栅格法

栅格法（grid），最早是由Howden在1968年提出的，一般作为路径规划的环境建模技术来用，是AUV最常用的建模方法之一[4]。在进行路径规划时采用栅格表示地图，如图1所示，处理障碍物的边界时，避免了复杂的计算。它具有表示不规则障碍物的能力，并适用于所有类型的传统或智能路径搜索算法。

Fig.1 Grid method图1 栅格法

起初，研究者将栅格法应用于AUV的水下三维空间进行环境建模[5-7]，但发现规划的空间内包含大量数据，占用系统的大部分存储空间。基于上述问题，2014年，Tanakitkorn等[8]提出一种改进算法，即在实验中不考虑水深，将三维空间简化为基于网格法的二维水下环境模型。虽然环境信息存在丢失，但节省了系统空间，取得了令人满意的效果。针对三维动态环境中AUV的水下目标搜索问题，2019年，Zhu等[9]构建水下二维环境离散栅格图，根据栅格图构建相应的生物启发式神经动力学模型来表示动态环境信息，利用该模型自适应地躲避障碍物，吸引目标搜索区域，提高了AUV搜索效率，减少AUV路径规划时间。栅格法作为常用AUV路径规划算法，它很难直接解决复杂的环境信息问题，一般需要与其他路径搜索算法结合来进行路径规划。

2.2 可视图法

可视图法（visibility graph）是在1979年由Lozano和Wesley首次提出的，主要应用于全局路径规划中的环境建模。可视图法的优点是可以直观地从可视图中求得最短路径，方法简单。缺点是一旦起点和目标点发生变化，就必须重构可视图，缺乏灵活性，如图2所示。

Fig.2 Visibility graph method图2 可视图法

对于在海底稀疏和密集区域中具有不同规则几何实体的障碍物，文献[10]提出一种基于可视图几何理论的AUV路径规划算法，该算法利用常规几何实体对三维海洋环境进行建模，在考虑能耗的前提下，规划三维环境中AUV可航行路径。2013年，Gal[11]在传统可视图法建模的基础上，又做出进一步的研究，提出一种基于可视图法的改进空间模型，该模型主要减少了构建节点的数量，从而提高计算效率，又添加了螺旋算法，更好地实现AUV避障。为了避免与海洋复杂障碍物发生碰撞，2018年，Xidias等[12]提出一种基于动态可视图的导航算法。使用动态可视图完成AUV实时自主海上导航，该算法在多种情况下进行测试，以证明其鲁棒性并满足不同约束条件，在获得最优路径的同时有效避碰。可视图法的局部路径规划能力较差，常常适用于全局和连续区域内的路径规划[13]。

2.3 维诺图法

维诺图法（Voronoi diagram）是由Dunlaing和Yap在1985年提出的，是一种通用的建模方法。在模型构建领域，维诺图法广泛应用于三维模型构建中，生成一个3D全局路线维诺图，可确保AUV在作业时远离障碍物，如图3所示。文献[14]中提供了一些使用维诺图法对AUV进行水下建模的实例。

Fig.3 Voronoi graph method图3 维诺图法

传统Voronoi图法生成的路径相对安全且距离障碍物较远，然而，生成的路径不平滑。针对这一问题，2013年，Candeloro等[15]提出一种基于维诺图和费马螺旋段的曲率连续路径规划算法。采用费马螺旋段来平滑路径和提供曲率连续性，产生曲率连续的路径，该算法最终得到一条仅由直线和螺旋段组成的安全、平滑的AUV可航行路径。航行稳定性和节能是AUV在水下环境下工作的关键问题。2015年，Dong等[16]提出一种基于维诺图法的新型路径规划方法。在二维维诺图中标记障碍物的位置，并通过维诺处理器生成一个近似路径来连接初始位置和目标位置。采用极限学习机法（extreme learning machine,ELM）对路径进行再生和平滑，以较快的速度生成光滑安全的路径。该方法在保证安全的前提下，能够很好地平滑规划路径，有效地促进AUV在水下环境中自动安全驾驶。2018年，Grefstad等[17]在前人研究的基础上，基于Voronoi图和Dijkstras算法规划出一条初始路径，采用费马螺旋段和一种视距随时间变化的视导系统进行路径平滑处理，有效解决了AUV避碰问题。

随着AUV计算速度的提高和对水下环境信息完整度的需求，水下三维环境建模将成为AUV路径规划算法研究的重点。上述三种常用环境建模方法优缺点对比如表1所示。

Table 1 Comparison of advantages and disadvantages of common environment modeling methods表1 常用环境建模方法优缺点对比

3 基于路径搜索的路径规划算法

路径搜索算法是基于已建立的环境模型，在搜索路径的起点和终点之间获得一条最优路径的方法。路径搜索的算法有很多，根据自身特点不同，适用领域也各不相同。本文将常用路径搜索算法分为传统路径搜索算法、智能仿生学路径搜索算法以及其他算法三类。

3.1 传统路径搜索算法

常用的传统路径搜索算法过程简单，易于实现，但也存在路径优化效果差（可行性差）、处理速度慢、动态避障能力不足等问题，如表2所示。AUV常用传统路径搜索算法主要有人工势场法、快速步进法、A*算法等。

Table 2 Comparison of advantages and disadvantages of common conventional path search algorithms表2 常用传统路径搜索算法优缺点对比

3.1.1 人工势场法

人工势场法（artificial potential field，APF）是Khatib于1986年提出的一种虚拟力法。静态环境中基于人工势场的路径搜索是成熟的，但由于其可执行性、收敛速度、效率等因素限制，使得动态环境中基于人工势场的最优路径搜索尚不成熟。

为了提高AUV航行的安全性和稳定性，文献[18]将视线法（line of sight，LOS）和APF算法相结合进行导航，对基本的LOS方法进行改进，并引入距离阈值作为参考航向修正，减少航向修正的计算量，还可以在航迹点改变时优化转弯轨迹，使得AUV在转弯时更平稳。2012年，Subramanian等[19]将该算法应用于水下动态路径搜索。然而，AUV并未达到精确的动态避障且存在局部最优问题。因此，传统的人工势场法已不能满足AUV实时避障与路径最优的要求，必须加以改进。针对三维水下环境中AUV的最优路径问题，2013年，Saravanakumar等[20]结合方向搜索法对上述传统APF算法进行改进，提出了水下机器人多重势场法（multiple potential field，MPPF），通过对AUV势场的采样，通过微调潜在函数的正比例因子以避免局部最小值，克服了三维空间中的局部最优问题。2014年，Yan等[21]基于复杂水下环境中多AUV的动态编队模型进一步完善了人工势场法。该模型将APF算法与粒子群算法相结合，动态规划最优路径，而变维粒子群算法的作用是通过动态调整路径节点的数量和分布来寻找最优路径。考虑到海流和复杂障碍物等海洋环境因素对AUV路径规划的影响，2016年，Zhu等[22]将APF算法与速度合成法相结合，提出一种新的路径规划算法。该方法既可以在海流扰动的环境下避开海底复杂障碍物，又可以缩短到达目标点的时间和路径长度，提高AUV路径规划的效率。面对较为复杂的障碍物环绕环境难以规划出完整路径的问题，2019年，程志等[23]提出一种改进的人工势场法。引入机器人前进的方向向量，对斥力的生成和计算机制进行了调整以解决其处于局部最小点情况下无法继续规划路径的问题，改进的算法可以有效解决传统APF算法容易出现的路径规划中断情况，有效提高路径规划效率。为了提高生成路径的可行性和平滑度，2020年，Song等[24]提出一种预测人工势场法，基于该算法提出三种修正参数：角度限制、速度调整和预测势。成功地限制最大转弯角，解决凹型局部极小值问题，提高可达性，同时缩短AUV航行时间并节省能源。

3.1.2 快速步进算法

快速步进算法（fast marching,FM）是由Sethian首先提出的一种基于水平集理论的界面演化跟踪算法，具有良好的可靠性，但也存在计算成本大，处理时间长等问题。针对FM算法存在的问题，文献[25]提出一种用于水下航行器避障和路径规划的各向异性FM算法，该算法引入AUV的运动学作为约束条件，以确保水下机器人可以到达最佳路径，并提出一种基于自适应网格生成的多分辨率方案，提高了算法的整体速度，使得计算成本大大降低，获得了AUV的成本最优路径。为了解决AUV的导航安全性、能耗等问题，2014年，Yu和Wang[26]考虑AUV的机动约束，如转弯半径、安全深度、油耗以及避免与障碍物碰撞的风险，将FM算法应用于大范围海洋环境中，获得了AUV的最优路径。基于先前的研究，2015年，Yu等[27]又对FM算法做出进一步研究，针对复杂动态水下环境，提出一种基于FM算法的混合搜索快速步进方法（hybrid search fast marching method，HSFM）。这种新算法使AUV在水下动态避障中更具竞争力，同时减少路径搜索时间，并引入多个约束条件和决策标准，如海流、浅滩、珊瑚礁、动态障碍物和导航规则等，对AUV航行规划任务的实验表明，HSFM算法满足在线规划的时间约束，与其他算法相比，HSFM在时间和成本方面都具有显著优势。大范围海洋环境中，必须考虑海流等环境因素对AUV能量的影响，2017年，Song等[28]提出一种新的多层快速步进（multilayered fast marching，MFM）算法，在与障碍物保持安全距离的同时，遵循逆流区域海流规则来节约能源成本，提高了算法的实用性。

3.1.3 A*算法

A*算法是在1968年发展起来的一种启发式搜索算法，又称A-Star算法，是一种静态网络中求解最短路径的有效搜索算法。在AUV路径规划过程中，Li等[29]考虑海流等海洋环境因素的影响，采用传统A*算法进行AUV路径搜索。然而，传统A*算法存在处理速度慢，全局优化能力不足等问题。针对传统A*算法存在的不足，2012年，陈实等[30]基于稀疏A*算法，考虑到AUV本身最大转弯角和最大路径长度的约束，提出一种新的用于构造搜索空间的随机布点方法，利用随机函数均匀地布撒足够多的搜索节点，从而构成搜索空间，可显著降低计算量，提高搜索效率，从而达到良好的全局路径规划效果并提高了计算速度，有效解决了传统A*算法存在的不足，具有重要的工程应用价值。针对海流扰动下的全局路径搜索问题，2016年，Zhang等[31]提出一种改进A*算法。根据海流的特征建立海流模型，通过分析AUV在海流导航中的速度和作用力，确定用于相邻两个节点向外扩展的A*算法的条件，并应用贝塞尔曲线理论来优化路径。2019年，吴鹏等[32]则采用双向A*算法同时进行正反向路径搜索，保证了最终目标节点搜索在连线中点区域内相遇，从而缩短了寻路计算时间，使得路径搜索效率得到显著提升，满足路径规划要求，具有一定的实际意义和应用价值。

利用A*算法得到的启发式路径成本低，求解最优，其优点是在规划过程中可以及时中断和恢复。然而，A*算法通过比较当前路径的相邻网格的启发函数值来逐渐确定下一个路径网格，当存在多个最小值时，A*算法不能保证搜索的最佳路径。

3.2 智能仿生学路径搜索算法

由于传统路径搜索算法存在着路径优化效果差、处理速度慢等问题，因此在处理复杂动态环境信息下的路径规划问题时，智能仿生学路径搜索算法逐渐成为主流算法。目前常用的智能仿生学路径搜索算法有蚁群优化算法、粒子群优化算法、遗传算法、狼群算法等，但智能算法也存在收敛速度慢，计算时间过长以及易陷入局部最优[33]等问题。

3.2.1 粒子群优化算法

粒子群优化算法（particle swarm optimization，PSO）最初由Kennedy和Eberhart提出，是一种基于鸟类种群捕食和返回的启发式算法[34]。2015年，Liu等[35]采用PSO算法对AUV进行避障和路径优化，实验表明该算法易于实现，具有较强的鲁棒性和快速的收敛速度，能在有限的计算时间内保证最优性。然而，粒子群优化算法也存在实时避障能力不足，稳定性差（易陷入局部最优）等问题，因此，出现了许多改进算法，如表3所示。

2016年，Zhuang等[36]提出一种混合算法，该算法将勒让德伪谱法（Legendre pseudospectral method，LPM）与PSO算法相结合。与传统PSO算法相比，新的混合算法通过重新规划方案，可以使AUV在静态障碍物和不同位置不确定性的动态障碍物中找到更好的运动轨迹，并成功地实现实时避障。针对未知海洋环境下的路径规划问题，2018年，Yan等[37]将粒子群优化算法和路径点制导算法相结合，提出一种新的AUV路径规划算法。该算法利用多波束前视声纳发现障碍物，采用PSO算法生成合适的航路点，通过跟踪这些航路点可生成低功耗、无碰撞（路径平滑）的最优路径。文献[38]又从量子力学的角度出发提出一种具有量子行为的粒子群优化改进算法（quantum behavior particle swarm optimization，QPSO），结合量子物理的思想，在更新粒子位置时重点考虑各个粒子的当前局部最优位置信息和全局最优位置信息。针对已知障碍物和定常海流的海洋环境中，2019年，Lim等[39]又对QPSO算法做出进一步研究，提出一种基于硬约束和软约束的AUV路径规划方案。该方案使用两种粒子群优化算法，即选择性差分进化混合量子粒子群算法（selectively differential evolution hybridized quantum PSO，SDEQPSO）和选择性差分进化自适应粒子群算法（selectively differential evolution adaptive PSO，SDEAPSO）。基于各算法求解质量、稳定性和计算效率等方面的考虑，SDEQPSO算法能够生成光滑的可行路径，计算需求相对较低和效率更高。2020年，郭兴海等[40]又针对水下环境中动态障碍物和时变海流的情况，提出一种新的QPSO算法，建立以三维空间路径最短与路径平滑度最大为约束的多目标函数，根据水下海流变化情况，利用高斯噪声递归估计海流下一时间节点的速度矢量状态，再结合三维环境下的AUV运动学方程，用以确保AUV的速度输出与运行的稳定性。改进的QPSO算法能使AUV潜行时更加平稳与安全，且具有更好的自主能力。

Table 3 Characteristic analysis of PSO and improved algorithms表3 PSO及其改进算法特性分析

3.2.2 蚁群优化算法

蚁群优化算法（ant colony optimization，ACO）是一种概率算法。意大利学者Dorigo受到蚂蚁在食物搜索过程中获得最佳路径的启发，提出了蚁群算法的概念。文献[41]应用蚁群优化原理对AUV的全局路径规划问题进行研究，发现蚁群优化算法非常适合于求解复杂环境中的全局路径规划问题，且规划时间短、路径平滑。与其他算法相比，ACO算法的优点是可以应用于水下3D动态路径搜索问题，对初始路线的选择要求较低，具有很强的鲁棒性。然而，传统蚁群算法也存在收敛速度慢，容易陷入局部最优等问题，如表4所示。

Table 4 Characteristic analysis of ACO and improved algorithms表4 ACO及其改进算法特性分析

因此，提出了许多改进的蚁群算法用于AUV水下路径搜索。文献[42]提出一种用于AUV路径规划的混合自适应ACO算法。实验结果表明，AUV的最优路径长度减少14%，且算法能够有效克服收敛速度慢问题，但易于陷入局部最优解。为了解决局部最优解的问题，2012年，Zhang等[43]在蚁群算法中引入了惩罚因子，以保持AUV与障碍物之间的安全距离，并结合四叉树算法进行二维水下路径搜索，实现了动态避障，且不易陷入局部最优解。基于先前的研究，2013年，Zhang等[44]又用八叉树算法取代四叉树算法，从二维空间延伸到三维空间。与障碍物保持安全距离的同时，完成了AUV对水下三维空间的搜索要求，但是搜索空间从二维拓展到三维环境下易出现搜索效率低、时间长等问题。对于三维环境下搜索时间长的问题，文献[45]提出一种混合算法对AUV进行全局路径规划，采用新的遗传蚂蚁混合策略，保留精英遗传算法和最大最小蚂蚁算法，在三维空间的复杂环境中也可以较快收敛到最优路径，但由于未考虑实际海流的影响，导致仿真环境与实际工况存在一定偏差。因此，需要考虑大范围海洋环境中海流对AUV能耗的影响。2016年，Liu等[46]提出一种改进蚁群算法，考虑海流等环境因素对AUV能量的影响，采用路径能耗的倒数作为路径信息素值，用能耗值指导蚁群进化，相比改进前的算法，路径不一定最短但能耗显著降低，对降低AUV能耗、提高续航能力有一定的优势。2019年，袁汪凰等[47]针对蚁群算法易陷入局部最优且收敛速度慢的问题，做出进一步研究，提出动态学习机制的双种群蚁群算法。引入奖惩模型，奖励算子提高算法的收敛速度，惩罚算子增加种群的多样性。该算法能以较少的迭代次数取得最优解或接近最优解。2019年，针对AUV海底地形环境中的三维路径规划问题，张楠楠等[48]提出一种适用于全局路径规划的改进蚁群算法。通过对启发函数、信息素更新方式等改进有效克服了传统蚁群算法收敛速度慢、容易陷入局部最优的缺点，并将路径的长度和路径的光滑度同时作为评价函数，减少AUV能量的消耗，使算法更具备实际工程意义。

3.2.3 遗传算法

1975年，Holland在其出版的Adaption in Natural and Artificial Systems一书中首次提出了遗传算法（genetic algorithm，GA）的概念。GA的优势在于它可以根据搜索过程中当前搜索的最优值找到全局最优值[49]。文献[50]将传统遗传算法用于AUV的路径搜索，发现GA算法可以应用于AUV在线路径搜索和动态避障。但其缺点是收敛速度慢，稳定性差，处理时间过长。处理时间长是所有生物智能算法的一个共同弱点。

针对遗传算法自身存在的不足，研究者们提出许多改进的算法。文献[51]在基于遗传算法的基础上加入弹性网格概念，以减小算法搜索空间，提高路径规划效率，与传统遗传算法相比，收敛速度和运行效率得到改善。无人潜航器通常工作在复杂多变的海流中，由于海洋环境的特殊性，在设计路径规划算法时需要将海流、复杂障碍物等环境因素对AUV的影响考虑进来。文献[52]在AUV路径规划中考虑到海流对AUV能量的影响，将海流因素作为遗传算法的评价因子，将遗传算法和粒子群优化算法相结合应用到AUV的全局路径规划中，减少AUV在大范围海洋环境中航行时的能量消耗。为提高AUV的续航能力，必须将其在运输过程中的能耗降至最低。2014年，Tanakitkorn等[8]在遗传算法的代价函数中加入AUV动力学估计的能量消耗项，针对二维静态环境下基于网格的遗传算法的路径规划，提出一种改进的代价函数，有效减少AUV能耗。针对AUV水下导航控制精度下降以及稳定性变差等问题，2017年，张磊[53]采用遗传算法优化模糊控制器来提高系统鲁棒性，在时变连续海流干扰和定常非连续海流干扰下，通过路径跟踪误差曲线可知，基于遗传算法优化的模糊控制的路径跟踪标准误差为0.258 m，常规模糊控制的路径跟踪标准误差为0.372 m，在海流大小改变之处的误差对比尤为明显，可见基于遗传算法优化后的模糊控制器对AUV路径跟踪控制具有更好的稳定性和控制精度。为了解决大范围海洋环境中AUV高效避障问题，2019年，Yan等[54]在改进遗传算法的基础上建立避障模型，结合实际应用问题进行研究，结果表明，改进的遗传算法模型不仅可以满足转弯角度的要求，避开障碍物，而且在满足AUV运动特性的前提下，明显缩短路径规划时间和路径长度，节约AUV运行能耗。针对三维路径规划问题，2020年，何光勤等[55]基于遗传算法对三维环境下的航迹进行路径规划，设计带有惩罚的代价函数，生成短而平滑的路径的同时，高效完成路径规划任务，为各种实际任务提供技术支持。

3.2.4 萤火虫算法

萤火虫算法（firefly algorithm，FA）是一种自然启发式算法，源于萤火虫群体行为的简化和模拟[56]。与其他群智能算法相比，萤火虫算法凭借算法参数较少、操作简单，且具有较高的寻优精度等优势，已广泛应用到AUV的路径规划中[57]。针对AUV路径规划多目标优化问题，2013年，董静[58]结合萤火虫算法独特的优化机制，提出一种多目标萤火虫优化算法。引入Pareto支配的概念以区分萤火虫亮度，采用外部档案保存算法产生Pareto最优解，并采用自适应神经网格法维护外部档案，最终规划出距离较近且平滑度较好的最优路径。然而，FA算法也存在三维环境下收敛速度慢的问题。针对这一问题，2015年，Liu等[59]提出一种改进的FA来实现AUV的三维路径规划。采用排除算子提高避障效果，并采用收缩算子提高路径的收敛速度和平滑度，该方法收敛速度快，可以在3D环境中找到有效的路径。但由于海洋环境是动态未知的，因此，需要进一步研究如何在真实的动态海洋环境中为AUV设计一条实用的路径。为实现AUV在未知动态环境中自适应导航，2019年，李凤玲等[60]提出一种基于萤火虫算法的AUV路径规划方法。采用单目相机检测机器人周围环境信息，并设计萤火虫算法的适应度函数，让AUV在避开障碍物的同时能搜索最优路径，验证了萤火虫算法在动态未知环境中路径规划的有效性与实时性，具有重要的实际应用价值。

3.2.5 狼群算法

狼群算法（wolf pack algorithm，WPA）是模拟狼群的捕食行为及其猎物分布模式，开发的一种智能算法。利用“胜者为王”的头狼生成规则以及“优胜劣汰”的狼性更新机制，实现在复杂搜索空间中的路径优化[61]。

针对水下导航精度问题，2016年，Shen等[62]提出一种基于狼群算法的改进路径规划方法，结合地形匹配问题对AUV的导航和路径规划进行研究，利用水下地形熵的计算公式以及水下地形信息的分布，通过狼群算法设置仿真参数对规划路线的地形匹配进行仿真，提高匹配精度，验证了算法可行性。2017年，Zhang等[63]通过建立AUV约束条件下的水下环境威胁模型，提出基于修正WPA的Dubins路径规划方法。利用Dubins曲线来满足角度控制约束，调整转弯半径来满足控制约束。改进后的WPA收敛速度快，局部搜索能力强，搜索时间减少6.3%，搜索路径减少57.3%，但改进的狼群算法中需要设置的参数比其他方法多，相对复杂，计算成本大。针对上述存在的问题，2019年，王盈祥等[64]提出一种基于差分进化的改进狼群算法（differential evolution wolf pack algorithm，DEWPA）。通过引入探狼搜索因子、猛狼最大奔袭次数、自适应围攻步长、差分进化策略等对传统狼群算法进行改进，在降低算法计算成本的同时提高算法的全局搜索能力。考虑到大范围海洋环境中，海流、复杂障碍物等环境因素对AUV路径规划的影响，为了降低执行成本、减小能耗，AUV必须确定一个时间或能量的最优位置。2020年，Panda等[65]提出一种新的狼群算法用于AUV的路径规划，通过对静态障碍物进行三维网格化仿真，基于计算时长、路径长度和路径代价对结果进行比较分析，改进的狼群算法降低操作成本，生成了低功耗、无碰撞的最优规划路径。狼群算法收敛速度快和求解精度高，同时在求解策略上能够较好地兼顾对解空间的全局和局部开发，因而具有优良的寻优性能。WPA及其改进算法不同特性分析如表5所示。

Table 5 Characteristic analysis of WPA and improved algorithms表5 WPA及其改进算法特性分析

3.2.6 人工神经网络算法

人工神经网络（artificial neural networks，ANN）是一种受生物神经网络功能的运作启发而产生的算法数学模型，具有强大的自学习和自适应能力。因此，在AUV路径搜索中存在许多应用[66-67]。然而，ANN算法也存在处理时间长、计算效率低等问题。针对上述问题，2016年，Ni等[68]基于生物启发式神经网络（biologically inspired neural network，BINN）提出一种改进的AUV路径规划算法，该算法对神经网络模型的分流方程进行了改进，以解决3D水下环境中AUV的实时路径规划问题，有效避障的同时提高了算法的计算效率。此外，人工神经网络算法易与其他算法相结合。因此，其改进算法以及与其他算法的结合就成为路径搜索领域的热门话题。为了解决AUV“太靠近”障碍物和路径优化的问题，2018年，Cao等[69]提出一种势场生物启发式神经网络（potential field bio-inspired neural network，PBNN）算法，通过生物启发神经网络算法用来规划实时无碰撞路径，引入势场防止AUV“太靠近”障碍物，在点对点路径规划中引入引力势场来优化路径，从而实时规划出安全平滑的路径。考虑到突发障碍物的影响，文献[70]提出一种三维生物启发式神经网络模型进行动态规划与避障，有效地促使AUV自主避障，自适应地规划出一条无碰撞的行驶路径，实时性较好，但并未考虑实际海流的影响，导致仿真环境与实际工况存在一定偏差。因此，在实际水下路径搜索中需要考虑海流对AUV能耗的影响，2019年，Zhu等[71]提出一种改进的多AUV自组织神经网络算法（self-organizing map neural network，SOMNN），用于3D水下环境中AUV的实时避障和路径规划，选择不同方位下海流的最短路径，在保证总能耗最小的前提下进行路径规划，获得最优规划路径。ANN及其改进算法不同特性分析如表6所示。

Table 6 Characteristic analysis of ANN and improved algorithms表6 ANN及其改进算法特性分析

3.3 其他算法

近年来，随着对AUV的不断探索与发展，一些新的算法因其优秀特点而被广泛应用到AUV的路径规划问题中来，且取得了不错的效果，这些算法一般都具有较强的路径搜索能力。比如水平集方法（level set method，LSM）、行为策略方法、快速探索随机树算法（rapidly-exploring random tree，RRT）、Dijkstra算法等。

水平集方法应用于路径搜索最大优势在于它可以有效地模拟动态过程，该方法可用于解决水下动力因素引起的问题。文献[72]采用水平集方法来预测AUV在不确定、强、动态海流中的时间最优路径，同时应用偏微分方程控制随机时间的最佳可达性来确定时间最优路径。快速探索的随机树算法具有强大的空间搜索能力，广泛应用于AUV的路径搜索。RRT算法可以收敛到最优解，可以在二维环境中实现AUV的路径搜索，并且可以解决多维环境中的路径搜索问题。Carreras等[73]采用RRT算法有效解决AUV路径规划问题，在受到微分约束的无碰撞运动的情况下，通过运动学方程获得新的状态从而生成更可行的求解路径，在真实复杂的水下环境中具有很好的适应性。针对AUV全覆盖路径规划问题，甘文洋等[74]提出一种基于行为策略的规划算法，构建栅格信度函数区分环境信息，引入行为策略确保AUV自动避开障碍物，该算法在二维和三维环境下能够完成AUV的全覆盖任务。

4 总结与展望

AUV路径规划算法在水下自主导航中占据重要地位。本文将常用AUV路径规划算法分为环境建模方法和路径搜索算法两类，详细介绍了AUV路径规划算法的研究现状并分析了各算法的优缺点，阐述了这些算法的基本工作原理和应用范围，比较了它们的实时性、算法的复杂性、环境适应性和规划路径的平稳性。分析发现，在面对复杂的三维海底动态环境时，如何提高算法在海流、复杂障碍物等三维海洋环境中的实用性，从而实现高效避障和节约能耗是AUV路径规划的重中之重。

随着科学技术的不断发展，人们对AUV路径规划的研究已取得巨大的成果，但由于面临的海洋环境日益复杂，对AUV路径规划技术的要求也越来越高。因此，寻求最优规划路径，响应复杂环境的变化将成为未来AUV路径规划算法发展的重点。从已有的研究成果看，AUV路径规划算法将会朝以下研究趋势进行发展。

4.1 AUV路径规划算法的智能化发展

海洋环境复杂多变，充斥着湍流、涡流等强瞬态自然现象，传统的路径规划方法很难实时抵抗这些强时变、强非线性现象所带来的干扰，并且AUV自身的动力学模型和环境信息难以进行公式化的精确描述。以上问题使得基于环境模型的路径搜索算法在复杂海洋环境下很难精准规划，而以深度强化学习（deep reinforcement learning，DRL）等为代表的新一代人工智能算法，不依赖环境模型且具有较强的自学习能力，可以更好地解决水下机器人在未知环境下的实时路径规划问题。例如通过借助DRL算法的感知决策能力，实现AUV对复杂海洋环境的理解并做出智能决策，从而实现由海洋环境到AUV运行行为的端到端控制。同时，可以利用启发式回报函数的设计来提高算法的搜索效率，解决路径规划算法收敛速度慢的问题。伴随着深度强化学习网络的发展，未来有望彻底解决水下机器人无先验环境知识下的局部路径规划问题。因此，将新兴的人工智能算法应用于AUV的路径规划中，进一步提高AUV的智能化水平将成为未来发展的重点。

4.2 AUV路径规划算法的融合

目前，AUV路径规划算法的研究已经取得了重大进展，但在每个具体规划算法中还存在一些不足，因此路径规划领域的重点依然是新的高效的路径规划算法和融合算法的研究。近年来，随着一些新的算法（技术）逐渐应用到路径规划中来，这种互补式的算法融合也促使了各算法的发展，通过取长补短，从而产生出一系列更为优秀的算法。例如将机器学习与群智能算法结合应用于AUV路径规划中，可以有效地克服群智能算法易陷入局部最优解的问题，同时解决了AUV路径规划过程中的死区问题。这种机器学习优化技术也可以应用于其他智能路径规划算法，使得AUV路径规划算法体系更加完善，从根本上解决AUV路径规划算法的局部最优问题，使得AUV水下探索的应用前景更加广阔。

4.3 向广域探测的AUV远程化方向发展

来自于科学需求的牵引使得长航程AUV成为很多科研机构研究的热点，但在现阶段，长航程AUV的发展主要受能源、多变复杂海洋环境等因素的约束。能源是影响AUV航行距离的一个重要因素。通过智能算法根据外部环境与AUV自身能源水平来评估任务完成的可能性，无疑将是AUV长时间作业的关键。例如利用模糊逻辑法来实现水下实时路径规划时，可以设计关于潜航器剩余能量的隶属度函数并结合专家经验给出规则表，通过查表根据剩余能量来决定规划时潜航器的线速度和角速度，这必然有助于AUV开展远距离、大尺度的海洋环境观测以及海底资源探测等作业。此外，海洋中所蕴藏的潮汐能、波浪能、海流能、温差能、盐能等可再生能源的智能采集和利用也将是未来AUV远程化发展所要探索的一个新方向。

4.4 多AUV协作路径规划算法的研究

多AUV协作并不是多个单元的机械式组合，而是以作业任务为牵引，设计集群系统算法策略。随着AUV作业范畴的不断扩展以及作业任务日益复杂化，单个AUV往往很难高效完成人们制定的任务，多AUV并行协作就成为解决此类问题的重要方式。然而，由于海洋环境的复杂性以及水下通信的困难度，极大地提高了多AUV协作路径规划的难度，而以深度学习、强化学习等为代表的新一代人工智能方法在图像处理、机器人控制等领域的性能优势就为多AUV协作路径规划提供了一个新方向，但也应该清楚地认识到人工智能方法的脆弱性。为了使新一代人工智能方法更好地融入到多AUV路径规划中，需要以作业任务为中心设计路径规划算法，将复杂任务进行分解，在核心处理步骤中构建适合的智能算法，对提高集群整体路径规划的可行性和系统的稳定性具有重要的研究价值。