BÖLGESEL KEŞİF YAPAN HAVA ARAÇLARI İÇİN İKİ AMAÇLI GÖREV PLANLAMASI

Year 2024, Volume: 29 Issue: 2, 413 - 430, 30.08.2024

Ayşegül Atak , Diclehan Tezcaner Öztürk

https://doi.org/10.17482/uumfd.1371681

Abstract

İnsanlı veya insansız hava araç sistemleri ile birlikte keşif ve gözetleme, kara ve sınır güvenliği, arama ve kurtarma operasyonları gibi önemli faaliyetler yürütülür. Özellikle insansız hava araçlarının kullanımı ile hem sivil hem askeri uygulamalarda bilgi edinilmesi ve müdahale edilmesi kolaylaşmaktadır. İyi bir görev planlama yapılması faaliyetlerin başarı ile yürütülmesi için büyük önem taşımaktadır. Bu çalışmada bölgesel gözetleme yapan hava keşif araçları için görev planlaması yapılmıştır. Bir hava aracı kalkış noktasından göreve başlayarak hedef bölgeleri gözetlemekte ve kalkış noktasına dönmektedir. Çalışmada hedefler, literatürdeki genel yaklaşım olan düğüm ile temsil edilmenin aksine, dikdörtgen alanlar olarak temsil edilmiştir. Bu alanların içini şeritler halinde tarayarak hedeften bilgi edinilmektedir. Rotalar oluşturulurken birbiri ile çelişen iki amaç gözetilmiştir. Birincisi uğranılan hedeflerden elde edilen toplam bilgiyi maksimize etmek ikincisi ise görev boyunca kat edilen toplam mesafeyi minimize etmektir. Etkin çözümlerin bulunması için iki amaçlı karma tam sayılı programlama modeli geliştirilmiş ve epsilon-kısıt yöntemi ile çözülmüştür. Büyük boyutlu problemler için de bir sezgisel çözüm yöntemi önerilmiştir. Tüm çözüm yöntemleri farklı boyutlardaki problemlerde karşılaştırılmıştır.

Keywords

Çok Amaçlı Optimizasyon, Görev Planlama, Hava Araçları, Oryantiring Problemi

Biobjective Mission Planning For Aerial Vehicles Tasked with Regional Reconnaissance

Abstract

Manned and unmanned aerial vehicle systems are used for important tasks such as reconnaissance and surveillance, land and border security, and search and rescue operations. Especially with the use of unmanned aerial vehicles, obtaining information and intervention become easier in both civilian and military applications. To carry out all these tasks successfully, a good mission planning is of great importance. In this study, we consider the mission planning of aerial vehicles tasked with conducting regional reconnaissance. An aircraft takes off from a base, visits the target areas, and returns back to the base. In contrast with the majority of the studies in the literature that represent the targets with nodes, we represent the targets with rectangular regions in this study. These areas are searched in strips to acquire information. Two conflicting objectives are considered in forming the routes. The first objective is maximizing the total information obtained from the targets visited, and the second is minimizing the total distance traveled during the mission. To find the efficient solutions, a biobjective mixed integer programming model is developed and solved using the 𝜀-constraint method. A heuristic solution method is also proposed for larger problem instances. Both solution methods are tested on different-sized problems.

Keywords

Multiobjective Optimization, Mission Planning, Aerial Vehicles, Orienteering Problem

References

• Chankong, V. ve Haimes, Y.Y. (1983) Multiobjective Decision Making: Theory and Methodology, North-Holland, New York.
• Chen, J., Du, C., Zhang, Y., Han, P., ve Wei, W. (2022) A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs. IEEE Transactions on Intelligent Transportation Systems, 23 (12), 25546-25556. doi: 10.1109/TITS.2021.3066240
• Chen, J., Zhang, R., Zhao, H., Li, J. ve He, J. (2023) Path Planning of Multiple Unmanned Aerial Vehicles Covering Multiple Regions Based on Minimum Consumption Ratio. Aerospace, 10, 93. doi: 10.3390/aerospace10020093
• Cho, S.-W., Park, J.-H., Park, H.-J., ve Kim, S. (2022) Multi-UAV Coverage Path Planning Based on Hexagonal Grid Decomposition in Maritime Search and Rescue. Mathematics, 10 (83). doi: 10.3390/math10010083
• Evers, L., Glorie, K., Van Der Ster, S., Barros, A. I., ve Monsuur, H. (2014) A two-stage approach to the orienteering problem with stochastic weights. Computers & Operations Research, 43, 248-260. doi: 10.1016/j.cor.2013.09.011
• Golden, B.L., Levy, L. ve Vohra, R. (1987) The orienteering problem, Naval Research Logistics, 34:3, 307 – 318.
• Golden, B.L., Wang, Q. ve Liu, L. (1988) A multifaceted heuristic for the orienteering problem, Naval Research Logistics, 35:3, 359-366.
• Jiao, Y. S., Wang, X. M., Chen, H. ve Li, Y. (2010) Research on the coverage path planning of uavs for polygon areas. In 2010 5th IEEE Conference on Industrial Electronics and Applications, 1467-1472, IEEE. doi: 10.1109/ICIEA.2010.5514816
• John, M. Panton, D. ve White, K. (2001) Mission planning for regional surveillance, Annals of Operations Research, 108, 157–173. doi: 10.1023/A:1016063129217
• Karasakal, O. (2016) Minisum and maximin aerial surveillance over disjoint rectangles, TOP, 24, 705–724. doi: 10.1007/s11750-016-0416-1
• Karasakal, O., Karasakal, E. ve Maraş, G. (2020) Multiobjective aerial surveillance over disjoint rectangles, Computers & Industrial Engineering, 148. doi: 10.1016/j.cie.2020.106732
• Kyriakakis, N. A., Marinaki, M., Matsatsinis, N. ve Marinakis, Y. (2022) A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning, European Journal of Operational Research, 300 (3), 992-1004. doi: 10.1016/j.ejor.2021.09.008
• Le, W., Xue, Z., Chen, J. ve Zhang, Z. (2022) Coverage Path Planning Based on the Optimization Strategy of Multiple Solar Powered Unmanned Aerial Vehicles, Drones, 6, 203. doi: 10.3390/drones6080203
• Lo, M. H., Liang, Y. C. ve Hsieh, J. C. (2010) A modified variable neighborhood search algorithm for orienteering problems. The 40th International Conference on Computers & Industrial Engineering, Awaji, Japan, 2010, 1-6. doi: 10.1109/ICCIE.2010.5668224
• Majeed, A. ve Hwang, S.O. (2021) A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments. Aerospace, 8, 343. doi: 10.3390/aerospace8110343
• Muñoz, J., López, B., Quevedo, F., Monje, C.A., Garrido, S. ve Moreno, L.E. (2021) Multi UAV Coverage Path Planning in Urban Environments. Sensors, 21 (21):7365. doi: 10.3390/s21217365
• Nedjati, A., Izbirak, G., Vizvari, B. ve Arkat, J. (2016) Complete Coverage Path Planning for a Multi-UAV Response System in Post-Earthquake Assessment, Robotics, 5(4), 26. doi: 10.3390/robotics5040026
• Ng, K.Y.K, ve Sancho, N.G.F. (2009) Regional surveillance of disjoint rectangles: a travelling salesman formulation, Journal of the Operational Research Society, 60:2, 215- 220. doi: 10.1057/palgrave.jors.2602507
• Sokkappa, P. (1990) The cost-constrained traveling salesman problem, The Degree of Doctor of Philosophy, Stanford University.
• Szwarc, K., ve Boryczka, U. (2022) A novel approach to the Orienteering Problem based on the Harmony Search algorithm. PLoS ONE 17(2): e0264584. doi: 10.1371/journal. pone.0264584
• Patel, N., Narayanaswamy, N.S. ve Joshi, A. (2020) Hybrid Genetic Algorithm for Ridesharing with Timing Constraints: Efficiency Analysis with Real-World Data. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO’20, 1159–1167. doi:10.1145/3377930.3389804
• Tarakçı, K. (2021) Vehicle routing for aerial surveillance with a homogeneous fleet, The Degree of Master of Science in Industrial Engineering, The Graduate School of Natural and Applied Sciences of Middle East Technical University, Ankara
• Tsiligirides, T. (1984) Heuristic Methods, Applied to Orienteering, Journal of the Operational Research Society, 35, 797–809. doi: /10.1057/jors.1984.162
• Vansteenwegen, P., & Gunawan, A. (2019). Orienteering problems. EURO Advanced Tutorials on Operational Research, Springer.
• Vasquez-Gomez, J. I., Herrera-Lozada, J. C., ve Olguin-Carbajal, M. (2018) Coverage path planning for surveying disjoint areas, In 2018 International Conference on Unmanned Aircraft Systems (ICUAS), 899-904, IEEE. doi: 10.1109/ICUAS.2018.8453386
• Vazquez-Carmona E. V., Vasquez-Gomez, J. I., Herrera-Lozada J. C., Antonio-Cruz M. (2022) Coverage path planning for spraying drones, Computers & Industrial Engineering, 168, 108125. doi: 10.1016/j.cie.2022.108125
• Wang, Y., Kırubarajan, T., Tharmarasa, R., Zargani, R. ve Kashyap, N. (2018) Multiperiod coverage path planning and scheduling for airbone surveillance, IEEE Transactions on Aerospace and Electronic Systems, 54:5. doi: 10.1109/TAES.2018.2812538
• Yuan, J., Liu, Z., Lian, Y., Chen, L., An, Q., Wang, L. ve Ma, B. (2022) Global Optimization of UAV Area Coverage Path Planning Based on Good Point Set and Genetic Algorithm, Aerospace, 9, 86. doi:10.3390/ aerospace9020086
• Zuo, Y., Tharmarasa, R., Zargani, R., Kashyap, N., Thıyagalıngam, J. ve Kırubarajan, T. (2020) MILP formulation for aircraft path planning in persistent, IEEE Transactions on Aerospace and Electronic Systems, 56:5, 3796-3811. doi: 10.1109/TAES.2020.2983532