{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T02:21:30Z","timestamp":1768702890458,"version":"3.49.0"},"reference-count":53,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T00:00:00Z","timestamp":1612483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Path planning is one of the most important issues in the robotics field, being applied in many domains ranging from aerospace technology and military tasks to manufacturing and agriculture. Path planning is a branch of autonomous navigation. In autonomous navigation, dynamic decisions about the path have to be taken while the robot moves towards its goal. Among the navigation area, an important class of problems is Coverage Path Planning (CPP). The CPP technique is associated with determining a collision-free path that passes through all viewpoints in a specific area. This paper presents a method to perform CPP in 3D environment for Unmanned Aerial Vehicles (UAVs) applications, namely 3D dynamic for CPP applications (3DD-CPP). The proposed method can be deployed in an unknown environment through a combination of linear optimization and heuristics. A model to estimate cost matrices accounting for UAV power usage is proposed and evaluated for a few different flight speeds. As linear optimization methods can be computationally demanding to be used on-board a UAV, this work also proposes a distributed execution of the algorithm through fog-edge computing. Results showed that 3DD-CPP had a good performance in both local execution and fog-edge for different simulated scenarios. The proposed heuristic is capable of re-optimization, enabling execution in environments with local knowledge of the environments.<\/jats:p>","DOI":"10.3390\/s21041108","type":"journal-article","created":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T08:33:48Z","timestamp":1612514028000},"page":"1108","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":45,"title":["Dynamic Optimization and Heuristics Based Online Coverage Path Planning in 3D Environment for UAVs"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8227-6462","authenticated-orcid":false,"given":"Aurelio G.","family":"Melo","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Federal University of Juiz de Fora, Juiz de Fora 36036-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6916-700X","authenticated-orcid":false,"given":"Milena F.","family":"Pinto","sequence":"additional","affiliation":[{"name":"Department of Electronics Engineering, Federal Center for Technological Education of Rio de Janeiro, Rio de Janeiro 20271-110, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9171-3089","authenticated-orcid":false,"given":"Andre L. M.","family":"Marcato","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Federal University of Juiz de Fora, Juiz de Fora 36036-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2735-4792","authenticated-orcid":false,"given":"Leonardo M.","family":"Hon\u00f3rio","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Federal University of Juiz de Fora, Juiz de Fora 36036-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6974-5738","authenticated-orcid":false,"given":"Fabr\u00edcio O.","family":"Coelho","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Federal University of Juiz de Fora, Juiz de Fora 36036-900, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,5]]},"reference":[{"key":"ref_1","first-page":"173","article-title":"Route planning algorithm and verification based on UAV operation path angle in irregular area","volume":"31","author":"Xu","year":"2015","journal-title":"Trans. Chin. Soc. Agric. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.autcon.2017.12.001","article-title":"Tunnel structural inspection and assessment using an autonomous robotic system","volume":"87","author":"Menendez","year":"2018","journal-title":"Autom. Constr."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Song, Y.S., and Arshad, M.R. (2016, January 22). Coverage path planning for underwater pole inspection using an autonomous underwater vehicle. Proceedings of the 2016 IEEE International Conference on Automatic Control and Intelligent Systems (I2CACIS), Selangor, Malaysia.","DOI":"10.1109\/I2CACIS.2016.7885320"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"177823","DOI":"10.1109\/ACCESS.2020.3027205","article-title":"3D Correspondence and Point Projection Method for Structures Deformation Analysis","volume":"8","author":"Melo","year":"2020","journal-title":"IEEE Access"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s40313-019-00453-2","article-title":"Mobile robot localization based on the novel leader-based bat algorithm","volume":"30","author":"Neto","year":"2019","journal-title":"J. Control. Autom. Electr. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Coelho, F.O., Carvalho, J.P., Pinto, M.F., and Marcato, A.L. (2018, January 4\u20136). Ekf and computer vision for mobile robot localization. Proceedings of the 2018 13th APCA International Conference on Automatic Control and Soft Computing (CONTROLO), Ponta Delgada, Portugal.","DOI":"10.1109\/CONTROLO.2018.8514177"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"38200","DOI":"10.1109\/ACCESS.2018.2853146","article-title":"Scalable Coverage Path Planning for Cleaning Robots Using Rectangular Map Decomposition on Large Environments","volume":"6","author":"Miao","year":"2018","journal-title":"IEEE Access"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Silva, M., Ribeiro, A., Santos, M., Carmo, M., Hon\u00f3rio, L., Oliveira, E., and Vidal, V. (2016, January 13\u201315). Design of angular PID controllers for quadcopters built with low cost equipment. Proceedings of the 2016 20th International Conference on System Theory, Control and Computing (ICSTCC), Sinaia, Romania.","DOI":"10.1109\/ICSTCC.2016.7790668"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Santos, M.F., Hon\u00f3rio, L.M., Costa, E.B., Oliveira, E.J., and Visconti, J.P.P.G. (2015, January 14\u201316). Active fault-tolerant control applied to a hexacopter under propulsion system failures. Proceedings of the 2015 19th International Conference on System Theory, Control and Computing (ICSTCC), Cheile Gradistei.","DOI":"10.1109\/ICSTCC.2015.7321334"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"7497924","DOI":"10.1155\/2019\/7497924","article-title":"A framework for analyzing fog-cloud computing cooperation applied to information processing of UAVs","volume":"2019","author":"Pinto","year":"2019","journal-title":"Wirel. Commun. Mob. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1002\/rob.20388","article-title":"Coverage path planning on three-dimensional terrain for arable farming","volume":"28","author":"Jin","year":"2011","journal-title":"J. Field Robot."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.3389\/fbuil.2018.00031","article-title":"Utilizing UAV and 3D computer vision for visual inspection of a large gravity dam","volume":"4","author":"Khaloo","year":"2018","journal-title":"Front. Built Environ."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kim, D.H., Hoang, G., Bae, M., Kim, J.W., Yoon, S.M., Yeo, T., Sup, H., and Kim, S. (2014, January 22\u201325). Path tracking control coverage of a mining robot based on exhaustive path planning with exact cell decomposition. Proceedings of the 2014 14th International Conference on Control, Automation and Systems (ICCAS 2014), Seoul, Korea.","DOI":"10.1109\/ICCAS.2014.6987875"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2124","DOI":"10.1109\/TVT.2018.2890773","article-title":"Autonomous navigation of UAVs in large-scale complex environments: A deep reinforcement learning approach","volume":"68","author":"Wang","year":"2019","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Silva, M.F., Lu\u00eds Lima, J., Reis, L.P., Sanfeliu, A., and Tardioli, D. (2020). Coverage Path Planning Optimization for Slopes and Dams Inspection. Robot 2019: Fourth Iberian Robotics Conference, Springer International Publishing.","DOI":"10.1007\/978-3-030-35990-4_55"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"101843","DOI":"10.1016\/j.rcim.2019.101843","article-title":"Coverage path planning with targetted viewpoint sampling for robotic free-form surface inspection","volume":"61","author":"Glorieux","year":"2020","journal-title":"Robot. Comput. Integr. Manuf."},{"key":"ref_18","unstructured":"Kim, S., and Likhachev, M. (October, January 28). Path planning for a tethered robot using Multi-Heuristic A* with topology-based heuristics. Proceedings of the 2015 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1017\/S0263574719001206","article-title":"Hybrid Methodology for Path Planning and Computational Vision Applied to Autonomous Mission: A New Approach","volume":"38","author":"Coelho","year":"2020","journal-title":"Robotica"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"13979","DOI":"10.1007\/s00500-020-04771-5","article-title":"Autonomous mobile robot path planning in unknown dynamic environments using neural dynamics","volume":"24","author":"Chen","year":"2020","journal-title":"Soft Comput."},{"key":"ref_21","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_22","doi-asserted-by":"crossref","unstructured":"Majeed, A., and Lee, S. (2019). A new coverage flight path planning algorithm based on footprint sweep fitting for unmanned aerial vehicle navigation in urban environments. Appl. Sci., 9.","DOI":"10.3390\/app9071470"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sch\u00f8ler, F., la Cour-Harbo, A., and Bisgaard, M. (2011, January 8\u201311). Generating configuration spaces and visibility graphs from a geometric workspace for uav path planning. Proceedings of the AIAA Guidance, Navigation, and Control Conference, Portland, OR, USA.","DOI":"10.2514\/6.2011-6416"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Yang, K., and Sukkarieh, S. (2008, January 27\u201329). Real-time continuous curvature path planning of UAVs in cluttered environments. Proceedings of the 2008 5th International Symposium on Mechatronics and Its Applications, Amman, Jordan.","DOI":"10.1109\/ISMA.2008.4648836"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Coelho, F.O., Carvalho, J.P., Pinto, M.F., and Marcato, A.L. (2018, January 4\u20136). Direct-DRRT*: A RRT improvement proposal. Proceedings of the 2018 13th APCA International Conference on Automatic Control and Soft Computing (CONTROLO), Ponta Delgada, Portugal.","DOI":"10.1109\/CONTROLO.2018.8514261"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s11633-013-0750-9","article-title":"Path planning in complex 3D environments using a probabilistic roadmap method","volume":"10","author":"Yan","year":"2013","journal-title":"Int. J. Autom. Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s10846-011-9568-2","article-title":"Path planning strategies for UAVS in 3D environments","volume":"65","author":"Guglieri","year":"2012","journal-title":"J. Intell. Robot. Syst."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Carsten, J., Ferguson, D., and Stentz, A. (2006, January 9\u201315). 3d field d: Improved path planning and replanning in three dimensions. Proceedings of the 2006 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Beijing, China.","DOI":"10.1109\/IROS.2006.282516"},{"key":"ref_29","first-page":"913","article-title":"Implementing 3D network analysis in 3D-GIS","volume":"37","author":"Musliman","year":"2008","journal-title":"Int. Arch. ISPRS"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Vidal, V.F., Hon\u00f3rio, L.M., Santos, M.F., Silva, M.F., Cerqueira, A.S., and Oliveira, E.J. (2017, January 28\u201331). UAV vision aided positioning system for location and landing. Proceedings of the 18th international carpathian control conference (ICCC), Sinaia, Romania.","DOI":"10.1109\/CarpathianCC.2017.7970402"},{"key":"ref_31","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_32","unstructured":"Franco, C.D., and Buttazzo, G. (2015, January 8\u201310). Energy-aware coverage path planning of UAVs. Proceedings of the 2015 IEEE International Conference on Autonomous Robot Systems and Competitions, Vila Real, Portugal."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bircher, A., Alexis, K., Burri, M., Oettershagen, P., Omari, S., and Siegwart, R. (2015, January 26\u201330). Structural inspection path planning via iterative viewpoint resampling with application to aerial robotics. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.","DOI":"10.1109\/ICRA.2015.7140101"},{"key":"ref_34","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_35","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1109\/TETC.2017.2687319","article-title":"A disaster management-oriented path planning for mobile anchor node-based localization in wireless sensor networks","volume":"8","author":"Han","year":"2017","journal-title":"IEEE Trans. Emerg. Top. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1177\/0278364917714338","article-title":"Deterministic sampling-based motion planning: Optimality, complexity, and performance","volume":"37","author":"Janson","year":"2018","journal-title":"Int. J. Robot. Res."},{"key":"ref_37","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_38","doi-asserted-by":"crossref","unstructured":"Biundini, I.Z., Pinto, M.F., Melo, A.G., Marcato, A.L.M., Hon\u00f3rio, L.M., and Aguiar, M.J.R. (2021). A Framework for Coverage Path Planning Optimization Based on Point Cloud for Structural Inspection. Sensors, 21.","DOI":"10.3390\/s21020570"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"152953","DOI":"10.1109\/ACCESS.2019.2948160","article-title":"ML4IoT: A Framework to Orchestrate Machine Learning Workflows on Internet of Things Data","volume":"7","author":"Alves","year":"2019","journal-title":"IEEE Access"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Pinto, M.F., Hon\u00f3rio, L.M., Marcato, A.L., Dantas, M.A., Melo, A.G., Capretz, M., and Urdiales, C. (2020). ARCog: An Aerial Robotics Cognitive Architecture. Robotica, 1\u201320.","DOI":"10.1017\/S0263574720000521"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Ad\u00e3o, T., Hru\u0161ka, J., P\u00e1dua, L., Bessa, J., Peres, E., Morais, R., and Sousa, J.J. (2017). Hyperspectral imaging: A review on UAV-based sensors, data processing and applications for agriculture and forestry. Remote. Sens., 9.","DOI":"10.3390\/rs9111110"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"107148","DOI":"10.1016\/j.comnet.2020.107148","article-title":"A compilation of UAV applications for precision agriculture","volume":"172","author":"Sarigiannidis","year":"2020","journal-title":"Comput. Netw."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Kurihara, J., Ishida, T., and Takahashi, Y. (2020). Unmanned Aerial Vehicle (UAV)-based hyperspectral imaging system for precision agriculture and forest management. Unmanned Aerial Vehicle: Applications in Agriculture and Environment, Springer.","DOI":"10.1007\/978-3-030-27157-2_3"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"126137","DOI":"10.1109\/ACCESS.2019.2938273","article-title":"Adaptive neural network control and optimal path planning of UAV surveillance system with energy consumption prediction","volume":"7","author":"Wai","year":"2019","journal-title":"IEEE Access"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1442","DOI":"10.1109\/TAES.2017.2671522","article-title":"Optimal path planning of solar-powered UAV using gravitational potential energy","volume":"53","author":"Lee","year":"2017","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Jeon, H., Song, J., Lee, H., and Eun, Y. (2020). Modeling quadrotor dynamics in a wind field. IEEE\/ASME Trans. Mechatron.","DOI":"10.1109\/TMECH.2020.3019831"},{"key":"ref_47","unstructured":"(2020, August 31). T-Motor. Available online: http:\/\/store-en.tmotor.com\/goods.php?id=340."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Dai, W. (2017). Reoptimization of minimum latency problem. International Computing and Combinatorics Conference, Springer.","DOI":"10.1007\/978-3-319-62389-4_14"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Escoffier, B., Monnot, J., and Paschos, V.T. (2006). Reoptimization of minimum and maximum traveling salesman\u2019s tours. Scandinavian Workshop on Algorithm Theory, Springer.","DOI":"10.1007\/11785293_20"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Poslednik, M., Pozniak-Koszalka, I., Koszalka, L., and Kasprzak, A. (2019). Comparison of Heuristic Algorithms for Path Planning in 3D Printing with Multistage Experimentation System. International Conference on Computational Collective Intelligence, Springer.","DOI":"10.1007\/978-3-030-28377-3_41"},{"key":"ref_51","unstructured":"Lu, Y., Hao, J.K., and Wu, Q. (2020). Solving the Clustered Traveling Salesman Problem via TSP methods. arXiv."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Hartman, C.R., and Sharma, R. (2019, January 7\u201311). Development of a Velocity Controller for Following a Human Using Target Velocity in a GPS-Denied Environment. Proceedings of the AIAA Scitech 2019 Forum, San Diego, CA, USA.","DOI":"10.2514\/6.2019-1452"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Hu, J., Ma, Z., Niu, Y., Tian, W., and Yao, W. (2019). Real-Time Trajectory Replanning for Quadrotor Using OctoMap and Uniform B-Splines. International Conference on Intelligent Robotics and Applications, Springer.","DOI":"10.1007\/978-3-030-27532-7_63"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1108\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:19:58Z","timestamp":1760159998000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,5]]},"references-count":53,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["s21041108"],"URL":"https:\/\/doi.org\/10.3390\/s21041108","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,5]]}}}