智能水下机器人是集成人工智能、目标探测与识别、数据融合、智能控制以及导航通信等多子系统的水下无人平台，在海洋开发、水下作业、深海探测、援潜救生等领域有广泛的应用前景。路径规划技术是智能水下机器人的关键技术之一，指在包含障碍物的水域环境内，按照一定的评价标准，寻找一条从起始状态到达目标状态的无碰撞路径，路径规划技术在一定程度上标志着水下机器人智能化程度的高低。从规划的目标范围来看，可以分为全局路径规划和局部路径规划。从规划环境看，可以分为静态路径规划和动态路径规划。

相比于其他移动机器人，水下机器人任务环境是大范围三维空间，水下环境的复杂性增大了规划的难度，同时还要考虑机器人位置、能耗、自身姿态和运动约束等。本文针对水下机器人的环境特点，根据具体算法和策略，阐述了从传统到智能各种典型方法的原理。传统方法包括基于路线图构建法的路径规划方法、单元分解法、A*和D*算法以及人工势场法，智能方法包括基于群智能的路径规划方法和基于机器学习的路径规划方法，介绍了各种方法的应用原理以及在水下机器人路径规划系统的具体应用现状，分析了各种方法的优缺点和关键技术，重点论述了智能算法的研究现状，最后展望智能水下机器人路径规划未来的研究方向。

一、传统路径规划方法

⒈路线图构建法

⑴可视图法

可视图法最早由Lozano和Wesley提出，如图1所示。

图1 可视图法

可视图法将机器人视为一点并将障碍物视为平面内多边形，然后连接起点、目标点以及多边形障碍物的各个顶点，同时要求所有连线与任何障碍物都不相交即所有路径都是无碰撞路径，最后形成一张可视图，然后采用某种算法搜索最优路径。这种方法原理简单容易实现，规划时间随障碍物密集程度增减，虽能寻找最短路径，但缺乏灵活性，路径通常靠近障碍物顶点和边缘，且不适用于高维空间。

⑵Voronoi图法

Voronoi图法是将空间分成n个多边形区域，并且具有如下特点：给定一组点{p1，p2……pn}，每个区域仅包含一个点pi，且pi所属区域内的点比任意pj≠pi更接近pi。图2为由Voronoi算法生成的路径图，点代表障碍物，线条代表路径，它是距离至少2个障碍物相等的点的集合，可见Voronoi图法与可视图法有较大区别，Voronoi图法能够规划出距离障碍物尽可能远的路径，而可视图法生成的是靠近障碍物顶点的路径。

图2 Voronoi图法

⒉单元分解法

基于路线图构建的方法描述简单便于实现，但通常适用于低维度空间的规划问题。目前路径规划技术对机器人环境模型的要求越来越高，路线图构建法无法描述复杂的水下环境信息。基于单元分解的方法能够通过将环境空间分解为子单元，通过附加单元属性信息，从而表达更完整的环境信息。

⑴栅格法

栅格法是目前研究和使用最广泛的路径规划建模方法，它将自由空间划分为无重叠的栅格单元，根据栅格是否被障碍物占据对栅格进行赋值。栅格粒度选取是规划问题关键，粒度越大，模型精确度越高，但同时占用了更多资源。栅格法可以分为精确栅格法和非精确栅格法，如图3所示的梯形栅格分解法属于典型的精确栅格法，每个障碍物顶点做一系列平行线，遇规划环境边缘和障碍物边缘则停止，最终将空间分解为一系列梯形区域。

图3 梯形栅格分解法

⑵四叉树和八叉树

四叉树和八叉树分解法属于非精确栅格法，分别用于二维平面和三维空间的分解。四叉树分解如图4所示，栅格单元通常为矩形，整个环境被分为多个连续的栅格，如果大矩形栅格包含障碍物或边界，则继续分为4个或8个小矩形栅格，直到达到预先设好的精度为止，这种方法可以有效对环境信息压缩，减小储存空间。有关文献分别利用四叉树和八叉树分解法建立平面海域障碍物模型和海底地形模型，除此外还可以将海流速度和方向作为栅格属性信息建立海流模型。此外，相关文献还提出建立包含海流、跃层、声道等更多海洋水文要素的环境模型。

图4 四叉树分解法

⒊A*和D*算法

路线图构建和单元分解法都需要采用搜索算法寻找最优路径，A*和D*算法是目前应用较广泛的路径搜索算法。A*算法是基于Dijkstra改进的启发式搜索算法，如图5所示。

图5 A*算法

通过计算所有候选节点到目标点的估值函数，从而选取最优路径节点，适用于静态路径规划，关键在于建立合适的启发函数。A*算法在面临较大环境空间时搜索效率不足，郭强在仿生鱼路径规划问题中，采用可展开点方法，减少搜索节点，提高了搜索效率，但缺少考虑环境影响因素。Zhou Y等建立局部流场模型，采用时间序列预测方法对深平均流预测，实现了不同规模流场下的路径规划。

此外，A*算法规划路径还存在靠近障碍物边缘的问题，除了膨化障碍物尺寸之外，邓顺平还提出建立障碍物威胁势场并加入适应度函数估计中，虽然路径非最短，但保证了AUV路径安全性。D*算法是动态A*算法，它通过检测最短路径的上一节点或附近节点的变化，适用于解决动态路径规划问题。

⒋人工势场法APF

人工势场法是由Khatib等提出的一种虚拟方法，基于人工势场的路径规划方法将水下机器人在环境中运动视为在虚拟受力场的运动，如图6所示。环境中障碍物对机器人产生斥力，而目标点则产生引力，最后计算合力控制机器人运动，路径不一定是最短但安全平滑。然而，人工势场法也存在局部极小、在相近障碍物前索不到路径以及狭窄环境下摆动大等缺点。针对局部极小问题，一些专家学者不断尝试新的途径，Warren利用人工势场法进行水下机器人路径规划，通过启发知识减小局部极小的情况，实现二维和三维空间下AUV的全局路径规划；Chao W采用最优化理论，将人工势场和障碍约束结合起来，把路径规划问题转化为求解约束和半约束问题；Wang F等将栅格节点作为势场信息单元，通过累计路径栅格点势能完成最优路径搜索，也一定程度解决局部极小点问题。除此之外，Cheng C等采用速度矢量合成算法，使海流速度和AUV速度的合速度指向目标，使资源消耗最小；S.Ferrari和G.Foderaro针对多AUV规避多探测平台网络的协同规划问题，将探测平台视为虚拟障碍物，并通过修改适应度函数，规划结果得到最小暴露率且无碰撞路径。

图6 人工势场法

二、智能路径规划方法

传统路径规划方法主要构建路线和环境模型再通过某种搜索算法规划路径，方法简单便于实现但缺乏灵活性且实时性要求不高，智能路径规划方法主要是将现代的人工智能技术应用于水下机器人路径规划，包括群智能方法和机器学习方法，群智能方法将路径规划问题转化为最优搜索问题，较依赖完全的先验环境知识，而具有自学习能力的机器学习方法不依赖环境模型，可以更好解决水下机器人在未知环境下的局部路径规划问题。

⒈基于群体智能路径的路径规划方法

⑴遗传算法GA

遗传算法由美国Michigan大学的Holland JH教授提出，是一种基于自然选择和自然遗传的最优搜索算法，它的基本迭代过程如图7所示。

图7 遗传算法一次迭代过程

随机产生一个初始种群作为候选解集，通过适应度函数对种群进行评价，在此基础上进行复制、交叉、变异等操作产生最优解。遗传算法全局搜索能力强，但易早熟收敛、局部寻优能力差，一些学者通过结合其他方法进行改进。徐玉如等采用GA-PSO混合规划算法实现了海流情况下的AUV全局路径规划，在GA算法流程内，通过定义特殊算子加入PSO的优化过程，提高收敛速度和执行效率；Hong li Xu等将免疫算法和遗传算法结合，利用抗体群聚类机理维持种群多样性，避免收敛过早，通过细胞克隆操作和免疫记忆增强局部搜索能力和速度；Guo Chang GU等结合模拟退火算法解决局部最优问题。考虑大范围环境AUV能耗问题，Kantapon Tanakitkorn等在遗传算法代价函数中加入AUV动力学估计的能量消耗项，可以有效减少AUV能耗。

⑵蚁群算法ACO

蚁群算法是一种用来寻找最优路径的概率型算法，它由意大利学者Marco Dorigo等提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，可以较好地解决TSP和作业调度问题。以此为基础，很多学者利用其解决水下机器人路径规划问题。王宏健等针对蚁群路径规划不平滑问题，设计了切割算子和差点算子，在二栅格环境模型实现了AUV全局路径规划。当搜索空间从二维环境拓展到三维环境下易出现搜索效率不高问题，潘昕等出基于蚂蚁遗传混合算法，保留精英遗传算法和最大最小蚂蚁算法，在三维空间中的复杂环境也可较快收敛到最优路径。针对路径能耗问题，LIU Guijie采用路径能耗作为路径信息素值，用能耗值指导蚁群进化，相比改进前的算法，路径不一定最短但能耗显著降低。

⑶萤火虫算法FA

萤火虫算法由Xinshe Yang于2008年提出，流程如图8所示。源于萤火虫群体行为的简化和模拟，通过萤火虫个体之间的相互吸引而达到寻优目的。相比其他群智能算法，萤火虫算法具有较高寻优精度和收敛速度，参数较少更易实现，在寻找全局最优解上有较好效果。针对水下机器人路径规划多目标优化问题，董静引入Pareto支配的概念以区分萤火虫亮度，采用外部档案保存算法产生Pareto最优解，并采用自适应神经网格法维护外部档案，最终能够规划出距离较近和平滑度都较好的路径。ChangLiu，Yuxin Zhao等针对三维环境下FA算法收敛慢的问题，根据操作过程对算法参数和随机步长进行调整，采用排除算子提高避障效果并采用压缩算子提高路径收敛度和平滑度。

图8 萤火虫算法流程

⑷生物地理学优化算法BBO

Dan Simon在2008年提出了生物地理学优化算法BBO，它是一种新的生物地理学启发算法，算法原理类似于遗传算法，如图9所示。主要通过物种迁移算子来实现信息资源共享，用以搜索全局最优解。BBO算法相比于其他群智能算法，运算速度但全局搜索能力弱，针对这一问题，有关文献提出利用差异进化算法DE改进BBO，提高了搜索能力，但采用的是线性迁移模型，没有考虑其他模型对算法的影响。Somaiyeh Mahmoud Zadeh等基于BBO算法设计了水下机器人两级递阶任务规划系统，并进行3种场景的仿真实验，结果表明基于BBO的规划算法在实时性上有显著潜力。

图9 生物地理学优化算法流程

⒉基于机器学习的路径规划方法

目前水下机器人路径规划法更多是将路径规划问题转化为搜索问题或者能量最优问题，基于群智能算法在全局路径规划上已经较为成熟，但对实时性要求不高，而机器学习作为目前规划问题的研究热点，它通常将路径规划描述为MDP问题，通过提供相应的数据集以供训练，学习成功后规划时间大幅减小，可以不依赖于环境模型，在解决实时动态规划问题上表现突出。

⑴神经网络NN

神经网络是人工智能最为重要的内容，在水下机器人路径规划中，通常将传感器的数据作为网络输入，以行为动作作为网络输出，通过训练获得网络模型。段群杰等设计了基于模糊神经网络的实时局部行为规划器如图10所示，分别设计避碰和接近行为决策模块，合理选择最终行为并根据失败探测器给出强化信号，通过调整输出变量隶属度中心值调整2个模块的推理规则直至规则库完全确定。近年来还有学者提出利用神经网络表示环境模型，根据神经元输出值来决策出路径点。有关文献提出基于生物启发神经网络的二维环境遍历路径规划方法；SLi将问题上升到三维空间，并考虑不同流速情况，研究河口环境下AUV路径规划问题；在此基础上，Zhu DQ重点研究了突发障碍物情况，利用环境变化导致神经元激励和活性输出值变化，从而输出无碰撞路径点。

图10 行为学习网络结构

⑵强化学习RL

强化学习是一种无监督的机器学习方法，把学习看作试探评价的过程。图11为强化学习过程，环境会根据AUV所选动作产生强化信号，AUV再根据强化信号和当前状态选择下一动作，目的是使累计强化信号达到最高。由于强化学习通过与环境交互进行学习，不需要有标签的样本训练数据，能方便在线实现，因此适用于解决未知环境模型的路径规划问题。徐莉提出将Q-learning应用于AUV局部路径规划方法中，用CMAC网络逼近状态空间和Q函数，采用多步SARSA（λ）算法解决复杂障碍物环境下的局部路径规划问题。针对海流对机器人能耗影响，Gautam U设计了考虑海流的代价函数，并将其转化为奖励矩阵，基于Q-learning算法对AUV三维环境下路径优化；SHENJing等针对未知动态环境下的局部路径规划问题，利用分层强化学习HRL的局部策略更新能力，解决无环境模型的路径规划问题，但是规划速度较慢，还无法满足实时性要求。

图11 强化学习

⑶深度强化学习DRL

强化学习侧重于学习问题的解决策略，而深度学习网络可以对大规模数据提取抽象特征，针对目前机器学习问题面临越来越复杂的任务环境，谷歌Deepmind团队提出结合强化学习和深度学习，即深度强化学习DRL。作为人工智能领域内新的研究热点，深度强化学习不仅在棋牌游戏、机器视觉等领域广泛应用，也开始应用于解决移动机器人局部路径规划问题。在水下机器人路径规划方面，有关文献提出了一种基于DRL的水下机器人避障规划算法，算法结构如图12所示。2个卷积层提取输入状态量特征，重点设计了包含到目标点距离Rdistance、到障碍物距离Rcollisions、终点附近速度Rend以及漂移Rdrift四项回报函数。基于DRL的规划方法研究目前还处于起步阶段，相比传统路径规划方法并无明显优势，但是随着深度强化学习技术的发展，未来有望成为解决复杂动态未知环境下路径规划问题的最有效途径。

图12 基于DRL的避障算法结构

三、结语

复杂动态环境下的路径规划方法是水下机器人关键技术研究的核心内容之一。本文依据路径规划方法的智能程度，从传统到智能总结水下机器人路径规划方法的研究现状和主要优缺点：

⑴路线图构建方法描述简单便于实现，但缺乏灵活性，对三维复杂的水下环境表达能力不足；栅格法是最常用的环境建模方法，关键是栅格分辨率对于规划时效有较大影响，栅格粒度划分与计算复杂度之间难以找到平衡点。人工势场法路径平滑，安全性高算法简单，但易陷入局部极小且在障碍物靠近区域规划效果不好，在针对特殊规划问题如跟踪墙壁等，可以通过增加扩展势场等得到更好路径。

⑵人工智能方法弥补了传统方法的很多不足，基于群智能方法是目前应用最广的路径规划方法，可以解决全局和局部路径规划问题，但普遍存在易陷入局部极小、搜索速度慢的缺点，依赖于基础环境模型构建且对规划实时性要求不高，可以通过算法的互补、并行运算提高搜索效率，最近还有学者提出将机器学习学习和群智能算法结合应用。

⑶基于神经网络的规划方法，样本数据量大且不易获取，但训练成功后规划时间短，泛化能力强，近年提出的生物启发神经网络无学习且自适应，适用于解决动态规划问题。强化学习是机器学习的重要分支，已经被广泛应用于解决局部避障规划问题，在结合深度学习网络之后，将大量的状态输入量压缩，动作选择机制应从有限组动作空间向连续动作空间发展，回报函数的设计也是深度强化学习的重点。伴随深度强化学习网络发展，未来有望彻底解决水下机器人无先验环境知识下的局部路径规划问题。

【作者简介】文/孙玉山 王力锋 吴菁 冉祥瑞，分别来自哈尔滨工程大学水下机器人技术重点实验室和中国船舶及海洋工程设计研究院；第一作者孙玉山，1973年出生，男，教授，研究方向为水下机器人导航、控制和规划系统；文章来自《舰船科学技术》（2020年第4期），参考文献略，用于学习与交流，版权归作者及出版社共同拥有，转载也请备注由“溪流之海洋人生”编辑整理。