论文引用格式：Wang C F， Wang S Z， Song S J， Wang K， Wu S， Huang G and Wu C. 2023. Multiple unmanned surface vehicles-based path planning method for sea patrol. Journal of Image and Graphics， 28（08）：2536-2548（引用格式:王朝飞， 王慎执， 宋士吉， 王凯， 武帅， 黄高， 吴澄. 2023. 面向海域巡逻的多无人船路径规划方法及仿真. 中国图象图形学报， 28（08）：2536-2548）［0　引言随着我国海洋强国建设重点工程发展战略与21世纪海上丝绸之路倡议的实施，我国海洋事业取得长足进步与发展，但同时我国海洋领域仍面临着诸多安全威胁，如海洋国土划界与领土争端、域外国家军事目标介入和生态环境受损严重等，极大地阻碍了我国海洋事业高质量发展（马文婷和史春林，2020）。在海洋巡逻方面，虽然我国拥有专业化的海防力量，配备一定数量的巡逻飞机、巡逻船等，但是面对大范围的海域巡逻任务，很难做到高效率，且存在人员规模有限、装备运行维护成本高等问题。随着智能制造技术的大力发展，以无人船为代表的海洋智能无人装备逐渐走向成熟，并在军事作战与反恐（王石 等，2019；常书平 等，2020）、资源勘探（常继强 等，2019）、地理测绘（Hong等，2021a，b）、水质检测与治理（吕扬民 等，2019）、水上搜救（陈佳，2013）和海域监控（叶晨 等，2022；张筱晗 等，2020）等领域获得实际应用，这为基于无人装备执行大范围海域巡逻任务提供了重要借鉴作用。相比传统的海域巡逻模式，无人装备的应用能够大幅提高工作效率，极大缩短任务完成时间，并减少人员、装备和能源等运营成本，拥有更具前景的应用价值和经济价值。利用无人船开展海域巡逻任务可视做典型的区域覆盖路径规划（area coverage path planning， ACPP）问题，其目的是为无人船设计一条有效且连续的路径来遍历环境地图中每个可达区域（Zuo 等，2016）。典型的区域遍历算法包括随机覆盖法（Balch，2000）、往返式覆盖法（Choset和 Pignon，1998）、螺旋式覆盖法（郝宗波 等，2017）、STC（spanning tree covering）覆盖法（Gabriely和 Rimon，2001）和单元分解覆盖法（Choset，2001）等。这些算法在遇到障碍物的场景时很难保证100%的覆盖率，且容易出现陷入死角的情况。为此，很多工作引入了一些搜索类算法，如深度优先搜索算法（Doucette和Lu，2015）、广度优先搜索算法（Tripathy 等，2021）、A*算法（Pal 等，2012；陈新 等，2021；吕霞付 等，2019）、人工势场法（张殿富和刘福，2013；王迪 等，2021）、蚁群算法（Lazarowska，2015；Liu 等，2017）、遗传算法（Yakoubi和Laskri，2016；刘松 等，2009）和生物激励神经网络算法（赵红 等，2020；Yang和Luo，2004）等。最新的研究工作多集中于遍历算法和搜索算法的融合应用。目前，已有一些以无人船为主体执行区域覆盖路径规划任务的工作。以单个无人船执行任务为背景，吕霞付等人（2019）提出了一种基于改进A*算法的无人船完全遍历路径规划方法，使无人船在陷入死角时可以向任意角度转向，减少不必要的重复遍历节点。赵德润（2020）对生物激励神经网络算法进行了改进，解决在障碍物毗邻区、海图边界区域等位置覆盖失效的问题，并在港口电子海图上进行了验证。张琪（2019）对遗传算法进行了自适应改进，引入烟花算法，降低了区域覆盖路经规划的重复率。针对单个无人船执行区域覆盖路径规划任务存在效率低、时间长和风险高等缺点，一些研究者提出了多无人船协作开展区域覆盖路径规划任务的方案。包昕幼（2018）研究了在浅水区无人探测艇编队执行巡航探测任务的场景，实现了基于往返式算法和A*算法相结合的区域覆盖路径规划。翁磊等人（2020）为解决多无人艇在岛礁周边海域进行协同测绘问题，提出了基于K-mean++算法的任务分配方法结合启发式路径规划方法的策略，在仿真环境中进行了验证。罗代超（2019）在多无人船协同探测水雷的任务中，考虑了声呐探测设备的联合探测概率，从而提升整个任务水雷探测的概率，是一次区域覆盖路径规划和探测任务结合的应用尝试。总体而言，现有与多无人区域覆盖路径规划相关的研究依然停留在算法研究阶段，一些仿真应用也偏向于港口、岛屿周边以及湖泊等小型水域，并不考虑无人船能源不足的问题。然而，在大型海域巡逻任务场景中，通常采用成本较小的电驱动的小型无人船，覆盖区域范围大和无人船能源动力小之间存在显著矛盾，必须考虑能源约束和能源补给的问题。在这样的背景下，本文对多无人船海域巡逻任务进行了问题定义和建模，在构建海域栅格地图基础上提出了基于任务均衡的多无人船任务区域划分方法和考虑能源约束条件的评价指标；在区域遍历算法方面重点提出了能源约束条件下的区域遍历算法；搭建了仿真平台，在三沙市实际海域地图上进行了仿真实验，验证了所提出算法的有效性，比较了在无能源约束和能源约束条件下不同遍历算法和能源补给策略的优劣性，分析了覆盖率、电池里程数等参数对算法的影响；为多无人船协作开展海洋巡逻任务提供了解决方案，对海洋安全领域技术研究与应用具有一定的借鉴意义。1　任务定义与建模多无人船海域巡逻任务可转化为针对目标海域，在一定约束条件下的多无人船协同区域覆盖路径规划问题，其目的是在最短时间、或小重复率、或最少能耗、或最优化某一指标、或最优化综合指标的情况下完成目标海域的全覆盖探测。其中，约束条件可包括：1）无人船的数量n。该参数直接影响目标海域的子区域划分方法。一般来说，在待覆盖的区域面积一定的情况下，无人船的数量越多，全覆盖所需的时间越短。2）无人船的电池续航里程数lship。该参数直接影响无人船的自动充电路径策略。一般来说，电池续航里程数越大，充电次数越少，由于充电带来的路径重复率会下降。3）无人船搭载的探测传感器的扫描宽度wship。该参数直接影响海域栅格地图的构建和区域覆盖的效率。一般来说，扫描宽度越宽，覆盖效率越高。4）无人船的探测航速vship。该参数不影响区域覆盖的路径规划策略，但是直接关系完成覆盖任务的时间，探测航速越大，完成任务的时间越短。1.1　基于栅格法的海域地图建模栅格法（Moravec和Elfes，1985）是当前研究和应用最为广泛的环境建模方法，它将整个海域地图划分成大小相等的栅格，每个栅格都代表了一片区域，根据地图中可达区域和不可达区域的情况， 确定每个栅格的占有值。栅格坐标系的坐标点与经纬度坐标系可一一对应，能够准确定位，方便于环境建模和算法规划。本文定义目标海域的栅格地图为S={(x,y)} （1）式中，（x，y）为栅格坐标。定义障碍物区域为S∆={(x,y)ocupx,y=0} （2）定义待覆盖区域为Sω={(x,y)ocupx,y=1} （3）式中，ocup∙代表占有函数，值为1表示无障碍物可通行，值为0表示有障碍物或超出目标海域无法通行，3个区域之间的关系为S=Sω⋃S∆ （4）Sω⋂S∆=∅ （5）栅格大小wgrid的设定影响覆盖效率，栅格过大会导致有些区域过度覆盖；过小则会导致覆盖时间过长。考虑到大型海域障碍物一般指岛屿，岛屿的大小通常远大于无人船探测传感器的扫描宽度。因此，本文将海域地图的栅格大小设定为无人船探测传感器的扫描宽度，即wgrid=wship，这样能最大程度展现无人船探测扫描的效率。1.2　基于任务均衡的区域划分在多无人船场景下，如果任由各个无人船按照自己的策略遍历地图，则很可能造成路径大量重复、甚至相撞等无序情况。因此有必要引入区域划分算法，依据一定的规则划分各个无人船的任务区域，明确分工，避免相互干扰；同时要尽可能缩短完成区域覆盖路径规划的总时间，等价于最小化最长路径的无人船的行驶路径，以提高多无人船的整体协作效率。本文将多无人船协同执行区域覆盖任务的目标函数定义为minSω maxiϵ{1,2,∙∙∙,n} Si （6）s.t.  S1⋃S2⋃…⋃Sn⊇Sω （7）式中，Si为第i个无人船的待覆盖任务区域，Si表示单个无人船完成Si区域覆盖任务的行驶路径长度，n表示无人船的数量。此目标函数要取得最优解，需要满足的条件为Si⋂Sj=∅, ∀i,  j∈1,∙∙∙, n, i≠jS1⋃S2⋃…⋃Sn=SωS1≈S2≈…≈Sn≈Sωn （8）基于上述分析，本文采用一种任务均衡的区域划分方法，主要思想是将海域栅格地图沿X轴或Y轴方向对待覆盖区域Sω进行面积近似的等量切分。以X轴方向切分为例（Y轴方向同理），第1个无人船从地图左侧第1列栅格开始逐列向右扫描，并将当前扫描过的列中待覆盖的区域面积累加，设扫描到第c1列时待覆盖栅格区域的面积为s1，如该面积超过待覆盖区域总面积sω的1/n，即s1≥1nsω，则将第1列到第c1列划分为第1个无人船的待覆盖任务区域；对于第i个无人船，从第ci-1+1列开始扫描，当扫描到第ci列时，待覆盖栅格区域面积满足∑l=1isi≥insω，则将第ci-1+1到第ci列划分为第i个无人船的待覆盖任务区域；以此往复，可将Sω划分为S1, S2, ∙∙∙,Sn。若忽略因障碍物绕行或自动充电等造成的重复路径，则每个无人船完成待覆盖任务区域的路径长度近似相等，满足条件式（8）。1.3　评价指标多无人船区域覆盖路径规划算法的评价指标主要包括覆盖率、重复率、总步数、总时间和总充电次数。1）覆盖率JCR。指任务结束后， 所有无人船完成的覆盖面积（重复面积只计算一次）与待覆盖区域总面积的比值。即JCR=a1+a2+…+ansω （9）式中，ai代表第i个无人船完成的覆盖面积，sω代表待覆盖区域的总面积。好的算法可实现100%覆盖。2）重复率JRR。指路径规划完成后，所有无人船行驶中出现 2 次或多次重复遍历的面积总和与总的待覆盖区域面积的比值， 即JRR=a1'+a2'+…+an'sω （10）式中，ai'代表第i个无人船重复遍历的面积。在相同覆盖率的情况下，重复率越小说明算法性能越好。3）总步数Nstep。路径规划完成后，所有无人船行驶的总步数与栅格大小相乘后即为总路径长度。在相同覆盖率的情况下，总步数越少说明算法性能越好。4）总时间T。指从路径规划开始到最后一个无人船完成任务时所用的时间，包括该无人船的航行时间Trun和充电时间Tcharge，表示为T=Trun+Tcharge （11）在相同覆盖率的情况下，总时间越短说明算法性能越好。5）总充电次数Ncharge。指路径规划完成后，所有无人船充电次数之和，可近似代表完成任务的总体能耗。在相同覆盖率的情况下，总充电次数越少说明算法性能越好。2　无人船区域覆盖遍历算法对目标海域完成栅格地图的构建后，采用基于任务均衡的区域划分方法为每个无人船划分任务区域，然后对划分后的任务区域进行遍历，目的是为每个无人船在任务区域内寻找一条经过所有无障碍物栅格（覆盖率JCR可达100%）的连续路径，该路径长度应该尽可能短，以减少总步数Nstep，降低重复率JRR，减少总时间T，同时还要求总充电次数Ncharge最小，以节省能源。在任务区域确定的情况下，假如要求每个无人船完成对应任务区域的全覆盖，则优化每个无人船行驶步数至最小，即可保证重复率最小，航行时间最少；假如要求每次充电的能源利用率最高，即每次充电可近似看做一次饱和充电（电量从最低要求到100%），优化充电次数至最小，即可保证能源消耗最小。在海域巡逻任务场景中，海域地图往往覆盖范围大且障碍物复杂度高，随机遍历算法（Balch，2000）和STC遍历算法（Gabriely和Rimon，2001）覆盖效率低，且会产生大比例的重复，从而造成高额的能源成本，显然是不适用的。同时，考虑到无人船的任务区域存在障碍物的情况，仅采用往返式覆盖法（Choset和Pignon，1998）和螺旋式覆盖法（郝宗波 等，2017）都不可避免出现无法全覆盖和陷入死角的问题，需要结合搜索类算法实现区域的跳转。在搜索类算法中，深度优先搜索法（Doucette和Lu，2015）和广度优先搜索法（Tripathy 等，2021）搜索完整的状态空间，能够获得全局最优解但搜索效率较低；A*算法（Pal 等，2012）、人工势场法（张殿富和刘福，2013）等启发式搜索方法压缩了搜索空间从而提升了搜索效率，但容易陷入局部最优解。在海域巡逻任务中，巡逻路径的长短直接关系着无人船的能源成本，是需要考虑的第一因素。同时，由于海域地图已知，对算法的效率要求并不高。因此，本文选择采用广度优先搜索法结合往返式覆盖法或螺旋式覆盖法进行主体算法框架设计。2.1　无能源约束条件下的遍历算法为方便研究与分析，首先考虑无能源约束的情况，即假设每个无人船都具有充足的能源，不会因为充电需要而改变航线。算法伪代码如下：算法1 无能源约束条件下的遍历算法输入：目标海域的栅格地图，无人船的数量、扫描宽度和行驶速度等。输出：无人船覆盖目标海域的方案，以及该方案的覆盖重复率、总时间和总步数等。1） 划分每个无人船的任务区域；2） 初始化每个无人船的位置；3） 采用往返式覆盖法（或螺旋式覆盖法）对某个无人船的任务区域进行首次扫描，扫描完成后会形成一个已覆盖区域和多个未覆盖区域；//以下以一个无人船为例，其他同理4） while 存在未覆盖区域 do；5） 利用广度优先搜索算法寻找与当前位置曼哈顿距离最小的未覆盖区域，并记录最短路径；6） 从当前位置沿最短路径到达最近的未覆盖区域；7） 采用往返式覆盖法（或螺旋式覆盖法）对该区域进行覆盖；8） end while。2.2　能源约束条件下的遍历算法在大型海域巡逻任务的实际应用场景中，无人船普遍存在能源不足的情况，必须考虑能源补给的问题。一种简单的策略是：无人船在能源不足时发出警报信号，由能源补给船前往无人船所在位置进行能源补给，补给完成后无人船继续沿既定路线航行，这样可将能源约束条件转化为无能源约束条件，采用上一节的算法执行任务。但这种方式需要补给船只以及相应装备、人员等，带来额外的成本消耗。一种智能化的策略是：无人船根据自身能源情况和自身与补给点之间的距离，自行决定是否前往补给点进行能源补给。在这种自动决策的策略中，无人船在补给完成后选择返回补给前的位置继续执行遍历任务，还是选择重新规划遍历路线，是一个需要评价和选择的问题。1）补给后返回原位置。优点是将区域遍历路径规划和能源补给解耦，能源补给不影响原先的路径规划；缺点是导致补给过程中的路径重复，增大了重复率，浪费了部分能源。2）补给后重新规划路线。优点是将补给过程经过的路线作为已覆盖区域，不对该路线进行重复遍历，能够提高能源使用效率；缺点是补给线路的引入会增大区域地图的复杂程度，且随着补给次数的增多地图复杂程度增大。本文讨论了上述两种方案的优劣，并进行了算法和实验比较验证，其中补给后重新规划路线采用广度优先算法寻找与当前充电点曼哈顿距离最小的未覆盖区域，并沿广度优先算法得到的最短路径到达新的区域，继续执行区域覆盖任务。算法伪代码如下：算法2 能源约束条件下的遍历算法输入：目标海域的栅格地图、无人船的数量、扫描宽度、行驶速度和电池里程数等。输出：无人船覆盖目标海域的方案，以及该方案的覆盖重复率、总时间、总步数和充电次数等。1） 划分每个无人船的任务区域；2） 初始化每个无人船的位置；//以下以一个无人船为例，其他同理3） while 存在未覆盖区域 do；4） if 需要充电 then；5） 采用广度优先搜索算法搜索离当前位置最近的充电点，并保存对应的最短路径，按照最短路径到达充电点充电；6） if 充电后返回原位置 then；7） 充电结束后，沿原路径返回上述最短充电路径的起点；8） else 充电后重新规划；9） 利用广度优先搜索算法寻找与当前位置曼哈顿距离最小的未覆盖区域，并沿最短路径到达该区域；10） end if；11） end if；12） if 当前区域已经覆盖完全 then；13） if 不存在未覆盖区域 then；14） break；15） else；16） 利用广度优先搜索算法寻找与当前位置曼哈顿距离最小的未覆盖区域，并沿最短路径到达该区域；17） end if；18） end if；19） 采用往返式覆盖法（或螺旋式覆盖法）执行一个动作；20） end while。2.3　能源约束条件下的充电时机选择在算法2中，充电时机的确定是后续充电路径规划和充电后路径规划的先决条件。实际应用中，为提升能源的使用效率和电池的寿命，一般采取饱和充电的策略，即无人船到达充电点时近似达到充电的边缘条件（如剩余电量小于一定的电量比例）。本文中设定的电池续航里程数lship可理解为电池最大电量减去最小电量后能够航行的距离。本节设计了一个实时电量监控以及充电路径规划的策略。具体地，航行中的每一步无人船都会使用广度优先搜索算法寻找最近的充电点以及对应的最短路径，并计算到达最近的充电点所需里程数，记为lmin，并与当前无人船电池的剩余里程数lres比较，若lres≥lmin+wgrid，则无需充电，无人船按照既定路线行走；若lreslmin+wgrid，则说明应该立刻前往最近的充电点充电。无人船做出充电决策后，会按照先前计算出的最短路径前往充电点，充完电后会返回原位置或者重新规划路线。3　仿真实验与结果分析为了实现多无人船区域覆盖路径规划方法的算法验证和实际应用，本文选择三沙市—西沙群岛周边海域地图作为海域巡逻任务的应用场景进行仿真实验。仿真实验的内容主要包括海域栅格地图构建与任务区域划分、无能源约束条件下的比较实验、能源约束条件下的比较实验以及消融实验。海域地图如图1所示，海域覆盖范围长约130 km、宽约120 km，海域面积约15 600 km2。除消融实验除外，无人船的参数设定为：所载探测装备的扫描宽度wship= 2 km，探测航速vship=20 km/h，数量n=10，电池里程数lship=400 km，一次完整充电时间为3 h。实验评估指标中T的单位为小时（h）。本文的仿真平台主要基于Python平台实现，物理仿真引擎采用Pymunk，渲染工具采用Pygame，数值计算工具采用Numpy。10.11834/jig.220287.F001图1三沙—西沙群岛周边海域示意图Fig.1The sketch map of the sea area around Sansha-Xisha islands3.1　海域栅格地图构建与任务区域划分设定栅格大小wgrid=wship，可将图1海域地图栅格化如图2所示，其中障碍物区域用深灰色表示，待覆盖区域用浅蓝色表示，栅格划分用黑色直线表示，统计可得sω=13 764 km2。10.11834/jig.220287.F002图2海域栅格地图Fig.2The raster map of the sea area为评估基于任务均衡区域划分方法的性能，图3展示了5个无人船协同执行区域覆盖任务时的区域划分结果，其中每个无人船的任务区域用不同的颜色表示。经计算，5个无人船的任务区域面积分别占待覆盖区域总面积的比例为20.8%、20.4%、20%、19.8%和19.0%，近似相等，达到了预期效果。10.11834/jig.220287.F003图3多无人船任务区域划分示意图Fig.3The sketch map of task area division3.2　无能源约束条件下的比较实验在无能源约束条件下，本节评估不同遍历算法对覆盖结果的影响。不同遍历算法包括往返式覆盖法和螺旋式覆盖法。启发式搜索方法采用广度优先搜索算法，具体算法参见2.1节算法1。评价指标包括覆盖率JCR、重复率JRR、总步数Nstep和总时间T(h)。每个无人船的起始点都设定为其所负责的子区域内最左边一列的最上方的栅格。表1展示了在保证覆盖率JCR=100%的条件下，无人船的数量n分别为1、5、10条件下的实验结果。实验结果表明：1）增大无人船数量会一定程度上增加重复率和总步数。无人船数量越多任务区域的划分会越分散，无人船在众多任务区域内需要跨越的子区域总体会变多，进而导致重复率和总步数的适度上升。2）增大无人船数量会显著降低完成任务的总时间，且二者之间大约呈现反比关系。在实际应用中，可根据任务要求的完成时间设定无人船的数量。3）在同等条件下，往返式遍历算法的重复率、总步数和总时间都略低于螺旋式。说明在本文设定的任务环境中，往返式遍历算法整体优于螺旋式遍历算法。10.11834/jig.220287.T001表1无能源约束条件下不同遍历算法的比较结果Table 1Comparison results of different traversal algorithms without energy constraint算法n=1,  JCR=100%n=5, JCR=100%n=10,  JCR=100%JRR/%NstepT/hJRR/%NstepT/hJRR/%NstepT/h往返式5.233 670367.08.383 79483.09.873 84143.0螺旋式10.463 848384.811.313 87786.212.313 91143.3图4展示了无能源约束条件下，设置n=1, JCR=100%，采用两种遍历算法的可视化仿真结果。图4（a）（c）为覆盖图，其中淡紫色代表一次覆盖过的区域，深紫色代表重复覆盖区域。图4（b）（d）为路线图，红色点为起点，箭头为前进方向，黄色点为终点。将图4（a）（c）与图4（b）（d）相比，可知往返式覆盖算法在重复率方面明显优于螺旋式覆盖算法。10.11834/jig.220287.F004图4无能源约束条件下的可视化仿真结果图Fig.4Visual simulation results without energy constraint（（a） round-trip coverage map； （b） round-trip track map； （c） spiral coverage map； （d） spiral track map）3.3　能源约束条件下的比较实验在考虑能源约束条件时，本节评估不同补给策略对覆盖结果的影响。补给策略包括补给后返回原位置和补给后重新规划路线，具体算法参见2.2节算法2。考虑到海域范围较大，本文考虑所有具有一定面积的典型岛屿上均可设立补给点，即图1中标记出的10座岛屿均设立补给点。由于大部分岛屿尚处于未开发的状态，无法精确设定补给点的位置，在仿真环境中将无人船到达岛屿即视做可以进行补给，这一假设对无人船的行进路线和执行任务时间带来的误差相比整个任务而言可忽略不计。表2和表3分别展示了往返式和螺旋式覆盖算法在电池里程数lship=400 km、覆盖率JCR=100%的条件下，无人船的数量分别为1、5、10条件下的实验结果。实验结果表明：1）相较于无能源约束的情况（表1），考虑能源约束（表2和表3）会显著地增加重复率、总步数以及总时间。分析可知，充电后返回原位置会导致充电路径带来额外的重复率，充电后重新规划路线则会导致分割子区域增多带来额外的重复率。2）在大多数实验设置和评价指标下（除无人船数量n=1条件下的总步数外），往返式覆盖算法均优于螺旋式覆盖算法。10.11834/jig.220287.T002表2往返式覆盖算法在能源约束条件下不同充电策略的比较结果Table 2Comparison results of different charging strategy with energy constraint by round-trip traversal algorithm算法n=1,  JCR=100%n=5, JCR=100%n=10,  JCR=100%JRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位12.234 073467.32012.314 076139.51811.103 96085.614重新规划12.074 016461.62010.413 884130.11610.693 92587.61510.11834/jig.220287.T003表3螺旋式覆盖算法在能源约束条件下不同充电策略的比较结果Table 3Comparison results of different charging strategy with energy constraint by spiral traversal algorithm算法n=1,  JCR=100%n=5, JCR=100%n=10,  JCR=100%JRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位13.514 007460.72016.974 136141.81919.134 21397.918重新规划12.923 970454.01915.364 060141.51918.104 16596.918图5展示了能源约束条件下，设置n=5， JCR=100%，采用两种遍历算法在充电后采取返回原位置和重新规划路线两种策略下的可视化仿真结果图。可以发现，往返式覆盖算法结合充电后重新规划路线的算法在减小重复率方面获得最优的效果。10.11834/jig.220287.F005图5能源约束条件下的可视化仿真结果图Fig.5Visual simulation results with energy constraint （（a） round-trip + return； （b） round-trip + replan； （c） spiral + return； （d） spiral + replan）3.4　消融实验在实际应用场景中，对区域覆盖任务的要求可能不一定是覆盖率为100%，可能只需要满足一定的阈值（如90%），无人船的电池里程数lship也会根据船体的大小和任务的需求而不同。为了使研究更贴近实际，本节分析不同覆盖率要求、不同无人船电池里程数对能源约束条件下区域覆盖算法的影响。往返式覆盖算法和螺旋式覆盖算法在无人船数量n=10、电池里程数lship=400 km，覆盖率要求分别为100%、90%、80%情况下，能源约束条件下的实验结果分别如表4和表5所示。实验结果表明：当要求的覆盖率降低时，重复率、完成任务总时间都会显著降低，这说明从实际应用的角度，适当降低覆盖率要求可以提高效率；此外，在不同覆盖率要求下充电后重新规划路线依然优于充电后返回原位置的算法。10.11834/jig.220287.T004表4往返式覆盖算法在能源约束条件下的覆盖率消融实验结果Table 4Ablation study of coverage rate with energy constraint by round-trip traversal algorithm算法n=10,  JCR=100%n=10, JCR=90%n=10,  JCR=80%JRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位11.103 96085.6144.673 32062.3102.902 90058.110重新规划10.693 92587.6153.773 26061.7102.312 86057.71010.11834/jig.220287.T005表5螺旋式覆盖算法在能源约束条件下的覆盖率消融实验结果Table 5Ablation study of coverage rate with energy constraint by spiral traversal algorithm算法n=10,  JCR=100%n=10, JCR=90%n=10,  JCR=80%JRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位19.134 21397.91812.973 62065.3109.103 12060.310重新规划18.104 16596.91812.463 59065.0108.283 08059.910往返式和螺旋式覆盖算法在无人船数量n=10、覆盖率要求JCR=100%，电池里程数lship分别为200 km、400 km和800 km情况下，能源约束条件下的实验结果如表6和表7所示。实验结果表明：电池里程数的大小会显著影响覆盖的重复率、所需时间以及充电次数。具体地，电池里程数越大，重复率、充电次数和总时间都会显著减小，说明在实际应用中，增大电池容量可以显著提升任务完成的效率。10.11834/jig.220287.T006表6往返式覆盖算法在能源约束条件下的电池里程数消融实验结果Table 6Ablation study of battery mileage with energy constraint by round-trip traversal algorithm算法n=10, lship=200 kmn=10, lship=400 kmn=10, lship=800 kmJRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位18.334 581171.84011.103 96085.61410.033 90155.64重新规划17.544 331160.03910.693 92587.61510.363 88655.6410.11834/jig.220287.T007表7螺旋式覆盖算法在能源约束条件下的电池里程数消融实验结果Table 7Ablation study of battery mileage with energy constraint by spiral traversal algorithm算法n=10, lship=200 kmn=10, lship=400 kmn=10, lship=800 kmJRR/%NstepT/hNchargeJRR/%NstepT/hNchargeJRR/%NstepT/hNcharge返回原位28.464 621169.84019.134 21397.91812.463 92355.73重新规划28.054 585169.74018.104 16596.91812.333 92055.534　结论在大型海域巡逻任务中，相比传统的巡逻装备，多无人船协同执行区域覆盖任务具有运行时间短、效率高和风险低等优势。但是，海域覆盖区域范围大和无人船能源动力不足之间存在显著矛盾，必须解决任务划分和能源补给等难点问题。在此背景下，本文首先对多无人船协同执行海域巡逻任务进行了定义和建模，在构建栅格海域地图的基础上提出了基于任务均衡的区域划分策略和评价指标；在分析比较了多种传统遍历算法的基础上，提出了无能源约束和能源约束条件下的区域覆盖遍历算法；搭建了仿真平台，以三沙市周边15 000多平方公里海域地图为仿真对象，验证了提出的无能源约束和能源约束条件下多种算法的有效性。实验结果表明，以宽度优先搜索算法结合往返遍历算法或螺旋遍历算法为主体算法框架，在无能源约束条件下，往返式遍历算法的覆盖率和完成任务时间优于螺旋式遍历算法。在能量约束条件下，充电后采用宽度优先搜索算法重新规划新路径优于充电后继续原有路径。消融实验表明：1）适当降低覆盖率要求可以减少整体任务的覆盖重复率和总任务时间；2）增加无人船的电池续航里程可以显著提高任务效率。我国海域辽阔，海域巡逻任务量巨大，迫切需要具备高效率、低成本特点的智能无人装备的大规模应用。本文的研究只是多无人船在大型海域巡逻任务中应用的一次尝试，旨在为相关领域的应用研究提供一定的借鉴意义。当前的研究依然存在一些不足，如充电补给点的设置并未考虑实际海岛的部署条件、无人船的航行过程并未考虑突发避碰的情况等。下一步将进一步贴近实际应用环境，深化研究充电点部署策略与算法效率的关系，加入无人船运行过程中突发避碰情况的解决方案，并考虑扩大方法的应用范围，如从海域巡逻任务向海底三维探测任务拓展等。