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

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

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

References

1. Chankong, V. ve Haimes, Y.Y. (1983) Multiobjective Decision Making: Theory and Methodology, North-Holland, New York.
2. 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
3. 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
4. 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
5. 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
6. Golden, B.L., Levy, L. ve Vohra, R. (1987) The orienteering problem, Naval Research Logistics, 34:3, 307 – 318.
7. Golden, B.L., Wang, Q. ve Liu, L. (1988) A multifaceted heuristic for the orienteering problem, Naval Research Logistics, 35:3, 359-366.
8. 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

9. 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
10. Karasakal, O. (2016) Minisum and maximin aerial surveillance over disjoint rectangles, TOP, 24, 705–724. doi: 10.1007/s11750-016-0416-1
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. Sokkappa, P. (1990) The cost-constrained traveling salesman problem, The Degree of Doctor of Philosophy, Stanford University.
20. 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
21. 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
22. 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
23. Tsiligirides, T. (1984) Heuristic Methods, Applied to Orienteering, Journal of the Operational Research Society, 35, 797–809. doi: /10.1057/jors.1984.162
24. Vansteenwegen, P., & Gunawan, A. (2019). Orienteering problems. EURO Advanced Tutorials on Operational Research, Springer.
25. 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
26. 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
27. 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
28. 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
29. 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