Area coverage path planning of multiple ASVs based on ECDIS
-
摘要:目的
针对无人艇（ASV）集群区域覆盖问题，设计一种基于电子海图信息系统（ECDIS）的多无人艇区域覆盖路径规划方法。
方法首先，通过提取ECDIS中的海陆和水深信息，建立基于栅格化方法的无人艇集群覆盖区域环境模型。其次，提出一种基于轮盘选择法的区域划分方法，解决基于初始位置的区域划分方法区域划分不规则的问题，实现在栅格地图中对无人艇集群覆盖子区域的合理划分。最后，构建一种基于模板法的区域覆盖路径规划方法，解决生成树覆盖方法路径转弯数量较多的问题。
结果搭建基于ECDIS的无人艇集群人机交互仿真平台，验证所提基于轮盘法和模板法的区域覆盖路径规划方法对优化规划路径转弯数量的有效性。
结论采用所提基ECDIS的无人艇集群区域覆盖路径规划方法，实现多无人艇对海上目标任务区域的覆盖路径规划。
Abstract:ObjectiveAiming at the area coverage problem of multiple autonomous surface vehicles (ASVs), this paper investigates a coverage path planning (CPP) strategy based on an electronic chart display and information system (ECDIS).
MethodFirst, according to the information of sea, land and water depth from ECDIS, an environmental model for the area coverage of ASVs is established based on the grid method. Second, an area division method based on the roulette wheel selection method is proposed to solve the problem of irregular area division in divided areas based on the robots' initial position method, and achieve the reasonable area division of ASVs in the grid map. Finally, a template-based area coverage path planning method is proposed to solve the problem of generating too many turns in paths generated by the spanning tree coverage agorithm.
ResultsA human-machine interactive simulation platform for ASVs based on ECDIS is established to verify the effectiveness of the proposed area coverage path planning method based on the roulette wheel method and template method in optimizing the number of turns in the planning path.
ConclusionThe proposed area coverage path planning method for ASVs based on ECDIS can be used to achieve coverage path planning in target mission areas at sea.
-
0. 引 言
对海洋的探索、开发和利用是当前各个国家的发展重点[1-3]。无人艇（autonomous surface vehicles，ASVs）因其具有小型化、轻量化、自主化等特点，已成为探索海洋、开发海洋的重要工具。与单艘无人艇相比，无人艇集群系统更可靠、更灵活、鲁棒性更强、更易扩展[4-6]。无人艇集群能够代替工作人员完成水上搜救[7]、海洋测绘[8]、港口防御[9]等复杂危险的任务，提高海上作业的效率和安全性。无人艇集群区域覆盖路径规划是无人艇集群任务中的一个重要环节，其主要任务可以描述为：多艘无人艇从多个起始点开始，航行通过除障碍物之外的整个任务海域，并尽可能地满足时间短、重复路径少、未遍历区域小等目标。
国内外学者在区域覆盖路径规划方面已进行了许多研究，其中生成树覆盖（spanning tree coverage，STC）方法是较常用的方法之一。文献[10]首次将STC方法应用到机器人的覆盖路径规划问题中，使机器人在任务区域的覆盖率达到95%。文献[11]将STC方法应用到多机器人覆盖路径规划问题中，减少了多机器人覆盖的任务时间。文献[12]将一种人工加权的STC方法应用到无人机集群覆盖路径规划中，提高了无人机集群的覆盖效率，减少了覆盖路径的重复率。文献[13]将基于初始位置的区域划分（divide areas based on robots' initial positions，DARP）方法与STC方法相结合，提高了多机器人的整体覆盖效率。然而，尽管在机器人和无人机领域已经提出了多种集群覆盖方法，但是在无人艇领域的相关研究还较少。文献[14]提出一种改进的BA*算法应用于无人艇集群覆盖路径规划，实现了无人艇集群的覆盖规划。
本文将从工程实践出发，研究在电子海图（ECDIS）场景中的无人艇集群区域覆盖路径规划方法，围绕电子海图栅格化处理、任务区域划分和子区域覆盖3个方面展开研究。首先，提取电子海图选定任务区域的海陆、水深信息，并采用栅格化处理的方法为任务区域建立栅格地图；其次，针对DARP方法区域划分不规则的问题，设计基于轮盘选择法的区域划分方法；再次，针对STC方法覆盖路径的转弯数量较多的问题，设计基于模板法的区域覆盖路径规划方法，减少STC方法生成路径的转弯数量；最后，搭建基于电子海图信息的人机交互仿真平台，针对2种改进策略对无人艇集群区域覆盖路径规划转弯数量优化的有效性进行仿真验证。
1. 环境模型的建立
1.1 电子海图信息的导出
电子海图是一种采用数字形式描述海域地理信息和航海信息，并借助计算机技术，通过显示设备对海图信息及航海数据进行制作显示的数字式海图。电子海图由多种海域要素组成，主要包括航行障碍、禁航区域、港口设施等。无人艇在进行海上作业任务时，通常需要通过电子海图获取任务区域的海域信息[15]。
将电子海图应用到无人艇集群覆盖路径规划中，需要对电子海图数据进行解析、提取、存储。用户可以在人机交互平台上自行选择任务区域，平台可以根据用户选择的任务区域遍历提取电子海图海陆、水深信息，并通过栅格化处理构建栅格地图，电子海图栅格化流程如图1所示。
1.2 栅格化建立环境模型
海洋环境尺度大，而采用栅格化方法可以将海洋大尺度的环境信息压缩，提高算法的运行速度，降低路径规划的复杂度。因此，本文采用栅格化方法为无人艇集群构建出易于路径规划的环境模型。
栅格化建立海洋环境模型的过程描述如下：针对用户选取的矩形任务区域，采用横向和纵向网格线将任务区域交割划分为尺寸相同的网格单元。人机交互仿真平台根据用户选择的任务区域，通过遍历方式提取任务区域海陆、水深信息，并将陆地、岛屿与水深较浅的区域设置为障碍区域。在确定障碍区域的位置后建立存在障碍栅格、空闲栅格（可航行区域）与初始位置栅格（无人艇初始位置）的栅格地图。海域栅格化示意图如图2和图3所示。此时，针对电子海图的无人艇集群覆盖路径规划问题便转化为在栅格地图中为无人艇集群规划出覆盖所有空闲栅格的路径。
2. 改进无人艇集群区域覆盖路径规划方法
2.1 基于轮盘选择的无人艇集群覆盖任务区域划分
以栅格地图中的无人艇集群覆盖为例，传统DARP方法以无人艇集群的初始位置栅格作为优化起点，通过对空闲栅格的迭代划分为每艘无人艇分配数量均等的空闲栅格。尽管该方法通过为无人艇分配等量栅格提高了无人艇集群覆盖的整体效率，但当无人艇集群初始位置栅格过于密集时[16]，DARP方法划分的子区域多为不规则的形状，且算法容易陷入循环迭代的“死区”。如图4所示，图中4个黄色圆点为4艘无人艇的初始位置，此时4艘无人艇选取较为密集的初始位置。使用DARP方法为4艘无人艇进行区域划分，并分别截取0，60，120，180，240和300 s时刻的区域划分情况。从图中可以发现，采用DARP方法为无人艇划分的子区域都是不规则形状。无人艇在不规则的子区域进行覆盖时会频繁进行转弯，这会增加无人艇航行时的能量消耗，降低区域覆盖整体效率[17]。
为解决上述问题，我们设计了基于轮盘选择的区域划分方法对DARP方法的优化起点进行改进，轮盘选择法示意图及流程图分别如图5和图6所示。由图可见，轮盘选择法首先基于任务区域的长宽，在任务区域内绘制1个内接圆，并根据无人艇的数量在内接圆上均匀取点，保证优化起点分散且在任务区域内均匀分布。当优化起点位于障碍栅格时，通过计算优化起点栅格与所有空闲栅格的欧式距离，找到一个与此栅格距离最小的空闲栅格作为此区域的优化起点栅格。此时，在栅格地图中得到了一系列分布均匀的无人艇优化起点栅格，基于这些优化起点栅格对空闲栅格进行迭代划分，能够在栅格地图中将空闲栅格区域划分为一系列规则的子区域，且算法也能够避免陷入循环迭代的“死区”。
2.2 基于模板法的子区域覆盖路径规划
在完成任务区域划分后，需要在每个子区域生成覆盖路径，本文选择STC方法作为覆盖路径规划的基本方法[18]。STC方法的原理是：在栅格地图中，将4个空闲栅格构造成1个空闲大栅格，将每个空闲大栅格的中心点转化成1个树节点，用线段连接2个相邻空闲大栅格的中心点（树节点），构造成一个遍历所有空闲区域的树结构。无人艇沿逆时针（或顺时针）方向围绕生成树，产生一个闭合的覆盖路径。图7（a）表示无人艇执行覆盖任务的栅格地图。其中，灰色栅格表示障碍栅格，白色栅格表示空闲栅格。将4个空闲栅格集合成1个空闲大栅格，并将中心点作为1个树节点，得到节点图7（b）。在图7（b）中，黄色节点代表空闲区域的树节点，蓝色节点代表无人艇优化起点栅格。在图7（c）中，每个子区域的树节点优先选择与之相邻的权值较小的树节点，并用线段与之相连形成一条边，子区域中边与边相连构成生成树。在图7（d）中，每艘无人艇从优化起点栅格开始，按顺时针（或逆时针）方向沿生成树环绕1周，得到4条闭合的全覆盖路径。
尽管STC方法能够为无人艇在每个子区域生成覆盖路径[19-21]，但在相同的任务场景下，当上、下和左、右4个覆盖方向的权值不同时，STC方法产生覆盖路径的转弯数量也不同。因此，为了提高无人艇在子区域的覆盖效率，本文提出基于模板法的STC方法，模板法流程图如图8所示。
如图9和图10所示，模板法的基本原理是：针对上、下和左、右4个生成树覆盖方向，设计上、下、左、右4种覆盖模板，通过改变每种模板的权值大小，为子区域生成4种生成树结构。通过计算每个子区域4种覆盖模板产生路径的转弯数量，最终选取转弯数量最少的生成树覆盖模板作为子区域的最优模板，并基于此模板优化的STC方法为子区域生成覆盖路径。
![]()
图 10 4种生成树模板生成的覆盖路径Figure 10. Covering paths generated by four spanning tree templates3. 仿真实验
3.1 仿真环境搭建
本文在VS2010和Python 3.6环境下完成了基于电子海图信息的无人艇集群覆盖路径规划方法仿真实验。
仿真任务区域选取为大连近海水域，具体区域由（121.645190°E，39.031178°N），（121.645190°E，38.884806°N），以及（121.842491°E，39.031178°N），（121.842491°E，39.031178°N）为顶点构成的矩形区域。任务区域包括不同水深的海洋区域与陆地区域，因此在选取任务区域后，根据框取区域的海陆、水深信息，用0-1编码代替电子海图的海陆信息。其中，0代表海洋，1代表陆地，转化完成后将数据打包发送给栅格化模块。
图11为基于电子海图的无人艇集群覆盖路径规划平台流程图，具体步骤如下：
![]()
图 11 无人艇集群覆盖路径规划程序流程图Figure 11. Flow chart of the coverage path planning for multi-ASVs1） 设置电子海图的尺度和无人艇的数量等参数信息。
2） 用户在电子海图中选取任务区域。
3） 设置栅格尺寸并对电子海图数据进行栅格化处理，生成任务区域的栅格地图。
4） 由基于轮盘选择的区域划分方法自动完成区域划分。
5） 由基于模板法优化的STC方法自动完成子区域的覆盖路径规划。
6） 完成对任务区域的覆盖路径规划，并将规划路径的数据发送给电子海图，若需要更换任务区域，则由用户重新选取任务区域，并由平台完成对新任务区域的覆盖路径规划。
7） 在电子海图界面显示规划结果。
3.2 仿真结果分析
图12和图13展示了基于轮盘选择的区域划分法与DARP方法的对比结果，图中选取一片岛礁区域作为任务区域。4艘无人艇的初始位置栅格为(32,1)，(41, 1)，(32, 8)，(41, 8)，以此4个栅格作为DARP方法的优化起点，区域划分与覆盖路径规划的结果如图12所示。在相同区域，采用轮盘选择法产生的优化起点栅格为(28, 3)，(48, 3)，(25, 26)，(48, 26)，以此4个栅格作为基于轮盘选择的区域划分法的优化起点，并采用同样的STC方法进行覆盖路径规划，区域划分与覆盖路径规划的结果如图13所示。对比可见，图13中划分的子区域比图12的子区域更规则。
![]()
图 13 采用所提轮盘选择区域划分方法的规划路径结果Figure 13. Planning path results using the proposed roulette wheel selection area division method在图12中，对于初始位置栅格为(32, 8)的区域3来说，覆盖路径的转弯数量是120次，且覆盖路径为一个“C”字型的不规则区域。而在图13中，采用轮盘选择法优化后生成的起点栅格为(25, 26)，在此优化起点采用基于轮盘选择的区域划分法为区域3划分出了一个近似“梯形”的任务区域，且此区域只产生了56次转弯，转弯率降低了47%。
图14和图15给出了模板法对STC方法优化的对比结果。图14为在划分后的区域1～区域4分别采用4种生成树覆盖模板为无人艇规划的覆盖路径，通过统计每个区域规划路径的转弯数量可知，对于同一个区域，采用不同的生成树覆盖模板会为覆盖路径产生不同的转弯数量。对于区域1来说，采用向下的模板会为覆盖路径产生82次转弯。而在相同区域下采用向左的模板只产生了38次转弯，转弯率比向下的模板降低了54%。在区域1～区域4中分别采用最优的生成树模板会降低整个栅格地图覆盖路径的总转弯数量。例如，对整个栅格地图的区域1～区域4采用同一种生成树模板，此时区域1～区域4共产生312次转弯，而针对不同的区域采用模板法对STC方法进行优化，每个区域采用转弯数量最小的生成树模板后区域1～区域4总转弯数量降至194次，栅格区域总体的转弯率降低38%。
![]()
图 14 同一区域不同覆盖方向的4种规划路径Figure 14. Four planning results under different coverage directions in the same area![]()
图 15 使用模板法优化后的规划路径Figure 15. Optimized results of path planning after using template-based STC algorithm图16～图19给出了不同数量级无人艇集群在电子海图中规划的效果图。图16是针对4艘无人艇的区域覆盖路径规划，黄色的矩形框图为选取的任务区域，其中包含海洋和陆地信息，4个红点代表轮盘选择法优化产生的优化起点。由图可见，基于轮盘选择区域划分方法产生的子区域均匀分布在任务区域的四角，且子区域的形状都相对规则，因此子区域产生覆盖路径的转弯数量也会降低。而每个子区域均采用基于模板法的STC方法，为每个子区域生成了转弯数量最优的覆盖路径。
![]()
图 19 25艘无人艇区域覆盖路径规划结果Figure 19. Area coverage path planning results of twenty-five ASVs图17是针对8艘无人艇的区域覆盖路径规划结果，此场景与4艘无人艇的场景相同，只是无人艇数量增加了一倍。即便如此，优化方法仍然为8艘无人艇均匀地规划出8个起点，即图17中的8个红点。由图可见，由于每个子区域的面积减小了一半，子区域的形状由规则的梯形向菱形转变，而模板法会使STC方法优先选择菱形长对角线方向作为往返扫海方向，因此形成了图17中由四周向中间覆盖的规划路径。
图18是针对12艘无人艇的区域覆盖路径规划结果，图19是针对25艘无人艇的区域覆盖路径规划结果。
由图18和图19可以发现，当无人艇的数量增加后，无人艇的优化起点均匀分布在同一个轮盘，产生的覆盖路径也均匀分布在任务区域中。即使无人艇集群的数量成倍地增加，在任务区域中优化起点的位置也能够分散且均匀分布，且子区域的形状也相对规则，这也解决了DARP方法在优化起点过于密集时容易陷入循环迭代“死区”的问题。
4. 结 语
本文基于电子海图栅格化方法，将电子海图与无人艇集群的覆盖路径规划相结合，完成了基于电子海图信息的无人艇集群覆盖路径规划算法及仿真平台的设计与实现。首先提出了基于轮盘选择的区域划分方法，优化了DARP方法在初始位置过于密集时区域划分的子区域不规则、产生覆盖路径转弯数量多的问题；其次提出了基于模板法的STC方法，减少了子区域覆盖路径的转弯数量。仿真验证了所提路径规划方法改进的效果，并在不同数量级的无人艇集群下完成了基于电子海图信息的无人艇集群覆盖路径规划测试验证。
本文所提基于电子海图的无人艇集群区域覆盖路径规划方法，将为未来无人艇集群大规模海上区域覆盖作业提供新的路径规划方法。
-
![]()
图 10 4种生成树模板生成的覆盖路径
Figure 10. Covering paths generated by four spanning tree templates
![]()
图 11 无人艇集群覆盖路径规划程序流程图
Figure 11. Flow chart of the coverage path planning for multi-ASVs
![]()
图 13 采用所提轮盘选择区域划分方法的规划路径结果
Figure 13. Planning path results using the proposed roulette wheel selection area division method
![]()
图 14 同一区域不同覆盖方向的4种规划路径
Figure 14. Four planning results under different coverage directions in the same area
![]()
图 15 使用模板法优化后的规划路径
Figure 15. Optimized results of path planning after using template-based STC algorithm
-
[1] LIU Z X, ZHANG Y M, YU X, et al. Unmanned surface vehicles: an overview of developments and challenges[J]. Annual Reviews in Control, 2016, 41: 71–93. doi: 10.1016/j.arcontrol.2016.04.018
[2] PENG Z H, WANG J, WANG D, et al. An overview of recent advances in coordinated control of multiple autonomous surface vehicles[J]. IEEE Transactions on Industrial Informatics, 2021, 17(2): 732–745. doi: 10.1109/TII.2020.3004343
[3] 张晓东, 刘世亮, 刘宇, 等. 无人水面艇收放技术发展趋势探讨[J]. 中国舰船研究, 2018, 13(6): 50–57. doi: 10.19693/j.issn.1673-3185.01258 ZHANG X D, LIU S L, LIU Y, et al. Review on development trend of launch and recovery technology for USV[J]. Chinese Journal of Ship Research, 2018, 13(6): 50–57 (in Chinese). doi: 10.19693/j.issn.1673-3185.01258
[4] LIU L, WANG D, PENG Z H. State recovery and disturbance estimation of unmanned surface vehicles based on nonlinear extended state observers[J]. Ocean Engineering, 2019, 171: 625–632. doi: 10.1016/j.oceaneng.2018.11.008
[5] 张兰勇, 韩宇. 基于改进的RRT*算法的AUV集群路径规划[J]. 中国舰船研究, 2023, 18(1): 43–51. doi: 10.19693/j.issn.1673-3185.02879 ZHANG L Y, HAN Y. AUV cluster path planning based on improved RRT* algorithm[J]. Chinese Journal of Ship Research, 2023, 18(1): 43–51 (in both Chinese and English). doi: 10.19693/j.issn.1673-3185.02879
[6] 欧阳子路, 王鸿东, 黄一, 等. 基于改进RRT算法的无人艇编队路径规划技术[J]. 中国舰船研究, 2023, 15(3): 18–24. doi: 10.19693/j.issn.1673-3185.01639 OUYANG Z L, WANG H D, HUANG Y, et al. Path planning technologies for USV formation based on improved RRT[J]. Chinese Journal of Ship Research, 2023, 15(3): 18–24 (in both Chinese and English). doi: 10.19693/j.issn.1673-3185.01639
[7] GAO S N, PENG Z H, LIU L, et al. Coordinated target tracking by multiple unmanned surface vehicles with communication delays based on a distributed event-triggered extended state observer[J]. Ocean Engineering, 2021, 227: 108283. doi: 10.1016/j.oceaneng.2020.108283
[8] 刘祥, 叶晓明, 王泉斌, 等. 无人水面艇局部路径规划算法研究综述[J]. 中国舰船研究, 2021, 16(增刊1): 1–10. LIU X, YE X M, WANG Q B, et al. Review on the research of local path planning algorithms for unmanned surface vehicles[J]. Chinese Journal of Ship Research, 2021, 16(Supp 1): 1–10 (in Chinese).
[9] 赵海彬. 多无人艇协同区域警戒算法研究[J]. 舰船科学技术, 2022, 44(7): 74–77. ZHAO H B. Research on the distributed algorithm for multi-USV cooperative regional alert[J]. Ship Science and Technology, 2022, 44(7): 74–77 (in Chinese).
[10] GABRIELY Y, RIMON E. Spanning-tree based coverage of continuous areas by a mobile robot[J]. Annals of Mathematics and Artificial Intelligence, 2001, 31(1/2/3/4): 77–98.
[11] AGMON N, HAZON N, KAMINKA G A. Constructing spanning trees for efficient multi-robot coverage[C]//Proceedings of 2006 IEEE International Conference on Robotics and Automation. Orlando: IEEE, 2006: 1698–1703.
[12] DONG W, LIU S S, DING Y, et al. An artificially weighted spanning tree coverage algorithm for decentralized flying robots[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1689–1698. doi: 10.1109/TASE.2020.2971324
[13] KAPOUTSIS A C, CHATZICHRISTOFIS S A, KOSMATOPOULOS E B. DARP: divide areas algorithm for optimal multi-robot coverage path planning[J]. Journal of Intelligent & Robotic Systems, 2017, 86(3/4): 663–680.
[14] MA Y, ZHAO Y J, LI Z X, et al. A new coverage path planning algorithm for unmanned surface mapping vehicle based on A-star based searching[J].Applied Ocean Research, 2022, 123: 103163.
[15] PAIS T, GAIOTTI M, BARSOTTI B. Evaluation of the residual capacity of a submarine for different limit states with various initial imperfection models[J]. Journal of Marine Science and Application, 2022, 21(2): 59–68. doi: 10.1007/s11804-022-00271-0
[16] WANG Y H, KIRUBARAJAN T, THARMARASA R, et al. Multiperiod coverage path planning and scheduling for airborne surveillance[J]. IEEE Transactions on Aerospace and Electronic Systems, 2018, 54(5): 2257–2273. doi: 10.1109/TAES.2018.2812538
[17] 邢博闻, 杨柳, 胡庆松, 等. 无人船全覆盖路径规划算法研究[J]. 兵器装备工程学报, 2022, 43(9): 28–33. XING B W, YANG L, HU Q S, et al. Research of unmanned ship based on artificial bee colony method[J]. Journal of Ordnance Equipment Engineering, 2022, 43(9): 28–33 (in Chinese).
[18] GAO L Y, LI P, QIN H D, et al. Mechatronic design and maneuverability analysis of a novel robotic shark[J]. Journal of Marine Science and Application, 2022, 21(2): 82–91. doi: 10.1007/s11804-022-00274-x
[19] LIU L, WANG D, PENG Z H, et al. Bounded neural network control for target tracking of underactuated autonomous surface vehicles in the presence of uncertain target dynamics[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(4): 1241–1249. doi: 10.1109/TNNLS.2018.2868978
[20] YORDANOVA V, GIPS B. Coverage path planning with track spacing adaptation for autonomous underwater vehicles[J]. IEEE Robotics and Automation Letters, 2020, 5(3): 4774–4780. doi: 10.1109/LRA.2020.3003886
[21] CAO Y, CHENG X H, MU J Z. Concentrated coverage path planning algorithm of UAV formation for aerial photography[J]. IEEE Sensors Journal, 2022, 22(11): 11098–11111. doi: 10.1109/JSEN.2022.3168840
-
期刊类型引用(2)
1. 吕旻高，古楠，刘陆，王安青，王丹，彭周华. 基于动态事件触发的多无人船协同路径跟踪控制. 中国舰船研究. 2025(01): 213-222 . 
本站查看
2. 姜涛，周兴阁，陈宇. 基于RRT*算法和DWA算法的分层结构路径规划策略. 计算机测量与控制. 2024(09): 241-248 . 百度学术
其他类型引用(2)
下载:
计量
- 文章访问数: 575
- HTML全文浏览量: 111
- PDF下载量: 138
- 被引次数: 4
