自主水下航行器路径规划技术综述及展望*

周 帅 王 征 杨 洋 尹 洋

（海军工程大学电气工程学院 武汉 430033）

1 引言

自主水下航行器（Autonomous Underwater Vehicle，AUV）是一种依靠自身携带能源自主航行，可根据搭载不同的载荷执行多种任务的无人水下航行器（UUV）［1］。AUV 在军事、民用领域运用广泛，能够完成海洋探测、水下设施检查、水雷对抗等多种任务，AUV 的研发已成为各国海洋技术研究的热点［2］。远离母船或岸基平台巡航作业的AUV也会因其导航、控制系统的测量计算能力而制约AUV 的实际效能，其中自主导航与智能控制已成为决定未来AUV 应用的关键技术，本文讨论的路径规划正是这两个关键技术的重要内容。作为体现AUV 与外部环境进行交互的能力的重要部分，路径规划水平是衡量AUV 工作效能、保证航行安全的关键。

2 AUV路径规划技术概述

路径规划就是使AUV 在规定的任务区域内，以一定的衡量依据（如避障、最小转弯半径等）寻找一条从起点到终点的安全无碰撞路径［2］。按照AUV 对航行环境信息的掌握程度可将路径规划分为全局路径规划和局部路径规划［4］。前者根据已知的航行海图和目标点位置等信息，计算出到达目标点并满足一定最优准则的安全路径；后者则根据AUV 自身携带的惯导、全球定位系统等设备获取当前位姿信息，根据前视声纳、多普勒速度仪探测设备获取实时的环境信息，规划出一条避开障碍物由起点或某子目标点到下一子目标点的优选路径［2］。

路径规划一般有以下步骤：第一，建立从外部环境原始形式映射到便于规划的内部抽象模型，使之能够有效地描述AUV 活动空间。第二，设计规划算法，在建立的环境模型中搜索出一条无碰路径。

3 AUV航行环境建模方法

常见的环境表示方法有几何建模法（可视图法、维诺图法、特征地图法）、单元分解法（栅格法、八叉树法），其中可视图法、维诺图法除具有环境表达能力外，本身也是一种基于图的搜索算法，拥有独立的路径搜索规则。考虑到实际的AUV 往往在复杂的水下三维环境中航行作业，对上述建模方法重点讨论其在三维环境空间建模的应用。

3.1 几何建模法

可视图法在构建环境模型时忽略AUV 的体积大小，视其为一个点，用不规则的多边形抽象表示环境中的障碍物，再将多边形各顶点与起点、目标点两两之间相连接，去除的连线即得出可视图［5］。一种改进可视图法将障碍物切线图形化，一定程度上解决了规划路径冗余问题［6］。对于规划的路径过于靠近障碍物易导致碰撞的问题，Gal［7］提出了减少构图节点、添加螺旋算法的改进可视图法，加快了计算速度且能够有效避免碰撞，但规划路径会有所增长。Ji-Hong Li 等［8］根据可视图几何理论，利用常规几何体实现了水下三维环境建模。

维诺图是由一组由连接两邻点直线的垂直平分线组成的连续多边形［9］。维诺图法因其通用性被广泛运用于AUV 的水下环境建模。针对维诺图法生成路径平滑性不佳不利于跟踪、距离障碍物较远导致路径非最短等问题，Candeloro［10］在维诺图中引入了费马螺旋段，规划出了由直线和螺旋段构成的平滑路径。

特征地图则以线段、圆弧、多边形等几何元素抽象表示AUV 航行空间的环境特征，并以具体参数在全局坐标系下表示环境中障碍物的具体位置。以该方法建立的模型信息紧凑，位置清晰，便于识别，但另一方面，它不易量化，难以处理不规则障碍。曲镜圆［11］建立了多波束声纳数字模型作为AUV 感知系统，利用特征地图完成了水下环境建模。

3.2 单元分解法

栅格法将AUV 的三维航行空间划分为若干个大小一致的单位立方体，并根据各立方体所处状态（或为自由空间，或为障碍空间）分别将其标记为不同的值。其中单位立方体的大小直接影响模型的精度，单位立方体越小，环境模型精度就越高，但同时存储的数据量将成倍增大，后续规划算法耗时亦将增加。该方法虽简单便于实现，但前提是能够获得原始航行空间的环境信息。通过NOAA、GMRT、JAMSTEC、IHO Data Centre for Digital Bathymetry等［12］高精度的海洋数据库，用户可获得研究所需的海底地形数据。对于未知环境，赵冬梅等［13］融合声纳仿真数据得到基于占有率的栅格地图。邢炜等［14］采用局部占用栅格法，将栅格法建立在AUV 的随体坐标系下，将双前视声纳实时检测到的障碍物信息纳入其中，实现了障碍物的精准定位。

在栅格法基础上提出的单元树法将AUV 的三维航行空间划为八个部分，称为八叉树。将这八个部分按照“自由空间”、“障碍空间”、“混合空间（既有自由空间又有障碍空间）”三种情况分类标记。对于第三种“混合空间”，将其继续划为八个小部分，再将这八个小部分按照相同方式分类标记，以此类推直至划分部分小到预定精度。八叉树法对障碍物边缘的分解作用，减少了模型所需的存储空间。八叉树法缓解了栅格法模型精度与规划效率之间的矛盾，但也存在计算单元之间邻接关系时损失较大的缺点。2003 年，高涛［15］通过八叉树法建模结合距离值传播法实现了AUV 水下三维路径规划。

表1 AUV航行环境建模方法优缺点对比

4 AUV路径规划算法

选择相应的规划算法，在建立的环境模型中搜索出一条无碰路径。通常包括传统规划算法、智能规划算法以及基于机器学习的路径规划算法。

4.1 传统规划算法

20 世纪70 年代开始，伴随着移动机器人的兴起，针对路径规划算法问题的研究逐渐发展起来。常用的传统规划算法有人工势场法、A*算法等。

人工势场法在环境中抽象出一个虚拟力场，环境中目标、障碍对AUV 分别产生的一定大小的引力和斥力，以其合力引导AUV 的运动。传统人工势场法存在易陷入局部最小值以及在障碍物距离目标点较近时可能造成目标不可达等问题。Weerakoon等［16］通过在局部最小值点施加额外的斥力来帮助机器人摆脱。梁献霞等［17］引入了虚拟障碍物，在虚拟障碍物和原有障碍物、目标点产生的合力综合作用下跳出局部极小值点。此外，段建民等［18］借助遗传算法以及填平势场也实现了跳出局部极小值的目的。S.S.Ge 等［19］提出了考虑目标与AUV 距离的改进斥力函数确保AUV 到达目标点。对于更复杂的水下三维环境，郭凯红等［20］综合考量了障碍物形状和目标点距离，并根据速度矢量判断障碍物在AUV 左舷还是右舷，从而合理选择转向，解决了传统的二维平面避障固定转向的缺陷。马小轩等［21］提出了考虑避障半径的优化斥力场函数方法，结合设置子目标点以及距离比较法分别避免陷入局部极小值和目标不可达的缺陷，实现了多障碍物水下三维环境的路径规划。

A*算法通过不断搜索靠近目标点的路径来获得机器人的移动路径。该算法的评价函数包含了实际距离代价函数、估算距离代价函数，其中后者作为启发函数直接决定了A*算法效率的高低。A*算法在栅格地图中进行，可牺牲搜索精度来保证搜索速度，进而在较短时间内找到最优解。为了进一步提高搜索速度，还可以选择跳跃点搜索、双向搜索、带宽搜索等手段。传统的A*算法规划出的路径折线多，且通过障碍物边缘时的避碰可靠性差。为了解决规划可行性问题，于晓天等［22］结合A*算法与模糊控制算法，先通过A*算法在高层栅格地图中进行全局规划，再利用模糊控制算法在底层栅格地图中进行局部规划，最终得到一条平滑路径。

4.2 智能规划算法

传统算法对环境空间变化适应能力较差，采用复杂优化方法则又大大降低了算法通用性。相比较下，智能优化算法能更有效地解决大规模复杂优化问题。常见的智能算法有蚁群算法、粒子群算法、遗传算法、神经网络算法等。

蚁群算法（Ant Clony Algorithm，ACA）因模拟了蚂蚁觅食寻径活动而得名，该算法根据蚂蚁行进时选择信息素浓度高的路径并释放的信息素的正反馈的作用找出最优路径［23］。传统蚁群算法易陷入局部最优、收敛慢甚至停滞。王宏健等［24］建立了蚁群可视图模型，阐明了信息素更新规则及算法步骤，验证了蚁群算法对解决AUV 全局路径规划问题的有效性。温志文等［25］借鉴了非劣最优解集的思想，考虑了路径长度、平滑度、规划时间、安全性等多个评价指标的优化组合，同时采用了趋向位置目标的吸引策略，提高了算法全局寻优能力。俞佳慧等［26］将蚁群算法同贝叶斯网络相结合，改进了转移概率公式及信息素浓度更新策略，提高了算法性能及其收敛性。梁凯等［27］提出了一种基于预测控制理论的方法，他在路径规划过程中加入了滚动窗口，仿真结果表明改进后的算法使机器人具备良好的动态避障能力。刘雨青等［28］基于Dijkstra算法改进了信息素初始化方式，构造了新的启发函数来消除水流导致不同路径点能耗不同的影响，同时利用贝塞尔曲线改善路径平滑性，提高了算法性能，适用于AUV 的路径规划。朱佳莹等［29］在改进蚁群算法的基础上引入粒子群算法路径预搜索优化初始信息素分布，提高了收敛速度和全局搜索能力。

粒子群算法（Particle Swarm Optimization，PSO）源于对鸟群捕食行为的研究，它的基本核心是利用个体的信息共享使得整个群体的运动在问题求解空间中产生从无序到有序的演化过程，进而获得问题的最优解［30］。传统的粒子群算法难以避免收敛精度较低、搜索停滞等问题。严浙平等［31］提出了一种竞争粒子群算法，算法中每个粒子都向着侧重于全局搜索和局部搜索的两个速度方向进化，在得到的两个子粒子中保留较优的子粒子，最终得到下一代粒子种群，将该算法应用于AUV 路径规划中得到了较优路径。贾慧群等［32］通过自适应地调整惯性权重因子和加速因子，同时引入鸡群算法中的更新方程扰动搜索停滞的粒子，使之向全局最优解靠近。改进后的算法在搜索精度及鲁棒性上均有较大提升。

遗传算法（Genetic Algorithm，GA）衍生于染色体选择交叉、基因变异的生物进化机制，它将路径编码为染色体，再根据适应度值保留优秀个体进行迭代，最终得到趋于全局最优路径［33］。传统遗传算法局部搜索能力差、运算效率低。王豪等［34］将路径长度和拐点数量纳入适应度评估，设计了自适应的交叉算子和变异算子，仿真结果表明改进后的算法迭代次数和拐点数更少。文献［35］在遗传算法中引入避障模型提高了AUV 动态避障能力，缩短了规划时间和路径长度。冯豪博等［36］提出了一种基于精英族系的遗传算法，该算法将迭代产生的精英个体标记为多路径规划结果，实现了AUV 集群最优多路径规划。文献［37］将海流对AUV 航行耗能的影响考虑到适应度函数中，提出了一种遗传算法与粒子群算法相结合的全局路径规划算法，降低了AUV 在大范围海域航行能耗。潘昕等［38］提出了一种遗传蚁群混合算法，通过遗传算法生成初始全局可行解弥补了蚁群算法初期信息素匮乏导致求解效率低的缺陷。俞炅旻等［39］设计了利用遗传算法优化隶属度函数的模糊控制器，实现了AUV 在未知水下环境的局部路径规划。

神经网络能够并行处理、分布式储存大量数据信息，能够在问题内部规律未知情况下实现网络从输入状态空间到输出状态空间的映射。神经网络中神经元与环境模型中位置单元一一对应，环境中障碍物信息作为输入，通过神经元之间连接和计算最终得出一条较优路径。刘成良等［40］提出了一种结合碰撞函数的神经网络算法，并通过仿真实现了机器人无碰撞路径规划。朱大奇等［41］建立了三维生物启发神经网络模拟水下三维环境，并根据神经元活性输出值分布情况得出了较优路径，验证了神经网络模型在AUV 三维路径规划的可行性。郝启润等［42］提出了一种结合A*算法与离散生物启发神经网络的算法，实现了AUV 在未知环境的实时路径规划。

除上述智能规划算法外，还有学者研究了入侵野草优化［43］、萤火虫算法［44］、狼群算法［45］等智能算法在AUV路径规划中的应用。

4.3 基于机器学习的路径规划算法

强化学习是智能体通过与环境的交互学习策略并迭代使累计奖励值达到最大的方法，该方法无需先验知识，适合解决AUV 在水下环境的路径规划问题［46］。刘和祥等［47］基于前视声纳信息采用Q-learning 算法在半实物仿真中实现了AUV 的局部路径规划。针对动作空间、样本空间维数增大导致算法收敛性变差等问题，冉祥瑞［48］提出了半马尔可夫决策过程，通过任务分层缓解了强化学习的“维度灾难”，提高了AUV 在水下环境的自适应能力。

深度强化学习利用神经网络拟合了Q 值表解决了状态-动作空间过大的问题，兼具了深度学习的感知能力与强化学习决策能力，更加适用于AUV 大范围水下三维环境的路径规划［49］。Yukiyasu 等［50］利用深度强化学习方法实现了AUV 在各种海底环境在线学习的路径规划。Prashant等［51］通过神经网络处理空间连续问题，提高了算法学习速度。卜祥津等［52］采用Asynchronous Advantage Actor-Critic算法训练机器人路径规划，根据机器人避障需求切换状态，优化了状态空间，提高了学习效率。张士伟等［53］提出了Actor-Multi-Critic 算法，多个评论家根据不同标准对AUV 动作进行评分，克服单一评论家评价耦合的问题，仿真结果表明该算法可满足AUV 动态路径规划实时性和可靠性的要求。

表2 各类规划算法的特性分析

5 结语

本文立足于无人水下航行器路径规划技术发展现状，以环境模型建立和规划算法为重点，概述了各类建模方法、规划算法原理及应用，对比分析了它们各自的适用范围及优缺点并针对其弱点提出了改进方向。研究发现，栅格法因其建模过程简单、便于执行计算而应用最广，但目前仍难以平衡栅格分辨率与计算效率。基于群智能的规划算法在大规模优化问题以及复杂环境适应问题上优于传统规划算法，能够较好地实现全局或局部路径规划，但也存在动态规划能力不足、求解精度与收敛速度难以兼顾等问题。深度强化学习不依赖环境模型和具体的求解规则，具备在线学习、自主学习的能力。近年来提出的近端策略优化算法［54］（Proximal Policy Optimization，PPO）可处理高维状态空间和实现连续动作控制，在解决复杂水下三维环境的局部路径规划问题上具有较大的潜力。还有学者提出将深度强化学习与群智能算法相结合，在保证较强动态规划能力的基础上提升全局规划能力，也成为新的研究方向。

当前，AUV 在军民领域执行的任务呈现多样化、复杂化的特点。根据不同任务场景需求，例如在广阔海域覆盖搜索、围捕目标，在近海底空间考虑地形海流、躲避水下监听威胁等，有针对性地建立充分表达环境的模型，设计适合解决该问题的路径规划算法逐渐成为研究的重点。为了弥补单一AUV 无法胜任复杂任务的缺陷，实际任务通常由异构的AUV 集群协同执行，利用深度强化学习协同规划AUV 集群的无冲突作业路径也成为当下研究的热点。随着深度强化学习网络的发展以及合成孔径声纳等设备的开发应用，AUV 在复杂任务场景下的路径规划问题有望得到彻底解决。