{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T19:13:09Z","timestamp":1774465989185,"version":"3.50.1"},"reference-count":40,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T00:00:00Z","timestamp":1680134400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["61973133"],"award-info":[{"award-number":["61973133"]}]},{"name":"National Natural Science Foundation of China","award":["2022CFA052"],"award-info":[{"award-number":["2022CFA052"]}]},{"name":"Natural Science Foundation of Hubei Province of China","award":["61973133"],"award-info":[{"award-number":["61973133"]}]},{"name":"Natural Science Foundation of Hubei Province of China","award":["2022CFA052"],"award-info":[{"award-number":["2022CFA052"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this paper, we investigate the algorithms for traversal exploration and path coverage of target regions using multiple agents, enabling the efficient deployment of a set of agents to cover a complex region. First, the original multi-agent path planning problem (mCPP) is transformed into several single-agent sub-problems, by dividing the target region into multiple balanced sub-regions, which reduces the explosive combinatorial complexity; subsequently, closed-loop paths are planned in each sub-region by the rapidly exploring random trees (RRT) algorithm to ensure continuous exploration and repeated visits to each node of the target region. On this basis, we also propose two improvements: for the corner case of narrow regions, the use of geodesic distance is proposed to replace the Eulerian distance in Voronoi partitioning, and the iterations for balanced partitioning can be reduced by more than one order of magnitude; the Dijkstra algorithm is introduced to assign a smaller weight to the path cost when the geodesic direction changes, which makes the region division more \u201ccohesive\u201d, thus greatly reducing the number of turns in the path and making it more robust. The final optimization algorithm ensures the following characteristics: complete coverage of the target area, wide applicability of multiple area shapes, reasonable distribution of exploration tasks, minimum average waiting time, and sustainable exploration without any preparation phase.<\/jats:p>","DOI":"10.3390\/s23073596","type":"journal-article","created":{"date-parts":[[2023,3,30]],"date-time":"2023-03-30T03:17:35Z","timestamp":1680146255000},"page":"3596","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning"],"prefix":"10.3390","volume":"23","author":[{"given":"Yijie","family":"Qin","sequence":"first","affiliation":[{"name":"School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430070, China"}]},{"given":"Lei","family":"Fu","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430070, China"}]},{"given":"Dingxin","family":"He","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430070, China"}]},{"given":"Zhiwei","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430070, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1002\/rob.20403","article-title":"Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots","volume":"28","author":"Barrientos","year":"2011","journal-title":"J. Field Robot."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3000","DOI":"10.1126\/scirobotics.abc3000","article-title":"Multidrone aerial surveys of penguin colonies in antarctica","volume":"5","author":"Shah","year":"2020","journal-title":"Sci. Robot."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Schartel, M., Burr, R., Mayer, W., Docci, N., and Waldschmidt, C. (2018, January 15\u201317). UAV-based ground penetrating synthetic aperture radar. Proceedings of the IEEE MTT-S International Conference on Microwaves for Intelligent Mobility, Munich, Germany.","DOI":"10.1109\/ICMIM.2018.8443503"},{"key":"ref_4","unstructured":"Hazon, N., and Kaminka, G.A. (2005, January 18\u201322). Redundancy, efficiency and robustness in multi-robot coverage. Proceedings of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain."},{"key":"ref_5","unstructured":"Moravec, H., and Elfes, A. (1985, January 25\u201328). High resolution maps from wide angle sonar. Proceedings of the IEEE International Conference Robotics and Automation, St. Louis, MO, USA."},{"key":"ref_6","unstructured":"Agmon, N., Hazon, N., and Kaminka, G.A. (2006, January 15\u201319). Constructing spanning trees for efficient multi-robot coverage. Proceedings of the 2006 IEEE International Conference on Robotics and Automation, Orlando, FL, USA."},{"key":"ref_7","unstructured":"Zheng, X., Jain, S., Koenig, S., and Kempe, D. (2005, January 2\u20136). Multi-robot forest coverage. Proceedings of the 2005 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada."},{"key":"ref_8","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_9","doi-asserted-by":"crossref","unstructured":"B\u00e4hnemann, R., Lawrance, N., Chung, J.J., Pantic, M., Siegwart, R., and Nieto, J. (2021, January 13). Revisiting Boustrophedon Coverage Path Planning as a Generalized Traveling Salesman Problem. Proceedings of the Field and Service Robotics: Results of the 12th International Conference, Singapore.","DOI":"10.1007\/978-981-15-9460-1_20"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1016\/j.robot.2013.09.004","article-title":"A survey on coverage path planning for robotics [J\/OL]","volume":"61","author":"Galceran","year":"2013","journal-title":"Robot. Auton. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Cabreira, T.M., Brisolara, L.B., and Paulo, R.F.J. (2019). Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones, 3.","DOI":"10.3390\/drones3010004"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/TIT.1983.1056648","article-title":"Some NP-hard polygon decomposition problems","volume":"29","author":"Supowit","year":"1983","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Latombe, J.C. (1991). Robot Motion Planning, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"ref_14","unstructured":"Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L., and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementation, The MIT Press."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1007\/s10846-016-0348-x","article-title":"Coverage path planning for UAVs photogrammetry with energy and resolution constraints","volume":"83","author":"Franco","year":"2016","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_16","unstructured":"Choset, H., and Pignon, P. (1998). Field and Service Robotics, Springer."},{"key":"ref_17","unstructured":"Choset, H., Acar, E., Rizzi, A.A., and Luntz, J. (2000, January 24\u201328). Exact cellular decompositions in terms of critical points of Morse functions. Proceedings of the 2000 ICRA, San Francisco, CA, USA."},{"key":"ref_18","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_19","unstructured":"Acar, E.U., and Choset, H. (November, January 29). Robust sensor-based coverage of unstructured environments. Proceedings of the IEEE\/RSJ International Intelligent Robots and Systems Conference, Maui, HI, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1177\/027836402320556368","article-title":"Sensor-based coverage of unknown environments: Incremental construction of morse decompositions","volume":"21","author":"Acar","year":"2002","journal-title":"Int. J. Robot. Res."},{"key":"ref_21","unstructured":"Wong, S.C., and MacDonald, B.A. (2003, January 27\u201331). A topological coverage algorithm for mobile robots. Proceedings of the IEEE\/RSJ International Conference Intelligent Robots and Systems, IROS 2003, Las Vegas, NV, USA."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Wong, S.C., and MacDonald, B.A. (2014, January 9\u201313). Complete coverage by mobile robots using slice decomposition based on natural landmarks. Proceedings of the PRICAI 2004: Trends in Artificial Intelligence, Auckland, New Zealand.","DOI":"10.1007\/978-3-540-28633-2_72"},{"key":"ref_23","unstructured":"Wong, S.C. (2006). Qualitative Topological Coverage of Unknown Environments by Mobile Robots. [Ph.D. Thesis, The University of Auckland]."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sergiyenko, O.Y., Flores-Fuentes, W., and Mercorelli, P. (2019). Machine Vision and Navigation, Springer.","DOI":"10.1007\/978-3-030-22587-2"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.robot.2011.05.004","article-title":"A new global optimization strategy for coordinated multi-robot exploration: Development and comparative evaluation","volume":"59","author":"Puig","year":"2011","journal-title":"Robot. Auton. Syst."},{"key":"ref_26","unstructured":"Sariel, S., and Balch, T. (2006, January 11\u201313). Efficient bids on task allocation for multi-robot exploration. Proceedings of the 19th International FLAIRS Conference, Melbourne, FL, USA."},{"key":"ref_27","unstructured":"Maza, I., and Ollero, A. (2007). Distributed Autonomous Robotic Systems, Springer."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s10514-021-10028-3","article-title":"Cooperative multi-UAV coverage mission planning platform for remote sensing applications","volume":"46","author":"Apostolidis","year":"2022","journal-title":"Auton. Robot."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/j.robot.2016.04.003","article-title":"Data transferring model determination in robotic group","volume":"83","author":"Sergiyenko","year":"2016","journal-title":"Robot. Auton. Syst."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"11262","DOI":"10.1109\/JSEN.2020.3007856","article-title":"3D Optical Machine Vision Sensors with Intelligent Data Management for Robotic Swarm Navigation Improvement","volume":"21","author":"Sergiyenko","year":"2021","journal-title":"IEEE Sens. J."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1016\/j.mechatronics.2010.10.009","article-title":"Coverage path planning for UAVs based on enhanced exact cellular decomposition method","volume":"21","author":"Li","year":"2011","journal-title":"Mechatronics"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/j.eswa.2016.02.007","article-title":"Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction","volume":"55","author":"Torres","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Guruprasad, K.R. (2019, January 2\u20136). X-stc: An extended spanning tree-based coverage algorithm for mobile robots. Proceedings of the Advances in Robotics, Chennai, India.","DOI":"10.1145\/3352593.3352662"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0004-3702(97)00078-7","article-title":"Learning metric-topological maps for indoor mobile robot navigation","volume":"99","author":"Thrun","year":"1998","journal-title":"Artif. Intell."},{"key":"ref_35","unstructured":"Meng, W. (2022). Key Technology Research from Calculating Approximate Geodesic Lines to Constructing Geodesic Voronoi Diagrams. [Ph.D. Thesis, Shandong University]."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/s12044-012-0076-5","article-title":"Fair partitions of polygons: An elementary introduction","volume":"122","author":"Nandakumar","year":"2012","journal-title":"Proc. Indian Acad. Sci. Math. Sci."},{"key":"ref_37","unstructured":"Chen, L. (2018). Study on Meshing Method and Optimization of Complex Free-Form Surface Meshing Structure. [Master\u2019s Thesis, Zhejiang University]."},{"key":"ref_38","first-page":"217","article-title":"Multi-adjacent-vertexes and Multi-shortest-paths Problem of Dijkstra Algorithm","volume":"41","author":"Wang","year":"2014","journal-title":"Comput. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1016610507833","article-title":"Spanning-tree based coverage of continuous areas by a mobile robot","volume":"31","author":"Gabriely","year":"2001","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10472-009-9120-2","article-title":"Efficient boustrophedon multirobot coverage: An algorithmic approach","volume":"52","author":"Rekleitis","year":"2009","journal-title":"Ann. Math. Artif. Intell."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/7\/3596\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:06:53Z","timestamp":1760123213000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/7\/3596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,30]]},"references-count":40,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["s23073596"],"URL":"https:\/\/doi.org\/10.3390\/s23073596","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,30]]}}}