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

Cai Chang; Chen Dan; Cai Lei

doi:10.12284/hyxb2024132

Volume 46 Issue 11

Nov. 2024

Turn off MathJax

Article Contents

Article Navigation > Haiyang Xuebao > 2024 > 46(11): 115-124

Cai Chang，Chen Dan，Cai Lei. Multi-AUV multi-regional coverage path planning based on coevolution[J]. Haiyang Xuebao，2024, 46(11)：115–124 doi: 10.12284/hyxb2024132

Citation:

Cai Chang，Chen Dan，Cai Lei. Multi-AUV multi-regional coverage path planning based on coevolution[J]. Haiyang Xuebao，2024, 46(11)：115–124 doi: 10.12284/hyxb2024132

Citation:

Cai Chang，Chen Dan，Cai Lei. Multi-AUV multi-regional coverage path planning based on coevolution[J]. Haiyang Xuebao，2024, 46(11)：115–124 doi: 10.12284/hyxb2024132

PDF( 2256 KB)

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

doi: 10.12284/hyxb2024132

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

Received Date: 2024-09-02
Rev Recd Date: 2024-11-04

Available Online: 2024-11-21

Publish Date: 2024-11-01

Abstract

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

FullText(HTML)

References(26)

References

[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]. Ulsan: Ulsan National Institute of Science and Technology, 2022.
[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.