{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T06:20:01Z","timestamp":1774506001286,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T00:00:00Z","timestamp":1677283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Science and Technology Innovation 2030 Major Project","award":["2020AAA0104802"],"award-info":[{"award-number":["2020AAA0104802"]}]},{"name":"Science and Technology Innovation 2030 Major Project","award":["91948303-1"],"award-info":[{"award-number":["91948303-1"]}]},{"name":"National Natural Science Foundation of China","award":["2020AAA0104802"],"award-info":[{"award-number":["2020AAA0104802"]}]},{"name":"National Natural Science Foundation of China","award":["91948303-1"],"award-info":[{"award-number":["91948303-1"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Coverage path planning (CPP) of multiple Dubins robots has been extensively applied in aerial monitoring, marine exploration, and search and rescue. Existing multi-robot coverage path planning (MCPP) research use exact or heuristic algorithms to address coverage applications. However, several exact algorithms always provide precise area division rather than coverage paths, and heuristic methods face the challenge of balancing accuracy and complexity. This paper focuses on the Dubins MCPP problem of known environments. Firstly, we present an exact Dubins multi-robot coverage path planning (EDM) algorithm based on mixed linear integer programming (MILP). The EDM algorithm searches the entire solution space to obtain the shortest Dubins coverage path. Secondly, a heuristic approximate credit-based Dubins multi-robot coverage path planning (CDM) algorithm is presented, which utilizes the credit model to balance tasks among robots and a tree partition strategy to reduce complexity. Comparison experiments with other exact and approximate algorithms demonstrate that EDM provides the least coverage time in small scenes, and CDM produces a shorter coverage time and less computation time in large scenes. Feasibility experiments demonstrate the applicability of EDM and CDM to a high-fidelity fixed-wing unmanned aerial vehicle (UAV) model.<\/jats:p>","DOI":"10.3390\/s23052560","type":"journal-article","created":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T02:10:46Z","timestamp":1677463846000},"page":"2560","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["Exact and Heuristic Multi-Robot Dubins Coverage Path Planning for Known Environments"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8645-0392","authenticated-orcid":false,"given":"Lin","family":"Li","sequence":"first","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dianxi","family":"Shi","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, China"},{"name":"Tianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Songchang","family":"Jin","sequence":"additional","affiliation":[{"name":"Artificial Intelligence Research Center (AIRC), Defense Innovation Institute, Beijing 100073, China"},{"name":"Tianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaowu","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenlei","family":"Zhou","sequence":"additional","affiliation":[{"name":"Tianjin Artificial Intelligence Innovation Center (TAIIC), Tianjin 300456, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaoning","family":"Lian","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hengzhu","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Computer, National University of Defense Technology, Changsha 410003, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"101005","DOI":"10.1016\/j.swevo.2021.101005","article-title":"Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system","volume":"69","author":"Chen","year":"2022","journal-title":"Swarm Evol. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Fevgas, G., Lagkas, T., Argyriou, V., and Sarigiannidis, P. (2022). Coverage path planning methods focusing on energy efficient and cooperative strategies for unmanned aerial vehicles. Sensors, 22.","DOI":"10.3390\/s22031235"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Karapetyan, N., Moulton, J., Lewis, J.S., Li, A.Q., O\u2019Kane, J.M., and Rekleitis, I. (2018, January 21\u201325). Multi-robot dubins coverage with autonomous surface vehicles. Proceedings of the 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia.","DOI":"10.1109\/ICRA.2018.8460661"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"25546","DOI":"10.1109\/TITS.2021.3066240","article-title":"A clustering-based coverage path planning method for autonomous heterogeneous UAVs","volume":"23","author":"Chen","year":"2022","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Karapetyan, N., Benson, K., McKinney, C., Taslakian, P., and Rekleitis, I. (2017, January 24\u201328). Efficient multi-robot coverage of a known environment. Proceedings of the 2017 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8206000"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Coombes, M., Chen, W.H., and Liu, C. (2019, January 20\u201324). Flight testing Boustrophedon coverage path planning for fixed wing UAVs in wind. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.","DOI":"10.1109\/ICRA.2019.8793943"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wilson, J.P., Mittal, K., and Gupta, S. (2019, January 27\u201331). Novel motion models for time-optimal risk-aware motion planning for variable-speed AUVs. Proceedings of the OCEANS 2019 MTS\/IEEE SEATTLE, Seattle, WA, USA.","DOI":"10.23919\/OCEANS40490.2019.8962644"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"5445","DOI":"10.1109\/LRA.2022.3154006","article-title":"Online coverage planning for an autonomous weed mowing robot with curvature constraints","volume":"7","author":"Maini","year":"2022","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Deng, D., Jing, W., Fu, Y., Huang, Z., Liu, J., and Shimada, K. (2019, January 3\u20138). Constrained heterogeneous vehicle path planning for large-area coverage. Proceedings of the 2019 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Macau, China.","DOI":"10.1109\/IROS40897.2019.8968299"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/2372560","article-title":"On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents","volume":"79","author":"Dubins","year":"1957","journal-title":"Am. J. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10472-009-9120-2","article-title":"Efficient boustrophedon multi-robot coverage: An algorithmic approach","volume":"52","author":"Rekleitis","year":"2008","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"119310","DOI":"10.1109\/ACCESS.2021.3108177","article-title":"A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms","volume":"9","author":"Tan","year":"2021","journal-title":"IEEE Access"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Cabreira, T.M., Brisolara, L.B., and Ferreira, P.R. (2019). Survey on coverage path planning with unmanned aerial vehicles. Drones, 3.","DOI":"10.3390\/drones3010004"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.comcom.2019.10.014","article-title":"Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges","volume":"149","author":"Aggarwal","year":"2020","journal-title":"Comput. Commun."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Yu, X., Jin, S., Shi, D., Li, L., Kang, Y., and Zou, J. (2020, January 11\u201314). Balanced multi-region coverage path planning for unmanned aerial vehicles. Proceedings of the 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Toronto, ON, Canada.","DOI":"10.1109\/SMC42975.2020.9283426"},{"key":"ref_16","first-page":"101","article-title":"On Complete Coverage Path Planning Algorithms for Non-holonomic Mobile Robots: Survey and Challenges","volume":"33","author":"Khan","year":"2017","journal-title":"J. Inf. Sci. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"17298806221091685","DOI":"10.1177\/17298806221091685","article-title":"Complete coverage problem of multiple robots with different velocities","volume":"19","author":"Li","year":"2022","journal-title":"Int. J. Adv. Robot. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"16842","DOI":"10.1109\/TITS.2021.3131473","article-title":"An adaptive clustering-based algorithm for automatic path planning of heterogeneous UAVs","volume":"23","author":"Chen","year":"2021","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Rafael Marti, G.R. (2022). Exact and Heuristic Methods in Combinatorial Optimization, Springer.","DOI":"10.1007\/978-3-662-64877-3_2"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.eswa.2018.09.001","article-title":"Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm","volume":"116","author":"Zhou","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.amc.2014.03.098","article-title":"A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem","volume":"237","year":"2014","journal-title":"Appl. Math. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1007\/s10846-016-0458-5","article-title":"Algorithms for heterogeneous, multiple depot, multiple unmanned vehicle path planning problems","volume":"88","author":"Sundar","year":"2017","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Vandermeulen, I., Gro\u00df, R., and Kolling, A. (2019, January 20\u201324). Turn-minimizing multirobot coverage. Proceedings of the 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada.","DOI":"10.1109\/ICRA.2019.8794002"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Yu, X., Roppel, T.A., and Hung, J.Y. (2015, January 9\u201312). An optimization approach for planning robotic field coverage. Proceedings of the IECON 2015-41st Annual Conference of the IEEE Industrial Electronics Society, Yokohama, Japan.","DOI":"10.1109\/IECON.2015.7392728"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1007\/s10514-018-09820-5","article-title":"Dynamic task allocation in an uncertain environment with heterogeneous multi-agents","volume":"43","author":"ElGibreen","year":"2019","journal-title":"Auton. Robot."},{"key":"ref_26","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_27","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_28","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_29","doi-asserted-by":"crossref","unstructured":"Zhou, X., Wang, H., and Ding, B. (2018, January 21\u201325). How Many Robots are Enough: A Multi-Objective Genetic Algorithm for the Single-Objective Time-Limited Complete Coverage Problem. Proceedings of the IEEE 2018 International Conference on Robotics and Automation (ICRA), Brisbane, Australia.","DOI":"10.1109\/ICRA.2018.8461028"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Wang, X., Jiang, P., Li, D., and Sun, T. (2017). Curvature continuous and bounded path planning for fixed-wing UAVs. Sensors, 17.","DOI":"10.3390\/s17092155"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"\u0160elek, A., Seder, M., Brezak, M., and Petrovi\u0107, I. (2022). Smooth Complete Coverage Trajectory Planning Algorithm for a Nonholonomic Robot. Sensors, 22.","DOI":"10.3390\/s22239269"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Duckett, T., Pearson, S., Blackmore, S., Grieve, B., Chen, W.H., Cielniak, G., Cleaversmith, J., Dai, J., Davis, S., and Fox, C. (2018). Agricultural robotics: The future of robotic agriculture. arXiv.","DOI":"10.31256\/WP2018.2"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Xu, A., Viriyasuthee, C., and Rekleitis, I. (2011, January 9\u201313). Optimal complete terrain coverage using an unmanned aerial vehicle. Proceedings of the 2011 IEEE International Conference on Robotics and Automation, Shanghai, China.","DOI":"10.1109\/ICRA.2011.5979707"},{"key":"ref_34","unstructured":"Yu, X. (2015). Optimization Approaches for a Dubins Vehicle in Coverage Planning Problem and Traveling Salesman Problems. [Ph.D. Thesis, AUBURN Univerisity]."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Lewis, J.S., Edwards, W., Benson, K., Rekleitis, I., and O\u2019Kane, J.M. (2017, January 24\u201328). Semi-boustrophedon coverage with a dubins vehicle. Proceedings of the 2017 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8206451"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulation of traveling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"J. ACM (JACM)"},{"key":"ref_37","first-page":"159","article-title":"The gurobi optimizer","volume":"41","author":"Bixby","year":"2007","journal-title":"Transp. Res. Part B"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","article-title":"On the worst-case performance of some algorithms for the asymmetric traveling salesman problem","volume":"12","author":"Frieze","year":"1982","journal-title":"Networks"},{"key":"ref_39","unstructured":"Romero, P. (2022, December 19). Simulink Drone Reference Application. Available online: https:\/\/github.com\/mathworks\/simulinkDrone\\ReferenceApp\/releases\/tag\/v2.1."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/5\/2560\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:42:24Z","timestamp":1760121744000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/5\/2560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,25]]},"references-count":39,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["s23052560"],"URL":"https:\/\/doi.org\/10.3390\/s23052560","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,25]]}}}