基于协同进化的多AUV多区域覆盖路径规划

蔡畅; 陈丹; 蔡磊

doi:10.12284/hyxb2024132

基于协同进化的多AUV多区域覆盖路径规划

doi: 10.12284/hyxb2024132

蔡畅^1,,
陈丹¹,
蔡磊^2, ,

1.
石家庄铁道大学信息科学与技术学院，河北石家庄 050043
2.
西北工业大学自动化学院，陕西西安 710072

基金项目: 国家自然科学基金（62071383）。

详细信息

作者简介:
蔡畅（1993—），女，河北省辛集市人，博士，主要从事自主水下航行器、覆盖路径规划、多机器人系统方向的研究。 E-mail：caichang@stdu.edu.cn

通讯作者:
蔡磊，博士，主要从事交通运输工程研究。 E-mail: caileilei@mail.nwpu.edu.cn

中图分类号: TP249
计量
- 文章访问数: 107
- HTML全文浏览量: 41
- PDF下载量: 27
- 被引次数: 0
出版历程
- 收稿日期: 2024-09-02
- 修回日期: 2024-11-04
- 网络出版日期: 2024-11-21

Multi-AUV multi-regional coverage path planning based on coevolution

Cai Chang^1
,,
Chen Dan¹,
Cai Lei^{2
, ,}

1.
School of Information and Science Technology, Shijiazhuang Tiedao University, Shijiazhuang 050043, China
2.
School of Automation, Northwestern Polytechnical University, Xi’an 710072, China

摘要

摘要: 针对多自主水下航行器（Autonomous Underwater Vehicle, AUV）水下覆盖任务过程中的突发情况，研究了多AUV的覆盖路径重规划问题，提出了一种多机器人−多区域覆盖路径规划（Multi-robot Multi-regional Coverage Path Planning, M²CPP）方法，为可用AUV重新分配未覆盖区域并规划覆盖路径。首先，通过割草机算法确定每个区域中的内部路径和候选入口位置。然后，采用协同进化方法求解最优的区域分配、区域顺序及各区域的最优入口，3个种群协同进化，共同决定所有AUV的完整路径，保证种群多样性，避免陷入局部最优。仿真结果表明，本文方法在根据初始位置和剩余能量为多AUV重规划较短路径的基础上，优化路径结构，保证多AUV工作量均衡，可以较好解决该背景下的路径重规划问题。
- 多机器人多区域覆盖路径规划 /
- 覆盖路径重规划 /
- 多AUV系统 /
- 协同进化 /
- 任务分配
Abstract: In response to contingencies that arise during the underwater coverage missions of multiple autonomous underwater vehicles (AUVs), this study addresses the problem of coverage path replanning for multiple AUVs. A multi-robot multi-regional coverage path planning (M²CPP) method is proposed to reassign uncovered areas to available AUVs and plan their coverage paths. Initially, the lawnmower algorithm is employed to determine the internal paths and candidate entry points within each region. Subsequently, a coevolutionary approach is utilized to solve for the optimal region allocation, region sequence, and the best entry points for each region. Three populations coevolve collaboratively to determine the complete paths for all AUVs, ensuring population diversity and preventing convergence into local optima. Simulation results demonstrate that the proposed method not only replans shorter paths for multiple AUVs based on their initial positions and remaining energy but also optimizes the path structure to ensure a balanced workload among the AUVs, effectively resolving the replanning issue under such scenarios.
- multi-robot multi-regional coverage path planning /
- coverage path replanning /
- multi-AUV system /
- coevolution /
- task allocation

HTML全文

图 1 路径结构图

Fig. 1 Path structure

下载: 全尺寸图片幻灯片

图 2 本文提出的多AUV多区域覆盖路径规划方法流程图

Fig. 2 Flowchart of the proposed path planning method for multi-AUV and multi-area coverage

下载: 全尺寸图片幻灯片

图 3 同一区域中不同方向上的两种LM覆盖路径

Fig. 3 Two types of LM coverage paths in different directions in the same area

下载: 全尺寸图片幻灯片

图 4 协同进化方法的总体流程

Fig. 4 Overall flowchart of the co-evolution method

下载: 全尺寸图片幻灯片

图 5 3个种群中的示例个体

Fig. 5 Example individuals in the three populations

下载: 全尺寸图片幻灯片

图 6 交叉、变异、交换和反转4种进化操作

Fig. 6 Four evolutionary operations: crossover, mutation, swap and inversion

下载: 全尺寸图片幻灯片

图 7 仿真初始场景

Fig. 7 Simulation of the initial scenario

下载: 全尺寸图片幻灯片

图 8 由LMCC方法(a)、GA算法(b)和BiCC方法(c)生成的最终路径

Fig. 8 Final paths generated by the LMCC method (a), GA algorithm (b), and BiCC method (c)

下载: 全尺寸图片幻灯片

图 9 本文方法中代价函数值的收敛过程

Fig. 9 Convergence of cost function values in the proposed method

下载: 全尺寸图片幻灯片

表 1 参数设置

Tab. 1 Parameter settings

分类	变量	数值
基本参数	区域个数（Nr）	6
	AUV个数（Na）	3
	AUV剩余能量（E）	{0.39, 0.89, 0.65}
	AUV位置（P）	{(800,2200), (1200 200), (4600 1000)}
	声呐量程（Ws）	200
合作协同进化方法参数	种群规模（Np）	100
	种群个数（NP）	3
	最大迭代次数（maxIte）	400
	交叉概率（Pc）	0.2
	变异概率（Pm）	0.2

下载: 导出CSV

表 2 各AUV的路径长度对比

Tab. 2 Comparison of the path length of each AUV

	本文方法	GA	BiCC
AUV $A_1 $	2248	5540	10180
AUV $A_2 $	9738	12640	1133
AUV $A_3 $	5978	9218	5978
总长度	17964	27398	17291

下载: 导出CSV

表 3 本文方法得到的各AUV预期工作量、实际工作量和工作量偏差

Tab. 3 The expected workload, actual workload and workload deviation of each AUV obtained by the proposed method

	预期工作量	实际工作量	工作量偏差
AUV $A_1 $	0.202	0.125	0.077
AUV $A_2 $	0.461	0.542	0.081
AUV $A_3 $	0.337	0.333	0.004

下载: 导出CSV

表 4 平均工作量偏差和平均$ {H}_{3} $对比

Tab. 4 Comparison of average workload deviation and average $ {H}_{3} $

	本文方法		GA	BiCC
平均工作量偏差	0.0540		0.0002	0.2637
平均$ {H}_{3} $	0.1360		0.4553	0.1564
	AUV $A_1 $	0.067
	AUV $A_2 $	0.127
	AUV $A_3 $	0.214

下载: 导出CSV

参考文献(26)

[1]	周晶, 司玉林, 林渊, 等. 海底AUV关键技术综述[J]. 海洋学报, 2023, 45(10): 1−12. Zhou Jing, Si Yulin, Lin Yuan, et al. A review of subsea AUV technology[J]. Haiyang Xuebao, 2023, 45(10): 1−12.
[2]	Cai Chang, Chen Jianfeng, Yan Qingli, et al. A prior information–based coverage path planner for underwater search and rescue using autonomous underwater vehicle (AUV) with side–scan sonar[J]. IET Radar, Sonar & Navigation, 2022, 16(7): 1225-1239.
[3]	黄琰, 李岩, 俞建成, 等. AUV智能化现状与发展趋势[J]. 机器人, 2020, 42(2): 215−231. Huang Yan, Li Yan, Yu Jiancheng, et al. State-of-the-art and development trends of AUV intelligence[J]. Robot, 2020, 42(2): 215−231.
[4]	Matos A, Martins A, Dias A, et al. Multiple robot operations for maritime search and rescue in euRathlon 2015 competition[C]//Proceedings of the OCEANS 2016 - Shanghai. Shanghai: IEEE, 2016.
[5]	朱大奇, 胡震. 深海潜水器研究现状与展望[J]. 安徽师范大学学报(自然科学版), 2018, 41(3): 205−216. Zhu Daqi, Hu Zhen. Research status and prospect of deep-sea underwater vehicle[J]. Journal of Anhui Normal University (Natural Science), 2018, 41(3): 205−216.
[6]	Ai Bo, Jia Maoxin, Xu Hanwen, et al. Coverage path planning for maritime search and rescue using reinforcement learning[J]. Ocean Engineering, 2021, 241: 110098.
[7]	Song Junnan, Gupta S. CARE: cooperative autonomy for resilience and efficiency of robot teams for complete coverage of unknown environments under robot failures[J]. Autonomous Robots, 2020, 44(3/4): 647−671.
[8]	Sun Chun, Tang Jingtao, Zhang Xinyu. FT-MSTC^*: an efficient fault tolerance algorithm for multi-robot coverage path planning[C]//Proceedings of 2021 IEEE International Conference on Real-time Computing and Robotics. Xining: IEEE, 2021.
[9]	Yazici A, Kirlik G, Parlaktuna O, et al. A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J]. IEEE Transactions on Cybernetics, 2014, 44(3): 305−314.
[10]	Xie Junfei, Carrillo L R G, Jin Lei. An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems[J]. IEEE Control Systems Letters, 2019, 3(1): 67−72. doi: 10.1109/LCSYS.2018.2851661
[11]	Xie Junfei, Chen Jun. Multiregional coverage path planning for multiple energy constrained UAVs[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(10): 17366−17381. doi: 10.1109/TITS.2022.3160402
[12]	Kim G. Multi-agent deep reinforcement learning for multi-regional coverage path planning[D/OL]. Ulsan: Ulsan National Institute of Science and Technology, 2021[引用日期].网址. Kim G. Multi-agent deep reinforcement learning for multi-regional coverage path planning[D/OL]. Ulsan: Ulsan National Institute of Science and Technology, 2021[引用日期].网址.
[13]	Shao Xianxin, Gong Yuejiao, Zhan Zhihui, et al. Bipartite cooperative coevolution for energy-aware coverage path planning of UAVs[J]. IEEE Transactions on Artificial Intelligence, 2022, 3(1): 29−42. doi: 10.1109/TAI.2021.3103143
[14]	金磊磊, 梁红, 杨长生. 基于卷积神经网络的水下目标声呐图像识别方法[J]. 西北工业大学学报, 2021, 39(2): 285−291. doi: 10.1051/jnwpu/20213920285 Jin Leilei, Liang Hong, Yang Changsheng. Sonar image recognition of underwater target based on convolutional neural network[J]. Journal of Northwestern Polytechnical University, 2021, 39(2): 285−291. doi: 10.1051/jnwpu/20213920285
[15]	Zhou Hexiong, Zeng Zheng, Lian Lian. Adaptive re-planning of AUVs for environmental sampling missions: a fuzzy decision support system based on multi-objective particle swarm optimization[J]. International Journal of Fuzzy Systems, 2018, 20(2): 650−671. doi: 10.1007/s40815-017-0398-7
[16]	Viet H H, Dang V H, Choi S, et al. BoB: an online coverage approach for multi-robot systems[J]. Applied Intelligence, 2015, 42(2): 157−173. doi: 10.1007/s10489-014-0571-8
[17]	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.
[18]	Connell D, Manh La H. Extended rapidly exploring random tree–based dynamic path planning and replanning for mobile robots[J]. International Journal of Advanced Robotic Systems, 2018, 15(3): 255903605.
[19]	赵荞荞, 张立川, 刘禄, 等. 水下仿生机器人集群节能关键技术综述[J]. 西北工业大学学报, 2022, 40(3): 576−583. doi: 10.3969/j.issn.1000-2758.2022.03.013 Zhao Qiaoqiao, Zhang Lichuan, Liu Lu, et al. Review on energy-saving key technologies of underwater bionic robot swarm[J]. Journal of Northwestern Polytechnical University, 2022, 40(3): 576−583. doi: 10.3969/j.issn.1000-2758.2022.03.013
[20]	Choset H. Coverage of known spaces: the boustrophedon cellular decomposition[J]. Autonomous Robots, 2000, 9(3): 247−253. doi: 10.1023/A:1008958800904
[21]	Galceran E, Carreras M. A survey on coverage path planning for robotics[J]. Robotics and Autonomous Systems, 2013, 61(12): 1258−1276.
[22]	Kapetanović N, Mišković N, Tahirović A, et al. A side-scan sonar data-driven coverage planning and tracking framework[J]. Annual Reviews in Control, 2018, 46: 268−280. doi: 10.1016/j.arcontrol.2018.10.012
[23]	Lakshmi M D, Murugan S S. Keypoint-based mapping analysis on transformed side scan sonar images[J]. Multimedia Tools and Applications, 2020, 79(35/36): 26703−26733.
[24]	Wu Meng, Zhu Xiaomin, Ma Li, et al. Torch: strategy evolution in swarm robots using heterogeneous–homogeneous coevolution method[J]. Journal of Industrial Information Integration, 2022, 25: 100239.
[25]	Miguel Antonio L, Coello Coello C A. Coevolutionary multiobjective evolutionary algorithms: survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(6): 851−865. doi: 10.1109/TEVC.2017.2767023
[26]	Wang Boqun, Zhang Hailong, Nie Jun, et al. Multipopulation genetic algorithm based on GPU for solving TSP problem[J]. Mathematical Problems in Engineering, 2020, 2020: 1398595.