{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T17:56:09Z","timestamp":1776275769093,"version":"3.50.1"},"reference-count":45,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T00:00:00Z","timestamp":1671840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62071383"],"award-info":[{"award-number":["62071383"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Remote Sensing"],"abstract":"<jats:p>In this study, we focus on the Multi-robot Coverage Path Planning (MCPP) problem for maritime Search And Rescue (SAR) missions using a multiple Autonomous Underwater Vehicle (AUV) system, with the ultimate purpose of efficiently and accurately discovering the target from sonar images taken by Side-Scan Sonar (SSS) mounted on the AUVs. Considering the specificities of real maritime SAR projects, we propose a novel MCPP method, in which the MCPP problem is transformed into two sub-problems: Area partitioning and single-AUV coverage path planning. The structure of the task area is first defined using Morse decomposition of the spike pattern. The area partitioning problem is then formulated as an AUV ordering problem, which is solved by developing a customized backtracking method to balance the workload and to avoid segmentation of the possible target area. As for the single-AUV coverage path planning problem, the SAR-A* method is adopted, which generates a path that preferentially visits the possible target areas and reduces the number of turns to guarantee the high quality of the resulting sonar images. Simulation results demonstrate that the proposed method can maintain the workload balance and significantly improve the efficiency and accuracy of discovering the target. Moreover, our experimental results indicate that the proposed method is practical and the mentioned specificities are useful for discovering targets.<\/jats:p>","DOI":"10.3390\/rs15010093","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T07:31:56Z","timestamp":1672126316000},"page":"93","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":66,"title":["A Multi-Robot Coverage Path Planning Method for Maritime Search and Rescue Using Multiple AUVs"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8164-2798","authenticated-orcid":false,"given":"Chang","family":"Cai","sequence":"first","affiliation":[{"name":"School of Marine Science and Technology, Northwestern Polytechnical University, Xi\u2019an 710072, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7281-7138","authenticated-orcid":false,"given":"Jianfeng","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Marine Science and Technology, Northwestern Polytechnical University, Xi\u2019an 710072, China"}]},{"given":"Qingli","family":"Yan","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Xi\u2019an University of Posts and Telecommunications, Xi\u2019an 710121, China"}]},{"given":"Fen","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Marine Science and Technology, Northwestern Polytechnical University, Xi\u2019an 710072, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,12,24]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Grza\u0327dziel, A. (2020). Results from developments in the use of a scanning sonar to support diving operations from a rescue ship. Remote Sens., 12.","DOI":"10.3390\/rs12040693"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Yu, Y., Zhao, J., Gong, Q., Huang, C., Zheng, G., and Ma, J. (2021). Real-time underwater maritime object detection in side-scan sonar images based on transformer-YOLOv5. Remote Sens., 13.","DOI":"10.3390\/rs13183555"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"7700","DOI":"10.1109\/TII.2020.2974047","article-title":"Maritime search and rescue based on group mobile computing for unmanned aerial vehicles and unmanned surface vehicles","volume":"16","author":"Yang","year":"2020","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"107612","DOI":"10.1016\/j.cie.2021.107612","article-title":"Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations","volume":"161","author":"Cho","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Almadhoun, R., Taha, T., Seneviratne, L., and Zweiri, Y. (2019). A survey on multi-robot coverage path planning for model reconstruction and mapping. SN Appl. Sci., 1.","DOI":"10.1007\/s42452-019-0872-y"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1007\/s10514-020-09903-2","article-title":"An informative path planning framework for UAV-based terrain monitoring","volume":"44","author":"Hitz","year":"2020","journal-title":"Auton. Robot."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Rajan, R., Otte, M., and Sofge, D. (2018, January 18\u201321). Optimizing multiagent area coverage using dynamic global potential fields. Proceedings of the 2018 IEEE Symposium Series on Computational Intelligence (SSCI), Bangalore, India.","DOI":"10.1109\/SSCI.2018.8628840"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1109\/LRA.2018.2794578","article-title":"An evolutionary algorithm for online, resource-constrained, multivehicle sensing mission planning","volume":"3","author":"Tsiogkas","year":"2018","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"103078","DOI":"10.1016\/j.autcon.2020.103078","article-title":"Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot","volume":"112","author":"Lakshmanan","year":"2020","journal-title":"Autom. Constr."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1609","DOI":"10.1007\/s10514-017-9631-3","article-title":"Simultaneous area partitioning and allocation for complete coverage by multiple autonomous industrial robots","volume":"41","author":"Hassan","year":"2017","journal-title":"Auton. Robot."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1689","DOI":"10.1109\/TASE.2020.2971324","article-title":"An artificially weighted spanning tree coverage algorithm for decentralized flying robots","volume":"17","author":"Dong","year":"2020","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1007\/s10845-010-0404-5","article-title":"A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time","volume":"23","author":"Kapanoglu","year":"2010","journal-title":"J. Intell. Manuf."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1109\/TIE.2016.2609838","article-title":"Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots","volume":"64","author":"Luo","year":"2017","journal-title":"IEEE Trans. Ind. Electron."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1016\/j.robot.2010.01.005","article-title":"Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach","volume":"58","author":"Sipahioglu","year":"2010","journal-title":"Robot. Auton. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0377-2217(85)90252-8","article-title":"The fleet size and mix problem for capacitated arc routing","volume":"22","author":"Ulusoy","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/TCYB.2013.2253605","article-title":"A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints","volume":"44","author":"Yazici","year":"2014","journal-title":"IEEE Trans. Cybern."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"106316","DOI":"10.1016\/j.oceaneng.2019.106316","article-title":"Multi-robot global sonar survey in the presence of strong currents","volume":"188","author":"Kim","year":"2019","journal-title":"Ocean Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/s10846-016-0461-x","article-title":"DARP: Divide areas algorithm for optimal multi-robot coverage path planning","volume":"86","author":"Kapoutsis","year":"2017","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1017\/S0263574719001127","article-title":"GM-VPC: An algorithm for multi-robot coverage of known spaces using generalized voronoi partition","volume":"38","author":"Nair","year":"2019","journal-title":"Robotica"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2189","DOI":"10.1007\/s10489-021-02483-3","article-title":"Multi-robot exploration in task allocation problem","volume":"52","author":"Alitappeh","year":"2021","journal-title":"Appl. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1007\/s10846-017-0559-9","article-title":"Area partition for coastal regions with multiple UAS","volume":"88","author":"Balampanis","year":"2017","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s10489-014-0571-8","article-title":"BoB: An online coverage approach for multi-robot systems","volume":"42","author":"Viet","year":"2014","journal-title":"Appl. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1023\/A:1008958800904","article-title":"Coverage of known spaces: The boustrophedon cellular decomposition","volume":"9","author":"Choset","year":"2000","journal-title":"Auton. Robot."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1827","DOI":"10.1109\/TMECH.2012.2213607","article-title":"Sensor-driven online coverage planning for autonomous underwater vehicles","volume":"18","author":"Paull","year":"2013","journal-title":"IEEE\/ASME Trans. Mechatron."},{"key":"ref_25","first-page":"92","article-title":"A maritime search and rescue location analysis considering multiple criteria, with simulated demand","volume":"56","author":"Akbari","year":"2017","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"OTOTE, D.A., Li, B., Ai, B., Gao, S., Xu, J., Chen, X., and Lv, G. (2019). A decision-making algorithm for maritime search and rescue plan. Sustainability, 11.","DOI":"10.3390\/su11072084"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"110050","DOI":"10.1016\/j.oceaneng.2021.110050","article-title":"AUV path planning for coverage search of static target in ocean environment","volume":"241","author":"Yao","year":"2021","journal-title":"Ocean Eng."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Zhu, B., Wang, X., Chu, Z., Yang, Y., and Shi, J. (2019). Active learning for recognition of shipwreck target in side-scan sonar image. Remote Sens., 11.","DOI":"10.3390\/rs11030243"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.oceaneng.2014.09.017","article-title":"Real time map generation using sidescan sonar scanlines for unmanned underwater vehicles","volume":"91","author":"Chen","year":"2014","journal-title":"Ocean Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"115940","DOI":"10.1016\/j.eswa.2021.115940","article-title":"Toward energy-efficient online Complete Coverage Path Planning of a ship hull maintenance robot based on Glasius Bio-inspired Neural Network","volume":"187","author":"Muthugala","year":"2022","journal-title":"Expert Syst. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Collins, L., Ghassemi, P., Esfahani, E.T., Doermann, D., Dantu, K., and Chowdhury, S. (June, January 30). Scalable Coverage Path Planning of Multi-Robot Teams for Monitoring Non-Convex Areas. Proceedings of the 2021 IEEE International Conference on Robotics and Automation (ICRA), Xi\u2019an, China.","DOI":"10.1109\/ICRA48506.2021.9561550"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"172988142097046","DOI":"10.1177\/1729881420970461","article-title":"Multi-robot informative path planning in unknown environments through continuous region partitioning","volume":"17","author":"Dutta","year":"2020","journal-title":"Int. J. Adv. Robot. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Cai, C., Chen, J., Yan, Q., Liu, F., and Zhou, R. (2022). A prior information-based coverage path planner for underwater search and rescue using autonomous underwater vehicle (auv) with side-scan sonar. IET Radar Sonar Navig.","DOI":"10.1049\/rsn2.12256"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1109\/JOE.2009.2025155","article-title":"Probability of target presence for multistatic sonar ping sequencing","volume":"34","author":"Krout","year":"2009","journal-title":"IEEE J. Ocean Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1177\/027836402320556359","article-title":"Morse decompositions for coverage tasks","volume":"21","author":"Acar","year":"2002","journal-title":"Int. J. Robot. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.compeleceng.2019.02.024","article-title":"Complete coverage path planning for aerial vehicle flocks deployed in outdoor environments","volume":"75","author":"Guastella","year":"2019","journal-title":"Comput. Electr. Eng."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Balampanis, F., Maza, I., and Ollero, A. (2016, January 7\u201310). Area decomposition, partition and coverage with multiple remotely piloted aircraft systems operating in coastal regions. Proceedings of the 2016 International Conference on Unmanned Aircraft Systems (ICUAS), Arlington, VA, USA.","DOI":"10.1109\/ICUAS.2016.7502602"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1109\/TRO.2005.861455","article-title":"Sensor-based coverage with extended range detectors","volume":"22","author":"Acar","year":"2006","journal-title":"IEEE Trans. Robot."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jsco.1994.1035","article-title":"A multipurpose backtracking algorithm","volume":"18","author":"Priestley","year":"1994","journal-title":"J. Symb. Comput."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Guldal, S., Baugh, V., and Allehaibi, S. (April, January 30). N-Queens solving algorithm by sets and backtracking. Proceedings of the SoutheastCon 2016, Norfolk, VA, USA.","DOI":"10.1109\/SECON.2016.7506688"},{"key":"ref_41","first-page":"81","article-title":"Coverage path planning for 2d convex regions","volume":"97","author":"Valentin","year":"2019","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"4774","DOI":"10.1109\/LRA.2020.3003886","article-title":"Coverage path planning with track spacing adaptation for autonomous underwater vehicles","volume":"5","author":"Yordanova","year":"2020","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_43","unstructured":"Gabriely, Y., and Rimon, E. (2001, January 21\u201326). Spanning-tree based coverage of continuous areas by a mobile robot. Proceedings of the Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation, Seoul, Republic of Korea."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1017\/S0263574718000292","article-title":"Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys","volume":"36","author":"Freitas","year":"2018","journal-title":"Robotica"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"110098","DOI":"10.1016\/j.oceaneng.2021.110098","article-title":"Coverage path planning for maritime search and rescue using reinforcement learning","volume":"241","author":"Ai","year":"2021","journal-title":"Ocean Eng."}],"container-title":["Remote Sensing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2072-4292\/15\/1\/93\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:50:15Z","timestamp":1760147415000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2072-4292\/15\/1\/93"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,24]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["rs15010093"],"URL":"https:\/\/doi.org\/10.3390\/rs15010093","relation":{},"ISSN":["2072-4292"],"issn-type":[{"value":"2072-4292","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,24]]}}}