{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T20:44:44Z","timestamp":1773089084802,"version":"3.50.1"},"reference-count":49,"publisher":"MDPI AG","issue":"21","license":[{"start":{"date-parts":[[2021,11,5]],"date-time":"2021-11-05T00:00:00Z","timestamp":1636070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["H2020-MG-2019-TwoStages-861696"],"award-info":[{"award-number":["H2020-MG-2019-TwoStages-861696"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Coverage path planning (CPP) is a field of study which objective is to find a path that covers every point of a certain area of interest. Recently, the use of Unmanned Aerial Vehicles (UAVs) has become more proficient in various applications such as surveillance, terrain coverage, mapping, natural disaster tracking, transport, and others. The aim of this paper is to design efficient coverage path planning collision-avoidance capable algorithms for single or multi UAV systems in cluttered urban environments. Two algorithms are developed and explored: one of them plans paths to cover a target zone delimited by a given perimeter with predefined coverage height and bandwidth, using a boustrophedon flight pattern, while the other proposed algorithm follows a set of predefined viewpoints, calculating a smooth path that ensures that the UAVs pass over the objectives. Both algorithms have been developed for a scalable number of UAVs, which fly in a triangular deformable leader-follower formation with the leader at its front. In the case of an even number of UAVs, there is no leader at the front of the formation and a virtual leader is used to plan the paths of the followers. The presented algorithms also have collision avoidance capabilities, powered by the Fast Marching Square algorithm. These algorithms are tested in various simulated urban and cluttered environments, and they prove capable of providing safe and smooth paths for the UAV formation in urban environments.<\/jats:p>","DOI":"10.3390\/s21217365","type":"journal-article","created":{"date-parts":[[2021,11,7]],"date-time":"2021-11-07T20:42:54Z","timestamp":1636317774000},"page":"7365","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":71,"title":["Multi UAV Coverage Path Planning in Urban Environments"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5068-3303","authenticated-orcid":false,"given":"Javier","family":"Mu\u00f1oz","sequence":"first","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6066-4923","authenticated-orcid":false,"given":"Blanca","family":"L\u00f3pez","sequence":"additional","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6556-3539","authenticated-orcid":false,"given":"Fernando","family":"Quevedo","sequence":"additional","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8295-127X","authenticated-orcid":false,"given":"Concepci\u00f3n A.","family":"Monje","sequence":"additional","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3838-8421","authenticated-orcid":false,"given":"Santiago","family":"Garrido","sequence":"additional","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4450-680X","authenticated-orcid":false,"given":"Luis E.","family":"Moreno","sequence":"additional","affiliation":[{"name":"Robotics Lab, Universidad Carlos III de Madrid, Av. Madrid 30, 28911 Legan\u00e9s, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1821","DOI":"10.3390\/su13041821","article-title":"A Review of Applications and Communication Technologies for Internet of Things (IoT) and Unmanned Aerial Vehicle (UAV) Based Sustainable Smart Farming","volume":"13","author":"Islam","year":"2021","journal-title":"Sustainability"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.comcom.2020.05.025","article-title":"PARTH: A two-stage lightweight mutual authentication protocol for UAV surveillance networks","volume":"160","author":"Alladi","year":"2020","journal-title":"Comput. Commun."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"4812","DOI":"10.1109\/LRA.2020.3003884","article-title":"Multi-UAV surveillance with minimum information idleness and latency constraints","volume":"5","author":"Scherer","year":"2020","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"105671","DOI":"10.1016\/j.ast.2019.105671","article-title":"Reinforcement learning based two-level control framework of UAV swarm for cooperative persistent surveillance in an unknown urban area","volume":"98","author":"Liu","year":"2020","journal-title":"Aerosp. Sci. Technol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"712","DOI":"10.3390\/s18030712","article-title":"Saliency detection and deep learning-based wildfire identification in UAV imagery","volume":"18","author":"Zhao","year":"2018","journal-title":"Sensors"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Wu, H., Li, H., Shamsoshoara, A., Razi, A., and Afghah, F. (2020, January 18\u201320). Transfer learning for wildfire identification in uav imagery. Proceedings of the 2020 54th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA.","DOI":"10.1109\/CISS48834.2020.1570617429"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1016\/j.cie.2018.05.013","article-title":"Persistent UAV delivery logistics: MILP formulation and efficient heuristic","volume":"120","author":"Song","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_8","first-page":"5155","article-title":"UAV-assisted content delivery in intelligent transportation systems-joint trajectory planning and cache management","volume":"22","author":"Samir","year":"2020","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Gupta, R., Shukla, A., Mehta, P., Bhattacharya, P., Tanwar, S., Tyagi, S., and Kumar, N. (2020, January 6\u20139). Vahak: A blockchain-based outdoor delivery scheme using uav for healthcare 4.0 services. Proceedings of the IEEE INFOCOM 2020-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Toronto, ON, Canada.","DOI":"10.1109\/INFOCOMWKSHPS50562.2020.9162738"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MPRV.2017.11","article-title":"Help from the sky: Leveraging UAVs for disaster management","volume":"16","author":"Erdelj","year":"2017","journal-title":"IEEE Pervasive Comput."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Chowdhury, T., Rahnemoonfar, M., Murphy, R., and Fernandes, O. (2020, January 10\u201313). Comprehensive semantic segmentation on high resolution uav imagery for natural disaster damage assessment. Proceedings of the 2020 IEEE International Conference on Big Data, Atlanta, GA, USA.","DOI":"10.1109\/BigData50022.2020.9377916"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cabreira, T.M., Brisolara, L.B., and Ferreira Paulo, R. (2019). Survey on coverage path planning with unmanned aerial vehicles. Drones, 3.","DOI":"10.3390\/drones3010004"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1016639210559","article-title":"Coverage for robotics\u2014A survey of recent results","volume":"31","author":"Choset","year":"2001","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_14","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_15","unstructured":"Jiao, Y.S., Wang, X.M., Chen, H., and Li, Y. (2010, January 15\u201317). Research on the coverage path planning of uavs for polygon areas. Proceedings of the 2010 5th IEEE Conference on Industrial Electronics and Applications, Taichung, Taiwan."},{"key":"ref_16","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_17","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_18","doi-asserted-by":"crossref","unstructured":"Coombes, M., Chen, W.H., and Liu, C. (2017, January 13\u201316). Boustrophedon coverage path planning for UAV aerial surveys in wind. Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA.","DOI":"10.1109\/ICUAS.2017.7991469"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Coombes, M., Fletcher, T., Chen, W.H., and Liu, C. (2018). Optimal polygon decomposition for UAV survey coverage path planning in wind. Sensors, 18.","DOI":"10.3390\/s18072132"},{"key":"ref_20","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_21","doi-asserted-by":"crossref","first-page":"3662","DOI":"10.1109\/LRA.2018.2854967","article-title":"Energy-aware spiral coverage path planning for uav photogrammetric applications","volume":"3","author":"Cabreira","year":"2018","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_22","unstructured":"\u00d6st, G. (2021, September 09). Search Path Generation with UAV Applications Using Approximate Convex Decomposition, Department of Electrical, Link\u00f6pings Universitet. Available online: http:\/\/www.diva-portal.org\/smash\/get\/diva2:526417\/FULLTEXT01.pdf."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Maza, I., and Ollero, A. (2007). Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms. Distributed Autonomous Robotic Systems 6, Springer.","DOI":"10.1007\/978-4-431-35873-2_22"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Balampanis, F., Maza, I., and Ollero, A. (2017). Coastal areas division and coverage with multiple UAVs for remote sensing. Sensors, 17.","DOI":"10.3390\/s17040808"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Balampanis, F., Maza, I., and Ollero, A. (2017, January 13\u201316). Spiral-like coverage path planning for multiple heterogeneous UAS operating in coastal regions. Proceedings of the 2017 International Conference on Unmanned Aircraft Systems, (ICUAS), Miami, FL, USA.","DOI":"10.1109\/ICUAS.2017.7991461"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s11119-012-9287-0","article-title":"Near-optimal coverage trajectories for image mosaicing using a mini quad-rotor over irregular-shaped fields","volume":"14","author":"Valente","year":"2013","journal-title":"Precis. Agric."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bouzid, Y., Bestaoui, Y., and Siguerdidjane, H. (2017, January 24\u201328). Quadrotor-UAV optimal coverage path planning in cluttered environment with a limited onboard energy. Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Vancouver, BC, Canada.","DOI":"10.1109\/IROS.2017.8202264"},{"key":"ref_28","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_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s42452-019-0872-y","article-title":"A survey on multi-robot coverage path planning for model reconstruction and mapping","volume":"1","author":"Almadhoun","year":"2019","journal-title":"SN Appl. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Sadat, S.A., Wawerla, J., and Vaughan, R.T. (2014, January 14\u201318). Recursive non-uniform coverage of unknown terrains for UAVs. Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Chicago, IL, USA.","DOI":"10.1109\/IROS.2014.6942790"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Sadat, S.A., Wawerla, J., and Vaughan, R. (2015, January 25\u201330). Fractal trajectories for online non-uniform aerial coverage. Proceedings of the IEEE International Conference on Robotics and Automation, Seattle, WA, USA.","DOI":"10.1109\/ICRA.2015.7139606"},{"key":"ref_32","unstructured":"Santamaria, E., Segor, F., and Tchouchenkov, I. (2013, January 12\u201315). Rapid aerial mapping with multiple heterogeneous unmanned vehicles. Proceedings of the ISCRAM 2013 Conference\u201310th International Conference on Information Systems for Crisis Response and Management, Baden-Baden, Germany."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Sauter, J.A., Matthews, R., Van Dyke Parunak, H., and Brueckner, S.A. (2005, January 25\u201329). Performance of digital pheromones for swarming vehicle control. Proceedings of the International Conference on Autonomous Agents, Utrecht, The Netherlands.","DOI":"10.1145\/1082473.1082610"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Paradzik, M., and Ince, G. (2016, January 16\u201319). Multi-agent search strategy based on digital pheromones for uavs. Proceedings of the 2016 24th Signal Processing and Communication Application Conference (SIU), Zonguldak, Turkey.","DOI":"10.1109\/SIU.2016.7495720"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1007\/s10514-015-9517-1","article-title":"Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots","volume":"40","author":"Bircher","year":"2016","journal-title":"Auton. Robot."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Ghaddar, A., and Merei, A. (2020). EAOA: Energy-Aware Grid-Based 3D-Obstacle Avoidance in Coverage Path Planning for UAVs. Future Internet, 12.","DOI":"10.3390\/fi12020029"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Cabreira, T.M., Ferreira, P.R., Di Franco, C., and Buttazzo, G.C. (2019, January 11\u201314). Grid-based coverage path planning with minimum energy over irregular-shaped areas with UAVs. Proceedings of the 2019 International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, GA, USA.","DOI":"10.1109\/ICUAS.2019.8797937"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Mu\u00f1oz, J., L\u00f3pez, B., Quevedo, F., Monje, C.A., Garrido, S., and Moreno, L.E. (2021). Coverage Strategy for Target Location in Marine Environments Using Fixed-Wing UAVs. Drones, 5.","DOI":"10.3390\/drones5040120"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Chen, J., Du, C., Zhang, Y., Han, P., and Wei, W. (2021). A clustering-based coverage path planning method for autonomous heterogeneous UAVs. IEEE Trans. Intell. Transp. Syst.","DOI":"10.1109\/TITS.2021.3066240"},{"key":"ref_40","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_41","doi-asserted-by":"crossref","unstructured":"Melo, A.G., Pinto, M.F., Marcato, A.L., Hon\u00f3rio, L.M., and Coelho, F.O. (2021). Dynamic Optimization and Heuristics Based Online Coverage Path Planning in 3D Environment for UAVs. Sensors, 21.","DOI":"10.3390\/s21041108"},{"key":"ref_42","unstructured":"Von Stackelberg, H. (1934). Marktform und Gleichgewicht, Springer."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"L\u00f3pez, B., Mu\u00f1oz, J., Quevedo, F., Monje, C.A., Garrido, S., and Moreno, L.E. (2021). Path Planning and Collision Risk Management Strategy for Multi-UAV Systems in 3D Environments. Sensors, 21.","DOI":"10.3390\/s21134414"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.robot.2012.10.009","article-title":"Planning robot formations with fast marching square including uncertainty conditions","volume":"61","author":"Lumbier","year":"2013","journal-title":"Robot. Auton. Syst."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1137\/S0036144598347059","article-title":"Fast marching methods","volume":"41","author":"Sethian","year":"1999","journal-title":"SIAM Rev."},{"key":"ref_46","unstructured":"(2021, September 09). IGN\u2013Instituto Geogr\u00e1fico Nacional. Available online: https:\/\/www.ign.es\/web\/ign\/portal\/qsm-cnig."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Garrido, S., Moreno, L., Blanco, D., and Martin, F. (2007, January 4\u20137). FM2: A real-time fast marching sensor-based motion planner. Proceedings of the 2007 IEEE\/ASME International Conference on Advanced Intelligent Mechatronics, Zurich, Switzerland.","DOI":"10.1109\/AIM.2007.4412505"},{"key":"ref_48","unstructured":"Coulter, R.C. (1992). Implementation of the Pure Pursuit Path Tracking Algorithm, Carnegie-Mellon UNIV Pittsburgh PA Robotics INST. Technical Report."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.jcp.2005.08.005","article-title":"O (N) implementation of the fast marching algorithm","volume":"212","author":"Yatziv","year":"2006","journal-title":"J. Comput. Phys."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/21\/7365\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:26:25Z","timestamp":1760167585000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/21\/7365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,5]]},"references-count":49,"journal-issue":{"issue":"21","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["s21217365"],"URL":"https:\/\/doi.org\/10.3390\/s21217365","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,5]]}}}