{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T18:51:33Z","timestamp":1775155893209,"version":"3.50.1"},"reference-count":33,"publisher":"MDPI AG","issue":"20","license":[{"start":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T00:00:00Z","timestamp":1697500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Korea government (MSIT)","award":["2021-0-02087"],"award-info":[{"award-number":["2021-0-02087"]}]},{"name":"Korea government (MSIT)","award":["20014854"],"award-info":[{"award-number":["20014854"]}]},{"name":"Korea government (MSIT)","award":["20210630"],"award-info":[{"award-number":["20210630"]}]},{"name":"Ministry of the Interior and Safety, Republic of Korea","award":["2021-0-02087"],"award-info":[{"award-number":["2021-0-02087"]}]},{"name":"Ministry of the Interior and Safety, Republic of Korea","award":["20014854"],"award-info":[{"award-number":["20014854"]}]},{"name":"Ministry of the Interior and Safety, Republic of Korea","award":["20210630"],"award-info":[{"award-number":["20210630"]}]},{"name":"Ministry of Trade, Industry and Energy","award":["2021-0-02087"],"award-info":[{"award-number":["2021-0-02087"]}]},{"name":"Ministry of Trade, Industry and Energy","award":["20014854"],"award-info":[{"award-number":["20014854"]}]},{"name":"Ministry of Trade, Industry and Energy","award":["20210630"],"award-info":[{"award-number":["20210630"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this study, we present a systematic exploration of hierarchical designs for multirobot coverage path planning (MCPP) with a special focus on surveillance applications. Unlike conventional studies centered on cleaning tasks, our investigation delves into the realm of surveillance problems, specifically incorporating the sensing range (SR) factor equipped on the robots. Conventional path-based MCPP strategies considering SR, primarily rely on naive approaches, generating nodes (viewpoints) to be visited and a global path based on these nodes. Therefore, our study proposes a general MCPP framework for surveillance by dealing with path-based and area-based structures comprehensively. As the traveling salesman problem (TSP) solvers, our approach incorporates not the naive approach but renowned and powerful algorithms such as genetic algorithms (GAs), and ant colony optimization (ACO) to enhance the planning process. We devise six distinct methods within the proposed MCPP framework. Two methods adopt area-based approaches which segments areas via a hierarchical max-flow routing algorithm based on SR and the number of robots. TSP challenges within each area are tackled using a GA or ACO, and the result paths are allocated to individual robots. The remaining four methods are categorized by the path-based approaches with global\u2013local structures such as GA-GA, GA-ACO, ACO-GA, and ACO-ACO. Unlike conventional methods which requires a global path, we further incorporate ACO- or GA-based local planning. This supplementary step at the local level enhances the quality of the path-planning results, particularly when dealing with a large number of nodes, by preventing any degradation in global path-planning outcomes. An extensive comparative analysis is conducted to evaluate the proposed framework based on execution time, total path length, and idle time. The area-based approaches tend to show a better execution time and overall path length performance compared to the path-based approaches. However, the path-based MCPP methods have the advantage of having a smaller idle time than the area-based MCPP methods. Our study finds that the proposed area-based MCPP method excels in path planning, while the proposed path-based MCPP method demonstrates superior coverage balance performance. By selecting an appropriate MCPP structure based on the specific application requirements, leveraging the strengths of both methodologies, efficient MCPP execution becomes attainable. Looking forward, our future work will focus on tailoring these MCPP structures to diverse real-world conditions, aiming to propose the most suitable approach for specific applications.<\/jats:p>","DOI":"10.3390\/s23208533","type":"journal-article","created":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T10:36:56Z","timestamp":1697625416000},"page":"8533","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Hierarchical Area-Based and Path-Based Heuristic Approaches for Multirobot Coverage Path Planning with Performance Analysis in Surveillance Systems"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-1669-1615","authenticated-orcid":false,"given":"Junghwan","family":"Gong","sequence":"first","affiliation":[{"name":"School of Electronic Engineering, Kumoh National Institute of Technology, Gumi 39177, Republic of Korea"}]},{"given":"Seunghwan","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Electronic Engineering, Kumoh National Institute of Technology, Gumi 39177, Republic of Korea"}]}],"member":"1968","published-online":{"date-parts":[[2023,10,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Alam, T., and Bobadilla, L. (2020). Multi-robot coverage and persistent monitoring in sensing-constrained environments. Robotics, 9.","DOI":"10.3390\/robotics9020047"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1007\/s10846-020-01156-6","article-title":"Multi-robot patrolling with sensing idleness and data delay objectives","volume":"99","author":"Scherer","year":"2020","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Noh, D., Choi, J., Choi, J., Byun, D., Youngjae, K., Kim, H.R., Baek, S., Lee, S., and Myung, H. (2022, January 4\u20136). MASS: Multi-agent scheduling system for intelligent surveillance. Proceedings of the 19th International Conference Ubiquitous Robots (UR), Jeju, Republic of Korea.","DOI":"10.1109\/UR55393.2022.9826281"},{"key":"ref_4","first-page":"318","article-title":"A new entrapment based invader capture strategy for multirobot surveillance systems","volume":"543","author":"Lee","year":"2022","journal-title":"Proc. SAI Intell. Syst. Conf."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lee, S. (2021, January 12\u201315). A multi-robot balanced coverage path planning strategy for patrol missions. Proceedings of the 21st International Conference on Control, Automation and Systems (ICCAS), Jeju, Republic of Korea.","DOI":"10.23919\/ICCAS52745.2021.9649836"},{"key":"ref_6","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. Robots"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wang, H., Lou, S., Jing, J., Wang, Y., Liu, W., and Liu, T. (2022). The EBS-A* algorithm: An improved A* algorithm for path planning. PLoS ONE, 17.","DOI":"10.1371\/journal.pone.0263841"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"198101","DOI":"10.1109\/ACCESS.2020.3027422","article-title":"A multi-robot coverage path planning algorithm for the environment with multiple land cover types","volume":"8","author":"Huang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Gao, C., Kou, Y., Li, Z., Xu, A., Li, Y., and Chang, Y. (2018). Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree. Math. Probl. Eng., 3436429.","DOI":"10.1155\/2018\/3436429"},{"key":"ref_10","first-page":"227","article-title":"Comparisons of Robot-Moving Strategies with Evolutionary Algorithm and Neuro-Fuzzy Method","volume":"10","author":"Yi","year":"2012","journal-title":"J. KIIT"},{"key":"ref_11","first-page":"158","article-title":"Analysis of the impact of parameters values on the Genetic Algorithm for TSP","volume":"10","author":"Bexhepi","year":"2013","journal-title":"Int. J. Comput. Sci."},{"key":"ref_12","first-page":"462","article-title":"A Comparative Assessment of ACO Algorithms Within a TSP Environment","volume":"1","author":"Asmar","year":"2005","journal-title":"Dyn. Contin. Discret. Impuls. Syst. Ser. B Appl. Algorithms"},{"key":"ref_13","first-page":"28","article-title":"A Performance Comparison of GA and ACO Applied to TSP","volume":"117","author":"Haroun","year":"2015","journal-title":"Int. J. Comput. Appl."},{"key":"ref_14","first-page":"1169","article-title":"A Hybrid Genetic Ant Colony Optimization Algorithm with an Embedded Cloud Model for Continuous Optimization","volume":"16","author":"Wang","year":"2019","journal-title":"J. Inf. Process. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"624333","DOI":"10.3389\/frobt.2021.624333","article-title":"Efficient coverage path planning for mobile disinfecting robots using graph-based representation of environment","volume":"8","author":"Nasirian","year":"2021","journal-title":"Front. Robot. AI"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s11370-018-00273-4","article-title":"Optimum harvesting area of convex and concave polygon field for path planning of robot combine harvester","volume":"12","author":"Rahman","year":"2019","journal-title":"Intell. Serv. Robot."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"97873","DOI":"10.1109\/ACCESS.2020.2997095","article-title":"Multi-cleaning robots using cleaning distribution method based on map decomposition in large environments","volume":"8","author":"Miao","year":"2020","journal-title":"IEEE Access"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Elangovan, D., Govindarajan, P.L., Elnaggar, M.F., Alrashed, M.M., and Kamel, S. (2022). A comprehensive review of path planning for agricultural ground robots. Sustainability, 14.","DOI":"10.3390\/su14159156"},{"key":"ref_19","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. Auton. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1017\/S026357472000096X","article-title":"CPC algorithm: Exact area coverage by a mobile robot using approximate cellular decomposition","volume":"39","author":"Guruprasad","year":"2020","journal-title":"Robotica"},{"key":"ref_21","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_22","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","article-title":"Least squares quantization in PCM","volume":"28","author":"Lloyd","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","article-title":"Voronoi diagrams\u2014A survey of a fundamental geometric data structure","volume":"23","author":"Aurenhammer","year":"1991","journal-title":"ACM Comput. Surv."},{"key":"ref_24","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_25","unstructured":"Bast, H., and Hert, S. (2000, January 16\u201319). The area partitioning problem. Proceedings of the 12th Canadian Conference on Computational Geometry Fredericton, New Brunswick, Canada."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"97","DOI":"10.2307\/1912531","article-title":"Perfect equilibrium in a bargaining model","volume":"50","author":"Rubinstein","year":"1982","journal-title":"Econometrica"},{"key":"ref_27","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_28","doi-asserted-by":"crossref","unstructured":"Fazli, P., Davoodi, A., and Mackworth, A.K. (2012, January 28\u201330). Multi-robot repeated area coverage: Performance optimization under various visual ranges. Proceedings of the 9th Conference on Computer and Robot Vision, Toronto, ON, Canada.","DOI":"10.1109\/CRV.2012.46"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s10514-012-9319-7","article-title":"Multi-robot repeated area coverage","volume":"34","author":"Fazli","year":"2013","journal-title":"Auto. Robot."},{"key":"ref_30","unstructured":"O\u2019Rourke, J. (1987). Art Gallery Theorems and Algorithms, Oxford University Press."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1080\/25765299.2019.1565193","article-title":"A novel hybrid approach for solving the multiple traveling salesmen problem","volume":"26","author":"Harrath","year":"2019","journal-title":"Arab. J. Basic Appl. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.1016\/j.ejor.2005.03.008","article-title":"Integer linear programming formulations of multiple salesman problems and its variations","volume":"174","author":"Kara","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","first-page":"545","article-title":"Hierarchical max-flow routing","volume":"1","author":"Lim","year":"2005","journal-title":"IEEE Glob. Telecommun. Conf."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/20\/8533\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:08:40Z","timestamp":1760130520000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/23\/20\/8533"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,17]]},"references-count":33,"journal-issue":{"issue":"20","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["s23208533"],"URL":"https:\/\/doi.org\/10.3390\/s23208533","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,17]]}}}