海洋测量是海洋测绘的重要组成部分，主要包括海洋大地测量、海道测量、海底地形测量等^[1]。自治水下机器人(AUV)和无人艇(USV)等海洋自主航行器(autonomous marine vehicle, AMV)对所探测的任务区域海底地形测量时需要进行高效全覆盖扫描^[2]。然而，海底地形往往存在大量复杂的起伏变化的山脊和沟壑^[3]。文献[4]为了克服复杂深海海底地形测绘问题，提出了根据海底地形坡度大小，通过利用混合决策模块有机协调平面测绘、螺旋测绘两种算法来实现AUV海底地形的三维全覆盖扫描。文献[5]则利用切片投影法将三维海底地形简化为若干层二维切片并投影到平面上，从而将三维海底环境中全覆盖地形测绘路径规划问题转化为二维环境中的AUV完全遍历路径规划问题。文献[6]对二维浅水岛礁海域USV自主测绘时存在的任务计算量大、场景复杂等问题，提出了一种考虑主动方向的动态栅格法与启发式完全遍历路径规划。在以上将复杂的三维海底地形转化为二维海底地形方法的基础上，本文对二维平面内的完全遍历路径规划进行研究，用于实现AMV深海多海湾或浅水多岛礁区域地形测绘和水文信息的采集工作。

二维环境下，AMV完全遍历路径规划^[7-8]需满足两个指标：遍历性和不重复性。所谓遍历性是指AMV的运动轨迹需要最大限度地遍布其可达任务空间^[9]，它反映的是AMV的工作质量问题；所谓不重复性是指AMV的行走路线应尽量避免重复^[10]，反映的是AMV的工作效率问题。目前，AMV完全遍历路径规划采用较多的算法有人工势场法、遗传算法、神经网络算法和启发式算法^[6]等。

人工势场法^[11]是通过设置势场函数，AMV在势场吸引力和排斥力的相互作用下向目标点移动。例如，文献[12]利用声呐获取的环境信息构建栅格化的AMV周围局部环境模型，并利用人工势场法顺序奔向各个栅格内目标点来实现完全遍历路径规划。但是，人工势场法的缺点在于一旦地形过于复杂，AMV完全遍历路径规划有可能陷入局部最优解，进而产生遗漏区域。遗传算法^[13]采取群体搜索策略以及在群体中个体之间的信息交换，是一种多点、隐含并行搜索算法，非常可能搜索到全局最优或者近似最优解，而不会限于局部最优。例如，文献[14]在二维环境下，为基于网格化的遗传算法提出了改进的代价函数，减少了AMV完成特定任务的耗能。但是，此算法搜索效率较低，面对复杂多变的海底环境较难达到遍历性要求。

文献[15]为避免生物激励神经网络出现随机性选择和重复覆盖多的缺陷，在遍历过程中遇到“死角”时，采用蚁群优化算法实现AMV以最优路径跳出“死角”，并经过仿真试验验证。结果表明：该方法覆盖率高，重复率小，在复杂环境条件下实用性较强。但是，神经网络算法需要事先采集足够多的训练样本数据对算法模型进行训练，并不适用于未知复杂海底区域的在线实时地形覆盖扫描任务的要求。

多海湾地形是指有多于两个海湾的封闭区域，此种地形多存在于岛礁海域和深海复杂地形区域^[16]。多海湾地形下，AMV单纯采用上述复杂算法可能会对完全遍历路径规划中重复搜索和遗漏搜索问题有所优化，但需要较大计算量和先验知识，并且以上算法并没有考虑载体地形全覆盖搜索耗能问题，不具备很好的实用性。

简单锯齿形完全遍历路径规划算法^[17]是一种简单、计算量小、实用性强和对先验地图信息依赖性低的二维完全遍历路径规划方式。然而，由于多海湾地形区域边界复杂性以及受到海流影响产生的偏离期望航线等影响，将此算法直接应用于AMV完全遍历路径规划中，并不能达到很好的遍历性和不重复性。为了实现多海湾地形下AMV全覆盖区域搜索达到较好的遍历性和不重复性，并兼顾降低AMV搜索耗能，本文在简单锯齿形完全遍历路径规划算法基础上做出了以下工作：

(1) 通过分析重复区域和遗漏区域的特征，提出了基于声呐传感器感知信息^[18]的重复海湾和遗漏海湾及其入口点、出口点和门户的路径规划环境表达。

(2) 根据提出的环境表达模型，设计了基于锯齿形行为、遗漏海湾搜索行为和重复海湾搜索行为的路径规划算法。

(3) 针对定常流场下的二维多海湾地形进行了基于行为的路径规划仿真，进行了AUV直航耗能、转向耗能和电气设备耗能的估算，通过USV湖泊水域试验验证算法的实用性。结果表明基于重复海湾和遗漏海湾搜索行为的路径规划在多海湾复杂地形条件下具有一定的优势。

1 问题描述 1.1 假定条件

为简化海底路径规划的难度，本文按常规方法将三维海底地形进行切片分层，再将分层后的区域做投影，进而得到海底地形的二维路径规划地形图，并且本文对AMV有如下假定：

(1) 假定AMV具备测绘地形、躲避障碍物^[19]及导航定位能力^[20]，并忽略不同攻角和漂角下水流对AMV直航阻力和转向阻力的影响。

(2) 假定海洋航行器为一个运动质点，并具有沿着期望路径直航和转向的能力。

(3) 假定海洋航行器在线实时测绘的多海湾区域为无全局地图信息区域。

1.2 遗漏海湾与重复海湾

AMV在开阔水域搜索时，一般会选择计算量要求小的锯齿形路径规划方式获取相关水域的水文信息。利用这种简单锯齿形搜索方式对二维规则边界的地形可以达到期望的覆盖率和较短的航程。如图 1，选定一个靠近搜索水域一侧的边界作为起始点S_p，建立直角坐标系，并根据AMV附带声呐的探测宽度w以及考虑到海底地形起伏对探测设备的地形覆盖搜索宽度的影响，利用栅格法建立任务环境地图。纵向栅格线的横坐标值规定为x=iw/2(i为栅格线编号，栅格线间距为w/2)。AMV从起始点开始沿着栅格线运行，每当AMV声呐探测到边界时，AMV将会向着x轴正方向转向，沿着水域边界寻找下一条栅格线。寻找到下一条栅格线后，AMV将沿着这条栅格线搜索下去，直到搜索完全部区域为止。

将AMV整体趋势向x轴正方向在栅格线上往返前进的行为定义为锯齿形路径规划行为。真实情况下的AMV是边行走边建立栅格线的，为了说明方便，在此将栅格线提前全部画出，并且因为AMV有时需要靠近边界获取光学图像或者近距离观察水中生物，本文中AMV沿边界航行时，其与边界的距离相对于声呐探测距离要近。

当搜索水域存在多海湾以及海岛时，路径规划算法一般先将搜索水域进行分块化处理。分块化处理是指根据海岛分布情况将环境空间划分为一系列不重合的、有限个无海岛的多海湾子区域，然后在此基础上对每个子区域进行遍历覆盖搜索。简单的锯齿形路径规划行为将会导致搜索遗漏或者重复搜索现象。如图 2，AMV从S_p点出发，使用上述行为进行搜索，搜索完中间区域后进入I₂区域，搜索完I₂区域后，AMV将沿着I₂区域内的栅格线返回，然后再进入I₃区域，搜索完I₃区域后会发现：在整个搜索过程中I₂区域重复搜索而I₁区域被遗漏。本文将AMV遗漏的海湾区域I₁定义为遗漏海湾，而重复搜索的海湾区域I₂定义为重复海湾。

2 基于重复海湾和遗漏海湾的搜索行为设计 2.1 遗漏海湾进入点

判定遗漏海湾进入点需要根据AMV探测到海角时所处栅格线L_i与海角边界曲线位置关系。分为两种情况(如图 3)：一种是海角边界与栅格线相交；一种是栅格线不与海角边界相交。

第1种情况如图 3(a)所示，假定AMV沿着栅格线运L_i动，在C₁点声呐探测到区域边界，它将沿着边界运动到C₂点，C₂点同样是处在L_i栅格线上，且自C₂点以后部分的栅格线仍处于搜索区域内，而直线段上任意一点都处在搜索区域外，那么就可以确定一个海角k=(C₁, C₂)，C₁和C₂两点就是海角点，C₂点就是海湾进入点E_I；第2种情况如图 3(b)所示，AMV声呐探测到栅格线L_i-1与边界第一个交点C₁后，它将记录此点位置，然后继续沿着L_i运动，当探测到线段的第2个端点C₂时，AMV将会确定C₂为遗漏海湾进入点。

2.2 重复海湾退出点

如图 4，假定AMV沿着栅格线L_i运动时探测到曲线边界，它将记录此边界，但并不改变其自身的航行方式进入海湾，AMV找到湾底(确定湾底的方法是AMV沿海湾边界航行，最终回到上一次经过的栅格线L_i+3，那么此栅格线和边界组成的部分即为湾底)时，确定为海角边界，此区域为重复海湾，C₄是重复海湾的退出点X_I，则为重复海湾的门户。

2.3 搜索行为设计

当AMV确认一个遗漏海湾后，AMV将自动记录下进入点E_I的位置并进入遗漏海湾，然后它将沿着遗漏海湾的边界航行，当找到湾底时，AMV启动锯齿形路径规划行为扫描遗漏海湾区域，接着AMV到达遗漏海湾的门户，AMV所处的位置可能是进入点E_I，也可能是退出点X_I。那么进入点和退出点所组成的线段就是遗漏海湾的门户。当AMV到达遗漏海湾门户时，不论是处在遗漏海湾的进入点E_I还是退出点X_I，为了确保门户所在的小区域被扫描过，AMV将沿着门户的线段的一个端点航行至另一个端点，到达另一个端点后，AMV将锁定这个遗漏海湾，将其看成实体，整个路径规划过程定义为遗漏海湾的搜索行为。

根据2.1节遗漏海湾进入点确定方式不同，遗漏海湾搜索结束行为也存在不同。如图 5(a)，第1种情况确定遗漏海湾进入点E_I时，AMV完成遗漏海湾区域搜索并走完门户路线后，它将沿着遗漏海湾门户所处的栅格线继续航行并对下一区域进行覆盖搜索；如图 5(b)，第2种情况确定遗漏海湾进入点E_I时，AMV搜索扫描完遗漏海湾后，将重新回到其切换点R，然后继续航行搜索下去。

当AMV以锯齿形路径规划行为到达重复海湾湾底后，重复海湾及其退出点被确认，AMV将直接回到重复海湾退出点，然后重复海湾门户将会被锁定，重复海湾将会变成实体区域。这种行为定义为重复海湾搜索行为，具体过程如图 4所示。然后，AMV再切换回锯齿形基本行为搜索下一个区域。

基于重复和遗漏海湾搜索行为的AMV完全遍历路径规划算法流程如图 6所示。遗漏海湾一般是先确认后探测，AMV确认其遇到的海湾为遗漏海湾后，为了不遗漏此区域，它将在确认遗漏海湾后立即进行探测。而重复海湾则是先探测后确认，这样做的目的是为了降低重复海湾的重复搜索的可能性。另外，为了保证AMV在完成整个区域搜索后不再重复搜索，还需要对整个路径规划行为定义一个终止条件。AMV探测地形的过程可以看作是一个二维地形图像区域生长^[21]的过程，一旦地形图中的边界线完成封闭，那么封闭边界线内的区域也同时被完全覆盖探测，此时可认为整个搜索的路径规划终止。

3 仿真试验 3.1 仿真环境设定

根据上述的环境表达以及各个路径规划行为，在图 2二维地形下条件下，利用AUV进行算法的验证，用MATLAB进行基于行为路径规划仿真。该地形的横向最大距离为1600 m，纵向的最大距离为1100 m。

在实际情况下，AUV工作的海底一般存在海流，海流对路径规划的影响不能忽略^[22]。为此，本文为图 2地形设定了一个网格化的定常流场(图 7)，单元网格为边长200 m的正方形。在此区域中曲线段、、和为海流不可穿越的实边界，若海流遇到实边界将会产生分流或者回流；线段、、和这4条曲线段为海流可穿越的虚边界。设置曲线段和为海流的速度入口，和为速度出口。将速度不为0的网格区域进行编号，未编号的网格区域海流流速为0。其中，在11号网格发生分流现象，在网格16号海流发生合流，在17号网格海流发生回流现象。1号、8号、26号、30号、31号和32号网格为海流入口，其流速分别为0.1、0.1、0.05、0.04、0.05和0.05 m/s。规定海流流向角为将正方向x坐标轴沿逆时针旋转到流速方向所走过的角度，每个网格内的海流的流速和流向角用网格中心点处的海流流速和流向角来代替。如果网格中心点不在此区域内，且网格与边界的交线为实边界，则认为此网格内的流速为零。

同时对AUV航迹进行网格划分，航迹小网格为海流网格四等分正方形，使AUV航迹尽可能的经过海流网格中心区域，并将小网格内的航迹由曲变直，以便近似估算AUV在每个海流网格内所受的阻力以及航程，从而计算每个网格内的运动耗能。

此AUV搭载有负责直航的主推进器和转向的侧推进器，能够同步独立地分别进行直航和转向。为保证AUV路径跟踪的精度，将直航速度设定为相对大地坐标系下的恒量(v₀=0.23 m/s)，并将AUV左右两侧声呐探测范围假定为400 m宽的带状区域，那么栅格线间隔为200 m，最终得到7条纵贯任务区域的栅格线。从AUV消耗能量的角度来评价基于行为的路径规划方式的性能。

如图 8，因为AUV直航速度设定为相对大地的恒量速度，那么AUV在每个海流网格内所受的阻力就会随着AUV迎流速度的变化而变化^[23]。为此，需要计算AUV在每个航迹小网格相对于海流的直航速度V_i，再由此速度计算AUV所受直航阻力f_i，进而获得每个小网格内的耗能。直航总耗能计算公式如下

式中，v_i为第i个小网格内海流速度；φ_i和θ_i分别为第i个小网格内AUV的航向和海流方向角。式(2)为AUV直航阻力函数^[24]，W_直航为直航总耗能，单位为焦(J)；N为航迹经过的小网格数量，l_i为第i个网格内直线航程，单位为米(m)。

AUV在转向过程中，迎流面积的变化产生的额外阻力会消耗一部分能量，并且转向次数越多，AUV的转向侧推进器同时会消耗更多的能量。为了简化计算，假定AUV在回转过程中所受阻力值f_i只与其所处的航迹小网格内的相对于海流直航速度有关，忽略其他影响因素。在航迹离散化中，文中将每个小网格内的航迹由曲变直损失了一部分航程，所以在计算转向耗能时，可以将这部分损失的航程算作小网格内的转向弧长S_i。在此，本文根据经验规定回转半径为5倍艇长(r=20 m)，所以回转航程就只与两个单元格中航迹角度的差值Δθ_i有关。并且转向角弧度始终是小于π，即若前一段航迹航向角与后一段航迹航向角差值小于π，AUV将向右转，差值大于π，则AUV向左转。那么，转向耗能W_转向(单位：J)计算公式如下

3.2 仿真结果

如图 9所示，AUV从起始点S_p出发，先沿着y轴正方向的栅格线前进，碰到边界后沿边界x正方向运动，以此锯齿形路径规划行为搜索下去，直到到达R点时，AUV以沿栅格线探测方式找到其左侧海角，并确认E_I为第1类遗漏海湾进入点。AUV将在切换点R暂时退出锯齿形路径规划行为并标记该点位置，然后奔向E_I点，此时AUV将启动遗漏海湾搜索行为，从此点进入遗漏海湾I₁。进入遗漏海湾I₁后，AUV沿着海湾I₁的边界行走，直至遇到湾底，然后后退搜索遗漏海湾区域I₁，搜索完后，AUV到达遗漏海湾退出点X_I，再从X_I沿栅格线运动到E_I点后，锁定遗漏海湾I₁门户，然后返回切换点R，重启锯齿形路径规划行为继续搜索下去。AUV将转入区域I₂，AUV以锯齿形路径规划行为航行，直至遇到湾底并判定采集到的地形图中边界未封闭，此时确认I₂区域为重复海湾，并标记点C为重复海湾的退出点，AUV完成湾底探测后将直接奔向C点。然后AUV切换回锯齿形路径规划行为沿着边界继续前往I₃区域搜索，直至到达区域I₃湾底时，判断搜索的二维区域边界已闭合，然后结束整个路径规划过程。

为了方便描述，将单纯锯齿形完全遍历路径规划称算法为传统方式，将基于重复海湾和遗漏海湾搜索行为的完全遍历路径规划算法称为改进方式，仿真结果如表 1所示。另外，为了对比两种方式下实现全覆盖地形搜索耗能，人为补全传统方式漏掉的搜索区域，如图 10中所示：从I₃区域转到I₁区域的实线路径为人为添加的可以实现搜索区域全覆盖路径规划，那么AUV需要从I₃再转回I₁，如此AUV将多走一段距离才能到达I₁区域。

在AUV完成整个区域覆盖搜索后，改进方式相对于传统方式缩短航程为2 322.5 m。传统方式和改进方式的直航耗能分别是6 339 247 J和5 774 950 J，改进方式节约8.9%的能量。AUV航行时间越长，其搭载的用电设备也会消耗更多的能量。结果显示传统方式耗时25.51 h，而改进方式耗时仅为22.7 h，AUV电气设备功率为50 W，改进后用电设备耗能减少11%。两种路径规划转向耗能分别为368 457 J和318 851 J，改进方式节能13.5%；传统方式有59次转向动作，而改进方式只有49次转向动作，相比之下节省10次转向。真实情况下，AUV在水下回转进行轨迹跟踪时，往往受到本身惯性以及附加惯性的影响而偏离预期轨迹^[25]，从而损耗更多的能量，所以减少转向次数对节省能量至关重要。

4 湖试验证

由于AUV实物试验成本过高，本算法采用如图 11中具有路径自主跟随功能的小型USV对算法的可行性进行湖试验证。湖试试验主要参数为：艇长56 cm、艇宽27 cm、艇高26 cm、艇重量2.5 kg、艇巡航速度1 m/s；试验水域长120 m、水域宽60 m、水面风速1.6~2 m/s、风向自南向北。湖试环境如图 11所示，并根据仿真试验中的边界区域形状设定多海湾区域搜索任务虚拟边界，形状尺寸大小为仿真区域形状大小的1/20。图片拍摄角度为自北向南，右下角方向标志位置为图 12和图 13中路径规划坐标原点位置，即图 2中的坐标原点，自北向南为x轴正方向，此方向虚拟边界最长距离为80 m，自西向东为y轴正方向，此方向最长距离为55 m。

湖面自南向北的风对USV航迹的影响相似于上一节中AUV水下航行时受到的水流的影响，导致图 12和图 13中USV实际航迹偏离期望路径，并增加了USV的全覆盖的耗能。从湖试结果可以发现：与仿真试验相比传统方式的遍历性有所提高，这是因为USV受到风浪影响，其航迹在期望路径两侧左右摆动，增加了其重复探测面积，同时导致USV覆盖重复率上升，而仿真试验中假定AUV是沿着期望的路径规划方式运动；改进方式中，USV同样受到风浪影响以及USV在转向时偏离期望路径而导致重复率有所上升。为了从耗能角度比较两种完全遍历路径规划方式的优劣，本文在湖试中，同样对传统方式中遗漏区域采取了补全路径的方法。最终，通过分别测量两种方式下USV电池电能消耗得出两种方式实现全覆盖时耗能结果，改进方式实现全覆盖地形搜索所耗能比传统方式低6.4%。总的来说，改进后的锯齿形完全遍历路径规划在实际应用中，不管在遍历性、不重复性和全覆盖地形搜索耗能方面，都具备一定的优势。

5 结论

本文从多海湾地形环境表达的角度提出了重复和遗漏海湾的概念，并基于这两种环境表达概念提出了改进后的锯齿形完全遍历路径规划搜索行为。通过多海湾地形下全覆盖测绘仿真，从遍历性、不重复性以及全覆盖搜索任务的耗能3个方面与单纯锯齿形完全遍历路径规划方法进行对比，表明了基于重复海湾和遗漏海湾搜索行为的完全遍历路径规划在复杂多海湾地形下AMV全覆盖搜索的有效性。另外，利用小型无人艇验证了此算法在实际应用中的有效性。在实际工程应用中，此算法可广泛用于智能无人艇对港口全覆盖水深测绘以及水下航行器进行深海海底地形测绘和水文信息获取等全覆盖任务，还可为无人机进行森林植被全覆盖调查以及农业喷洒农药提供路径规划策略。室内扫地机器人以及自动化割草机也可借鉴此算法实现对复杂目标区域的全覆盖任务。