{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T10:43:01Z","timestamp":1762252981104,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:00:00Z","timestamp":1556409600000},"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":["61773031","61573042"],"award-info":[{"award-number":["61773031","61573042"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this paper, a multi-robot persistent coverage of the region of interest is considered, where persistent coverage and cooperative coverage are addressed simultaneously. Previous works have mainly concentrated on the paths that allow for repeated coverage, but ignored the coverage period requirements of each sub-region. In contrast, this paper presents a combinatorial approach for path planning, which aims to cover mission domains with different task periods while guaranteeing both obstacle avoidance and minimizing the number of robots used. The algorithm first deploys the sensors in the region to satisfy coverage requirements with minimum cost. Then it solves the travelling salesman problem to obtain the frame of the closed path. Finally, the approach partitions the closed path into the fewest segments under the coverage period constraints, and it generates the closed route for each robot on the basis of portioned segments of the closed path. Therefore, each robot can circumnavigate one closed route to cover the different task areas completely and persistently. The numerical simulations show that the proposed approach is feasible to implement the cooperative coverage in consideration of obstacles and coverage period constraints, and the number of robots used is also minimized.<\/jats:p>","DOI":"10.3390\/s19091994","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T02:57:32Z","timestamp":1556506652000},"page":"1994","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["A Novel Cooperative Path Planning for Multi-robot Persistent Coverage with Obstacles and Coverage Period Constraints"],"prefix":"10.3390","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8729-2856","authenticated-orcid":false,"given":"Guibin","family":"Sun","sequence":"first","affiliation":[{"name":"School of Automation Science and Electrical Engineering, Beihang University, Beijing 100083, China"}]},{"given":"Rui","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Automation Science and Electrical Engineering, Beihang University, Beijing 100083, China"}]},{"given":"Bin","family":"Di","sequence":"additional","affiliation":[{"name":"National Innovation Institute of Defense Technology, Academy of Military Sciences PLA China, Beijing 100071, China"}]},{"given":"Zhuoning","family":"Dong","sequence":"additional","affiliation":[{"name":"School of Automation Science and Electrical Engineering, Beihang University, Beijing 100083, China"}]},{"given":"Yingxun","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Automation Science and Electrical Engineering, Beihang University, Beijing 100083, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"3364","DOI":"10.1109\/TCYB.2015.2505737","article-title":"Decentralized patrolling under constraints in dynamic environments","volume":"46","author":"Chen","year":"2016","journal-title":"IEEE Trans. Cybern."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/j.ast.2017.05.031","article-title":"A potential game approach to multiple UAV cooperative search and surveillance","volume":"68","author":"Li","year":"2017","journal-title":"Aerosp. Sci. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.robot.2016.08.006","article-title":"Cooperative mapping of unknown environments by multiple heterogeneous mobile robots with limited sensing","volume":"87","author":"Masehian","year":"2017","journal-title":"Robot. Autom. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1177\/0278364917741969","article-title":"Probabilistic cooperative mobile robot area coverage and its application to autonomous seabed mapping","volume":"37","author":"Paull","year":"2018","journal-title":"Int. J. Robot. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"12395","DOI":"10.1109\/ACCESS.2018.2804899","article-title":"3D land mapping and land deformation monitoring using persistent scatterer interferometry (PSI) ALOS PALSAR: validated by geodetic GPS and UAV","volume":"6","author":"Razi","year":"2018","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"17841","DOI":"10.1109\/ACCESS.2018.2818733","article-title":"Multi-type UAVs cooperative task allocation under resource constraints","volume":"6","author":"Huang","year":"2018","journal-title":"IEEE Access"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1016\/j.robot.2013.06.011","article-title":"Distributed multi-robot patrol: A scalable and fault-tolerant framework","volume":"61","author":"Portugal","year":"2013","journal-title":"Robot. Autom. Syst."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1109\/TCST.2011.2167331","article-title":"Control of multiple UAVs for persistent surveillance: algorithm and flight test results","volume":"20","author":"Nigam","year":"2012","journal-title":"IEEE Trans. Control Syst. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1115\/1.4035874","article-title":"Cloud-supported coverage control for persistent surveillance missions","volume":"139","author":"Peters","year":"2017","journal-title":"J. Dyn. Syst. Meas. Contr."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10514-013-9364-x","article-title":"Efficient complete coverage of a known arbitrary environment with applications to aerial operations","volume":"36","author":"Xu","year":"2014","journal-title":"Auton. Robots"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.conengprac.2018.03.011","article-title":"2D visual area coverage and path planning coupled with camera footprints","volume":"75","author":"Mansouri","year":"2018","journal-title":"Control Eng. Pract."},{"key":"ref_12","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","volume":"61","author":"Galceran","year":"2013","journal-title":"Robot. Autom. Syst."},{"key":"ref_13","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 International Conference on Intelligent Robots and Systems, Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8206000"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1023\/A:1016665115585","article-title":"Efficient and inefficient ant coverage methods","volume":"31","author":"Koenig","year":"2001","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"6117","DOI":"10.1109\/TIE.2018.2874587","article-title":"Diversity-based cooperative multivehicle path planning for risk management in costmap environments","volume":"66","author":"Votion","year":"2019","journal-title":"IEEE Trans. Ind. Electron."},{"key":"ref_16","first-page":"185","article-title":"Pseudo spanning tree-based complete and competitive robot coverage using virtual nodes","volume":"491","author":"Ranjitha","year":"2016","journal-title":"IFAC-Pap. Online"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s10472-010-9193-y","article-title":"Multi-robot area patrol under frequency constraints","volume":"57","author":"Elmaliach","year":"2009","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_18","unstructured":"Franco, C., Vachtsevanos, G., and Tang, L. (2007, January 20\u201323). Multi-unmanned aerial vehicle coverage planner for area surveillance missions. Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit, Hilton Head, SC, USA."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.ejcon.2014.12.001","article-title":"Persistent coverage control for a team of agents with collision avoidance","volume":"22","author":"Franco","year":"2015","journal-title":"Eur. J. Control"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Erignac, C.A. (2007, January 7\u201310). An exhaustive swarming search strategy based on distributed pheromone maps. Proceedings of the AIAA Infotech@Aerospace 2007 Conference and Exhibit, Rohnert Park, CA, USA.","DOI":"10.2514\/6.2007-2822"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/j.apm.2017.03.021","article-title":"A cellular automata ant memory model of foraging in a swarm of robots","volume":"47","author":"Lima","year":"2017","journal-title":"Appl. Math. Model."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1016\/j.ejor.2017.03.048","article-title":"A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multi-objective optimization","volume":"261","author":"Liu","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Tumer, T., and Agogino, A. (2005, January 25\u201329). Coordinating multi-rover systems: Evaluation functions for dynamic and noisy environments. Proceedings of the 7th annual conference on Genetic and evolutionary computation, Washington, DC, USA.","DOI":"10.1145\/1068009.1068109"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Hokayem, P.F., Stipanovi\u00b4c, D., and Spong, M.W. (2007, January 12\u201314). On persistent coverage control. Proceedings of the 46th IEEE Conference on Decision and Control, New Orleans, LA, USA.","DOI":"10.1109\/CDC.2007.4434875"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/TSMC.2015.2500027","article-title":"Mutual information-based multi-AUV path planning for scalar field sampling using multidimensional RRT*","volume":"46","author":"Cui","year":"2016","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2936","DOI":"10.1016\/j.automatica.2014.10.023","article-title":"Supervised coverage control of multi-agent systems","volume":"50","author":"Voulgaris","year":"2014","journal-title":"Automatica"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1867","DOI":"10.1016\/j.automatica.2013.02.048","article-title":"Persistent awareness coverage control for mobile sensor networks","volume":"49","author":"Song","year":"2013","journal-title":"Automatica"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Smith, S.L., and Rus, D. (2010, January 15\u201317). Multi-robot monitoring in dynamic environments with guaranteed currency of observations. Proceedings of the 49th IEEE Conference on Decision and Control, Atlanta, GA, USA.","DOI":"10.1109\/CDC.2010.5717132"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Stump, E., and Michael, N. (2011, January 24\u201327). Multi-robot persistent surveillance planning as a vehicle routing problem. Proceedings of the 2011 IEEE International Conference on Automation Science and Engineering, Trieste, Italy.","DOI":"10.1109\/CASE.2011.6042503"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.conengprac.2018.03.002","article-title":"Cooperative coverage path planning for visual inspection","volume":"74","author":"Mansouri","year":"2017","journal-title":"Control Eng. Pract."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1314","DOI":"10.1016\/j.robot.2013.08.004","article-title":"Experimental investigation on coverage performance of a chaotic autonomous mobile robot","volume":"61","author":"Volos","year":"2013","journal-title":"Robot. Autom. Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1016\/j.ejor.2017.04.001","article-title":"A multi-objective facility location problem in the presence of variable gradual coverage performance and cooperative cover","volume":"262","author":"Karatas","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/j.asoc.2017.07.051","article-title":"Multi-objective coverage path planning: Enabling automated inspection of complex, real-world structures","volume":"61","author":"Ellefsen","year":"2017","journal-title":"Appl. Soft Comput."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"354","DOI":"10.3390\/s7030354","article-title":"An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment","volume":"7","author":"Wang","year":"2007","journal-title":"Sensors"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1109\/TEVC.2011.2112662","article-title":"Cooperatively coevolving particle swarms for large scale optimization","volume":"16","author":"Li","year":"2012","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.1109\/TPDS.2007.70808","article-title":"Distributed deployment schemes for mobile wireless sensor networks to ensure multilevel coverage","volume":"19","author":"Wang","year":"2008","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"2925","DOI":"10.1109\/TVT.2008.2010619","article-title":"Obstacle-resistant deployment algorithms for wireless sensor networks","volume":"58","author":"Chang","year":"2009","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"4796","DOI":"10.1109\/JSEN.2013.2274693","article-title":"A bipopulation-based evolutionary algorithm for solving full area coverage problems","volume":"13","author":"Seok","year":"2013","journal-title":"IEEE Sens. J."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Di, B., Zhou, R., Zhang, Y., and Che, J. (2014, January 8\u201310). Path planning for unmanned vehicle searching based on sensor deployment and travelling salesman problem. Proceedings of the 2014 IEEE Chinese Guidance, Navigation and Control Conference, Yantai, China.","DOI":"10.1109\/CGNCC.2014.7007451"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.comnet.2016.08.007","article-title":"Autonomous deployment of wireless sensor networks for optimal coverage with directional sensing model","volume":"108","author":"Li","year":"2016","journal-title":"Comput. Netw."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"18051","DOI":"10.1109\/ACCESS.2017.2740382","article-title":"The optimal deployment, coverage, and connectivity problems in wireless sensor networks: revisited","volume":"5","author":"AlKaraki","year":"2017","journal-title":"IEEE Access"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.inffus.2017.08.001","article-title":"Novel efficient deployment schemes for sensor coverage in mobile wireless sensor networks","volume":"41","author":"Fang","year":"2018","journal-title":"Inf. Fusion"},{"key":"ref_43","unstructured":"Maza, I., and Ollero, A. (2007, January 23\u201325). Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms. Proceedings of the 7 th International Symposium on Distributed Autonomous Robotic Systems, Toulouse, France."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/j.pmcj.2008.02.001","article-title":"Coverage and connectivity issues in wireless sensor networks: A survey","volume":"4","author":"Ghosh","year":"2008","journal-title":"Pervasive Mob. Comput."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1109\/TEVC.2010.2052054","article-title":"Orthogonal learning particle swarm optimization","volume":"15","author":"Zhan","year":"2011","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Palacios-Gas\u1f79s, J.M., Talebpour, Z., Montijano, E., Sag\u00fc\u00e9s, C., and Martinoli, A. (June, January 29). Optimal path planning and coverage control for multi-robot persistent coverage in environments with obstacles. Proceedings of the 2017 International Conference on Robotics and Automation, Singapore.","DOI":"10.1109\/ICRA.2017.7989156"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Hecht, M.S., and Kim, C.E. (1976, January 25\u201327). Approximation algorithms for some routing problems. Proceedings of the 17th Annual Symposium on Foundations of Computer Science, Houston, TX, USA.","DOI":"10.1109\/SFCS.1976.6"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Casta\u00f1o, F., Beruvides, C., Haber, R.E., and Artu\u00f1edo, A. (2017). Obstacle recognition based on machine learning for on-chip LiDAR sensors in a cyber-physical system. Sensors, 17.","DOI":"10.20944\/preprints201708.0014.v1"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Casta\u00f1o, F., Beruvides, C., Villalonga, A., and Haber, R.E. (2018). Self-tuning method for increased obstacle detection reliability based on internet of things LiDAR sensor models. Sensors, 18.","DOI":"10.20944\/preprints201802.0192.v1"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/9\/1994\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:47:48Z","timestamp":1760186868000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/9\/1994"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,28]]},"references-count":49,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["s19091994"],"URL":"https:\/\/doi.org\/10.3390\/s19091994","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2019,4,28]]}}}