İnsansız hava araçları ile ayrık alanlı alan tarama probleminin matematiksel model ile çözümü

Yıl 2025, Cilt: 40 Sayı: 3, 1431 - 1444

Melike Kübra Ekiz Bozdemir , Nilgün Fığlalı

https://doi.org/10.17341/gazimmfd.1456025

Öz

Günümüzde İnsansız Hava Araçları (İHA'lar), küçük boyutları, düşük maliyetleri ve güçlü uyarlana bilirlikleri nedeniyle arama kurtarma çalışmalarında, tarım, güvenlik ve gözetleme uygulamalarında giderek daha çok kullanılmaktadır. İHA uygulamaları için önemli bir problem olan Alan Tarama Problemi (ATP, Coverage Path Planning-CPP), en temel hali ile belirli bir alanı tarayan bir yol planlaması yapmak olarak tanımlanabilir. Literatürde tek bir alanın taranmasına yönelik çalışmalar oldukça fazla iken birbirinden ayrık alanları dikkate alan çalışma sayısı oldukça azdır. Bu çalışmada batarya kapasitesi dikkate alınan homojen İHA filosu ile ayrık dörtgen alanların taranması problemi ele alınmış ve çözümü için etkin bir matematiksel model önerilmiştir. Ele alınan probleme ait test problemleri farklı iz aralıkları ve batarya kapasiteleri kullanılarak oluşturulmuş, önerilen model ile çözülmüş ve sonuçlar yorumlanmıştır.

Anahtar Kelimeler

İnsansız hava araçları (İHA), alan tarama problemi(ATP), çoklu ayrık alan, homojen İHA filosu

Kaynakça

• 1. Deniz G., Çelik H., Vision based automatic control and target tracking of a quadcopter, Journal of the Faculty of Engineering and Architecture of Gazi University, 39 (3), 1865-1878, 2024.
• 2. Gümüşboğa İ., Design of an automated stock-taking system based on unmanned aerial vehicles, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (4), 1767-1781, 2022.
• 3. Chung S. H., Sah B., Lee J., Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions, Computers & Operations Research, 123 (1), 105004, 2020.
• 4. Otto A., Agatz N., Campbell J., Golden B., Pesch E., Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey, Networks, 72 (4), 411-458, 2018.
• 5. Bişkin B., Tezcaner Öztürk D., Tuncer Şakar C., Biobjective route planning for a fleet of UAVs: Exact and heuristic approaches, Journal of the Faculty of Engineering and Architecture of Gazi University, 38 (4), 2167-2178, 2023.
• 6. Zhen L., Yang Z., Laporte G., Yi W., Fan T., Unmanned Aerial Vehicle Inspection Routing and Scheduling for Engineering Management, Engineering, 36, 223–239, 2024.
• 7. Valente J., Cerro J. D., Barrientos A., Sanz D., Aerial coverage optimization in precision agriculture management: A musical harmony inspired approach, Computers and Electronics in Agriculture, 99 (1), 153-159, 2013.
• 8. Kyriakakis N. A., Marinaki M., Matsatsinis N., Marinakis Y., A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning, European Journal of Operational Research, 300, 992–1004, 2022.
• 9. Hong Y., Jung S., Kim S., Cha J., Autonomous Mission of Multi-UAV for Optimal Area Coverage, Sensors, 21 (7), 2482, 2021.
• 10. Jiao Y.S., Wang, X.M., Chen H., Chen Y., Research on the Coverage Path Planning of UAVs for Polygon Areas, Conference on Industrial Electronics and Applications, Taichung, 1467-1472, 15-17 June 2010.
• 11. Torres M., Pelta D. A., Verdegay J., Torres J. C., Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction, Expert Systems With Applications, 55 (1), 441–451, 2016.
• 12. Franco C. D., Buttazzo G., Coverage Path Planning for UAVs Photogrammetry with Energy and Resolution Constraints, Journal of Intelligent & Robotic Systems, 83 (1), 445–462, 2016.
• 13. Cabreira T. M., Brisolara L. B., Paulo R. Jr. F., Survey on coverage path planning with unmanned aerial vehicles, Drones, 3 (1), 1-38, 2019.
• 14. Guo Y., Liu C., Coombes M., Spraying Coverage Path Planning for Agriculture Unmanned Aerial Vehicles, International Conference on Automation and Computing, Portsmouth, United Kingdom, 1-6, 02-04 September 2021.
• 15. Elmokadem T., Savkin A. V., Computationally-Efficient Distributed Algorithms of Navigation of Teams of Autonomous UAVs for 3D Coverage and Flocking, Drones, 5 (4), 1-35, 2021.
• 16. Shah K., Schmidt A. E., Ballard G., Schwager M., Large Scale Aerial Multi-Robot Coverage Path Planning, Field Robotics, 2 (1), 1971–1998, 2022.
• 17. Liu C., Zhang S., Akbar A., Ground Feature Oriented Path Planning for Unmanned Aerial Vehicle Mapping, IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 12 (4), 1175-1187, 2019.
• 18. Nagasawa R., Mas E., Moya L., Koshimura S., Model based analysis of multi UAV path planning for surveying postdisaster building damage, Scientific reports, 11 (1), 1-14, 2021.
• 19. Nedjati A., Izbirak G., Vizvari B., Arkat J., Complete Coverage Path Planning for a Multi-UAV Response System in Post-Earthquake Assessment, Robotics, 5 (4), 1-15, 2016.
• 20. Almadhoun R., Taha T., Seneviratne L., Zweiri Y., A survey on multi robot coverage path planning for model reconstruction and mapping, SN Applied Sciences, 1 (847), 1-24, 2019.
• 21. Yaguchi Y., Tomeba, T. Region Coverage Flight Path Planning Using Multiple UAVs to Monitor the Huge Areas, International Conference on Unmanned Aircraft Systems, Athens, Greece, 1677-1682, 15-18, June 2021.
• 22. Cho S. W., Park H. J., Lee H., Shim D. H., Kim S.Y., Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations, Computers & Industrial Engineering, 161 (1), 107612, 2021.
• 23. Nielsen L. D., Sung I., Nielsen P., Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges, Sensors, 19 (19), 1-11, 2019.
• 24. Arkin E. M., Fekete S. P., Mitchell J. S., Approximation algorithms for lawn mowing and milling, Computational Geometry, 17 (1-2), 25-50, 2000.
• 25. Galceran E., Carreras M., A survey on coverage path planning for robotics, Robotics and Autonomous Systems, 61 (12), 1258–1276, 2013.
• 26. Tan C. S., Mohd-Mokhtar R., Arshad M. R., A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms, IEEE Access, 9 (1), 119310 -119342, 2021.
• 27. Mannan A., Obaidat M. S., Mahmood K., Ahmad A., Ahmad,R. Classical versus reinforcement learning algorithms for unmanned aerial vehicle network communication and coverage path planning: A systematic literature review, International Journal of Communication Systems, 36 (5), 1-31, 2023.
• 28. Xie J., Lei J., Carrillo L. R. G., Optimal Path Planning for Unmanned Aerial Systems to Cover Multiple Regions, AAIAA Scitech Forum, 1-12, 2019.
• 29. Xie J., Chen J., Multi-Regional Coverage Path Planning for Robots with Energy Constraint, IEEE 16th International Conference on Control & Automation, Sapporo, Hokkaido, Japan, 1372-1377, 09-11 October 2020. 30. Ng K., Sancho N., Regional surveillance of disjoint rectangles: a travelling salesman formulation, Journal of the Operational Research Society, 60 (1), 215-220, 2009.
• 31. Karasakal O., Minisum and maximin aerial surveillance over disjoint rectangles, Top, 24 (1), 705–724, 2016. 32. Xie J., Carrillo L. R. G., Jin L., An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems, IEEE Control Systems Letters, 3 (1), 67-72, 2019.
• 33. Xie J., Carrillo L. R. G., Jin L., Path Planning for UAV to Cover Multiple Separated Convex Polygonal Regions, IEEE Access, 8 (1), 51770-51785, 2020.
• 34. Chen X., Chen J., Du C., Xu Y., Region Coverage Path Planning of Multiple Disconnected Convex Polygons Based on Simulated Annealing Algorithm, 4th International Conference on Computer and Communication Engineering Technology, 238-242, 13-15 August 2021. 35. Choi Y., Choi Y., Briceno S., Mavris D. N., Multi-UAS Path-Planning for a Large-scale Disjoint Disaster Management, International Conference on Unmanned Aircraft Systems (ICUAS), Atlanta, GA, USA, 799-807, 11-14 June 2019.
• 36. Chen J., Du C., Lu X., Chen K., Multi-Region Coverage Path Planning for Heterogeneous Unmanned Aerial Vehicles Systems, International Conference on Service-Oriented System Engineering, San Francisco, USA, 356-361, 04-09 April 2019.
• 37. Yu X., Jin S., Shi D., Li L., Kang Y., Zou J., Balanced Multi-Region Coverage Path Planning for Unmanned Aerial Vehicles, IEEE International Conference on Systems, Man, and Cybernetics, Toronto, Canada, 3499-3506, 11-14 October 2020.
• 38. Zuo Y., Tharmarasa R., Jassemi-Zargani R., Kashyap N., Thiyagalingam J., MILP Formulation for Aircraft Path Planning in Persistent Surveillance, IEEE Transactions on Aerospace and Electronic Systems, 56 (5), 3796-3811, 2020.
• 39. Chen J., Ling F., Zhang Y., You T., Liu Y., Du X., Coverage path planning of heterogeneous unmanned aerial vehicles based on ant colony system, Swarm and Evolutionary Computation, 69 (1), 101005, 2022.
• 40. Chen J., Du C., Zhang Y., Han P., Wei,W. A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs, IEEE Transactions on Intelligent Transportation Systems, 23 (12), 25546 - 25556, 2022.
• 41. Yu K., O’Kane J. M., Tokekar P., Coverage of an Environment Using Energy-Constrained Unmanned Aerial Vehicles, International Conference on Robotics and Automation (ICRA), Montreal, Canada, 3259-3265, 20-24 May 2019.
• 42. Karasakal O., Karasakal E., Maraş G., Multi objective aerial surveillance over disjoint rectangles, Computers & Industrial Engineering,148 (1), 1-13, 2020.
• 43. Vasquez-Gomez J. I., Herrera-Lozada J.-C., Olguin-Carbajal M., Coverage Path Planning for Surveying Disjoint Areas, International Conference on Unmanned Aircraft Systems (ICUAS), Dallas, TX, USA, 899-904, 12-15 June 2018.
• 44. Peña P. F., Luna M. A., Isaac M. S. A, Ragab A. R., Elmenshawy K., Gómez, Campoy D. M. P., Molina M., A Proposed System for Multi-UAVs in Remote Sensing Operations, Sensors, 22 (1), 1-13, 2022.
• 45. Shao X.X., Gong Y.J., Zhan Z.H., Zhang J., Bipartite Cooperative Coevolution for Energy-Aware Coverage Path Planning of UAVs, IEEE Transactions On Artificial Intelligence, 3 (1), 29-42, 2022.
• 46. Xie J., Chen J., Multiregional Coverage Path Planning for Multiple Energy Constrained UAVs, Transactions on Intelligent Transportation Systems, 23 (10), 17366 - 17381, 2022.
• 47. Xie J., Zhang W., Chen J., Path Planning for Multiple Energy Constrained Unmanned Aerial Vehicles to Cover Multiple Regions, AIAA AVIATION Forum, 1-11, 2020.
• 48. Khanam Z., Saha S., Ehsan S., Stolkin R., Mcdonald-Maier K., Coverage Path Planning Techniques for Inspection of Disjoint Regions With Precedence Provision, IEEE Access, 9 (1), 5412-5427, 2020.
• 49. Muñoz J., López B., . Quevedo F., Monje C. A., Garrido S., Moreno L. E., Multi UAV Coverage Path Planning in Urban Environments, Sensors, 21 (21), 1-18, 2021.
• 50. Luna,M. A., Isaac M. S. A., Ragab A. R., Campoy P., Peña P. F., Molina M., Fast Multi-UAV Path Planning for Optimal Area Coverage in Aerial Sensing Applications, Sensors, 22 (6), 1-25, 2022.
• 51. Karasakal O., Karasakal E.,Maraş G., Multiobjective aerial surveillance over disjoint rectangles, Computers & Industrial Engineering, 148, 106732, 2020.
• 52. Kara İ., Güden H., Koç Ö. N., Genelleştirilmiş Gezgin Satıcı Problemi İçin Polinom Büyüklükteki Yeni Karar Modelleri., 2011.
• 53. Pop P. C., Kara I., Marc, A. H. New mathematical models of the generalized vehicle routing problem and extensions, Applied Mathematical Modelling, 36 (1), 97–107, 2012.
• 54. Bektaş T., Erdoğan G., Røpke S., Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem, Transportation Science, 45 (3), 299-316, 2011.
• 55. Freitas M., Silva J. M. P., Uchoa E., A unified exact approach for Clustered and Generalized Vehicle Routing Problems, Computers & Operations Research, 149,106040, 2023.
• 56. Pop P. C., Cosma O., Sabo C., Sitar C. P., A comprehensive survey on the generalized traveling salesman problem, European Journal of Operational Research, 314 (3), 819-835, 2024.
• 57. Chen J., Zhang R., Zhao H., Li J., He J., Path Planning of Multiple Unmanned Aerial Vehicles Covering Multiple Regions Based on Minimum Consumption Ratio, Aerospace, 10 (2), 1-16, 2023.
• 58. Huang J., Luo Y., Quan Q., Wang B., Xue X., Zhang Y., An autonomous task assignment and decision-making method for coverage path planning of multiple pesticide spraying UAVs, Computers and Electronics in Agriculture, 212, 108128, 2023.
• 59. Du L., Fan Y., Gui M., Zhao D., A Multi-Regional Path-Planning Method for Rescue UAVs with Priority Constraints, Drones, 7, 1-32, 2023.
• 60. GAMS. GAMS® Documentation Center. https://gams.com./latest/docs/. Erişim tarihi Kasım 8, 2024.