Araştırma Makalesi
BibTex RIS Kaynak Göster

Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması

Yıl 2025, Cilt: 40 Sayı: 3, 1673 - 1688

Emre Ayvaz , Yılmaz Atay , İsmail Babaoğlu

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

Öz

İnsansız hava araçlarının dahil olduğu çoklu görev planlama problemleri; zamana bağlı görevler ve çeşitli türdeki araçların sensör, konum, yakıt, faydalı yük vb. farklı yetenek ve kısıtlarına bağlı olarak ne tür görevleri yapabileceğinin belirlenmesini ve bunların planlamasını ifade eder. Bu problem, Kısıt Tatmin Problemi (KTP) olarak modellenebilmektedir. Zamansal KTP (ZKTP) ise ardışıl görevlerin, zamansal anlamda görev ikililerine bölünerek KTP üzerine inşasını modeller. Bu işleme bağlı olarak görev isterleri ile İnsansız Hava Aracının (İHA)’nın yetenekleri arasındaki statik ve dinamik kısıtlara bağlı olarak gerçekleştirebilecek eylemler ile ilgili baskın bir çözüm kümesi aranır. Böylece görevler ile mevcut İHA’ların yetenekleri arasındaki ilişki, zamansal boyutta irdelenerek çok amaçlı problemleri optimize eden aday çözümler bulunur. İyileştirilmiş ZKTP (İZKTP) yönteminde KTP’deki aç gözlü yaklaşım yerine, etki alanındaki en yüksek puana sahip İHA’nın göreve atanması önerilmiştir. Ek olarak, iyileştirilmiş ileri kontrol yöntemiyle bir sonraki görevin etki alanındaki İHA'ların gerçek zamanlı konumlarına ve zamanlarına göre atama durumu değerlendirilebilmektedir. Bu çalışmada, yakıt tüketimini ve toplam havada kalma süresini en aza indiren uygun bir çözüm kümesinin KTP ile aynı zaman karmaşıklığı içinde bulunması amaçlanır. Burada, zamansal kısıt tatmin modeli gerçeklenmiş ve çeşitli görevlerde karmaşıklığı aşamalı olarak değiştirilerek geri izleme (Backtracking), ileri kontrol (Forward Checking), yay tutarlılığı (Arc Consistency), düğüm tutarlılığı (Node Consistency) yöntemleriyle önerilen yaklaşımın performansı, deneysel çalışmalarla doğrulanmıştır. Bu kapsamda yapılan deneyler iki farklı aşamayı içermektedir. İlk aşamada, çeşitli yetenek ve kısıtlara sahip İHA'ların farklı isterleri olan görevlere atanmasını içeren farklı simülasyonlar gerçekleştirilmiştir. Buradaki simülasyonlarda olası gerçek senaryolardan esinlenen sentetik veriler kullanılmıştır. İkinci aşamada ise atamalar sonrası dinamik programlama temelli etki alanı güncellemesiyle görev ikililerinin zaman pencerelerinde değişen süreçleri takip eden düğüm kontrolü, geri izleme, ileri kontrol ve yay tutarlılığı yaklaşımları kullanılmıştır. Önerilen KTP ile gerçekleştirilen testler sonucu sekiz farklı görev içeren iş paketinde, KTP ile benzer zaman karmaşıklığında daha uygun maliyet ve zaman çıktıları elde edilmiştir. Testler kapsamında 64 farklı görev içeren bir problem için önerilen yöntem, standart KTP’ye göre12 adet daha az İHA kullanılmasını sağlayarak önemli bir performans artışına ulaşmıştır.

Anahtar Kelimeler

Çoklu Görev Atama Çoklu İHA Dinamik Programlama Geri İzleme İleri Kontrol Kısıt Tatmin Problemi

Kaynakça

  • 1. Achtelik M.C., Stumpf J., Gurdan D., Doth K.M. Design of a Flexible High Performance Quadcopter Platform Breaking the MAV Endurance Record with Laser Power Beaming. IEEE/RSJ International Conference on Intelligent Robots and Systems, 5166-5172, 2011.
  • 2. Alighanbari M., Bertuccelli L., How J. Filter-Embedded UAV Task Assignment Algorithms for Dynamic Environments. Doktora Tezi, Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, Cambridge, ABD, 2004.
  • 3. Allen J.F. Maintaining Knowledge About Temporal Intervals. Communications of the ACM, 26 (11), 832-843, 1983.
  • 4. Amazon. Prime Air. About Amazon. https://www.aboutamazon.com/news/tag/prime-air. Yayın tarihi: 2020. Erişim tarihi: 24 Ekim 2023.
  • 5. Bektas T. The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures. Omega, 34 (2), 209-219, 2006.
  • 6. Bethke B., Valenti M., How J.P. UAV Task Assignment. IEEE Robotics and Automation Magazine, 15 (1), 39-44, 2008.
  • 7. Byung D.S., Kyungsu P., Jonghoe K. Persistent UAV Delivery Logistics: MILP Formulation and Efficient Heuristic. Computers & Industrial Engineering, 120, 418-428, 2018.
  • 8. Chen Y., Yang D., Yu J. Multi-UAV Task Assignment with Parameter and Time-Sensitive Uncertainties Using Modified Two-Part Wolf Pack Search Algorithm. IEEE Transactions on Aerospace and Electronic Systems, 54 (6), 2853-2872, 2018.
  • 9. De Almeida D.R.A. ve diğerleri. Monitoring Restored Tropical Forest Diversity and Structure Through UAV-Borne Hyperspectral and Lidar Fusion. Remote Sensing of Environment, 264, 112582, 2021.
  • 10. Doherty J., Kvarnström F., Heintz F. A Temporal Logic-Based Planning and Execution Monitoring Framework for Unmanned Aircraft Systems. Autonomous Agents and Multi-Agent Systems, 19 (3), 332-377, 2009.
  • 11. Edison E., Shima T. Integrated Task Assignment and Path Optimization for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms. Computers & Operations Research, 38 (1), 340-356, 2011.
  • 12. Fabiani P., Fuertes V., Piquereau A., Mampey R., Teichteil-Konigsbuch F. Autonomous Flight and Navigation of VTOL UAVs: From Autonomy Demonstrations to Out-of-Sight Flights. Aerospace Science and Technology, 11 (2-3), 183-193, 2007.
  • 13. Fargier H., Lang J. Uncertainty in Constraint Satisfaction Problems: A Probabilistic Approach. European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty, 97-104, 1993.
  • 14. Gao H. ve diğerleri. UAV-Assisted Multitask Allocation Method for Mobile Crowd Sensing. IEEE Transactions on Mobile Computing, 2022.
  • 15. Gao S., Wu J., Ai J. Multi-UAV Reconnaissance Task Allocation for Heterogeneous Targets Using Grouping Ant Colony Optimization Algorithm. Soft Computing, 25 (6), 7155-7167, 2021.
  • 16. Gaowei J., Jianfeng W., Peng W., Qingyang C., Yujie W. Using Multilayer Coding Genetic Algorithm to Solve Time-Critical Task Assignment of Heterogeneous UAV Teaming. International Conference on Control, Automation and Diagnosis (ICCAD), Grenoble, Fransa, 2019.
  • 17. Hart P.E., Nilsson N.J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4 (2), 100-107, 1968.
  • 18. Hillier F.S. Introduction to Operations Research. McGraw-Hill, New York, ABD, 2001.
  • 19. Huang H., Zhuo T. Multimodel Cooperative Task Assignment and Path Planning of Multiple UCAV Formation. Multimedia Tools and Applications, 78 (1), 415-436, 2019.
  • 20. Ji X., Zhao Y. Architecture Design for Unmanned Aerial Vehicle Mission Planning System. International Conference on Modeling, Simulation and Big Data Analysis, 419-424, 2019.
  • 21. Jia Z., Yu J., Ai X., Xu X., Yang D. Cooperative Multiple Task Assignment Problem with Stochastic Velocities and Time Windows for Heterogeneous Unmanned Aerial Vehicles Using a Genetic Algorithm. Aerospace Science and Technology, 76, 112-125, 2018.
  • 22. Jussien N., Rochart G., Lorca X. Choco: An Open Source Java Constraint Programming Library. CPAIOR'08 Workshop on Open-Source Software for Integer and Constraint Programming, 1-10, 2008.
  • 23. Kiran B.R., Sobh I., Talpaert V., Mannion P., Al Sallab A.A., Yogamani S., Pérez P. Deep Reinforcement Learning for Autonomous Driving: A Survey. IEEE Transactions on Intelligent Transportation Systems, 23 (6), 4909-4926, 2021.
  • 24. Laroche P., Charpillet F., Schott R. Mobile Robotics Planning Using Abstract Markov Decision Processes. 11th IEEE International Conference on Tools with Artificial Intelligence, 299-306, 1999.
  • 25. LaValle S.R., Latombe J.C. An Approach to Mission Planning for Unmanned Aerial Vehicles. IEEE International Conference on Robotics and Automation (ICRA), 1995.
  • 26. Li J.T., Zhang S., Zheng Z., Xing L.N., He R.J. Research on Multi-UAV Loading Multi-Type Sensors Cooperative Reconnaissance Task Planning Based on Genetic Algorithm. 13th International Intelligent Computing Theories and Application, Liverpool, İngiltere, 2017.
  • 27. Li M. ve diğerleri. Task Allocation on Layered Multiagent Systems: When Evolutionary Many-Objective Optimization Meets Deep Q-Learning. IEEE Transactions on Evolutionary Computation, 25 (3), 842-855, 2021.
  • 28. Low A.M. The Pilotless Aircraft. Flight, 1916.
  • 29. Luo W. ve diğerleri. Learning-Based Policy Optimization for Adversarial Missile-Target Assignment. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51 (7), 4426-4437, 2021.
  • 30. McGetrick R.J. The Ryan Firebee. Proceedings of the IEEE, 51 (3), 1963.
  • 31. Mills-Tettey G.A., Stentz A., Dias M.B. The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs. Carnegie Mellon University, Robotics Institute, Pittsburgh, ABD, 2007.
  • 32. Mohsan S.A.H., Khan M.A., Noor F., Ullah I., Alsharif M.H. Towards the Unmanned Aerial Vehicles (UAVs): A Comprehensive Review. Drones, 6 (6), 147, 2022.
  • 33. Nethercote N., Stuckey P.J., Becket R., Brand S., Duck G.J., Tack G. MiniZinc: Towards a Standard CP Modelling Language. International Conference on Principles and Practice of Constraint Programming, 529-543, 2007.
  • 34. Nex F., Armenakis C., Cramer M., Cucci D.A., Gerke M., Honkavaara E., Kukko A., Persello C., Skaloud J. UAV in the Advent of the Twenties: Where We Stand and What Is Next. ISPRS Journal of Photogrammetry and Remote Sensing, 184, 215-242, 2022.
  • 35. O'Rourke K.P., Carlton W.B., Bailey T.G. Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search. Military Operations Research, 6 (1), 5-30, 2001.
  • 36. Ramirez-Atencia C., Bello-Orgaz G., R-Moreno M.D., Camacho D. A Simple CSP-Based Model for Unmanned Air Vehicle Mission Planning. IEEE International Symposium on Innovations in Intelligent Systems and Applications (INISTA), Alberobello, İtalya, 146-153, 2014.
  • 37. Ramirez-Atencia C., Bello-Orgaz G., R-Moreno M.D., Camacho D. A Hybrid MOGA-CSP for Multi-UAV Mission Planning. Proceedings of the Companion Publication of the Annual Conference on Genetic and Evolutionary Computation, 120, 2015.
  • 38. Ramirez-Atencia C., Camacho D. Constrained Multiobjective Optimization for Multi-UAV Planning. Journal of Ambient Intelligence and Humanized Computing, 10 (7), 2467-2484, 2019.
  • 39. Richoux F., Uriarte A., Baffier J.F. Ghost: A Combinatorial Optimization Framework for Realtime Problems. IEEE Transactions on Computational Intelligence and AI in Games, 8 (4), 377-388, 2016.
  • 40. Schumacher C., Chandler P., Pachter M. UAV Task Assignment with Timing Constraints. AIAA Guidance, Navigation, and Control Conference and Exhibit, 5664, 2003.
  • 41. Secrest B.R. Travelling Salesman Problem for Surveillance Mission Using Particle Swarm Optimization. Biblioscholar, California, ABD, 2001. 42. Shakoor S. ve diğerleri. Role of UAVs in Public Safety Communications Energy Efficiency Perspective. IEEE Access, 7, 140665-140679, 2019.
  • 43. Shima T., Rasmussen S.J., Sparks A.G. Multiple Task Assignments for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms. Computers & Operations Research, 33 (11), 3252-3269, 2006.
  • 44. Shin J., Badgwell T.A., Liu K.H., Lee J.H. Reinforcement Learning -- Overview of Recent Progress and Implications for Process Control. Computers & Chemical Engineering, 127, 282-294, 2019.
  • 45. Shrestha R., Bajracharya R., Kim S. 6G Enabled Unmanned Aerial Vehicle Traffic Management: A Perspective. IEEE Access, 9, 91119-91136, 2021.
  • 46. Song B.D., Park H., Park K. Toward Flexible and Persistent UAV Service: Multiperiod and Multiobjective System Design with Task Assignment for Disaster Management. Expert Systems with Applications, 206, 2022.
  • 47. Song J., Zhao K., Liu Y. Survey on Mission Planning of Multiple Unmanned Aerial Vehicles. Aerospace, 10 (3), 208, 2023.
  • 48. Sullivan C.J., Bosanac N. Using Multiobjective Deep Reinforcement Learning to Uncover a Pareto Front in Multibody Trajectory Design. AAS/AIAA Astrodynamics Specialist Conference, Virtual Event, 9-12, 2020.
  • 49. Techcrunch. Russian Scientists Put a Defibrillator on a Drone. TechCrunch. https://techcrunch.com/2017/07/27/russian-scientists-put-a-defibrillator-on-a-drone/. Yayın tarihi: 27 Temmuz 2017. Erişim tarihi: 11 Eylül 2023.
  • 50. Turner J., Meng Q., Schaefer G., Whitbrook A., Soltoggio A. Distributed Task Rescheduling with Time Constraints for the Optimization of Total Task Allocations in a Multi-Robot System. IEEE Transactions on Cybernetics, 48 (9), 2583-2597, 2018.
  • 51. Wallace R.J., Freuder E.C. Stable Solutions for Dynamic Constraint Satisfaction Problems. Proceedings of the International Conference on Principles and Practice of Constraint Programming, 447-461, 1998.
  • 52. Wang X., Wang H., Zhang H., Wang M., Wang L., Cui K., Ding Y. A Mini Review on UAV Mission Planning. Journal of Industrial & Management Optimization, 19 (5), 2023.
  • 53. Wu X., Yin Y., Xu L., Wu X., Meng F., Zhen R. Multi-UAV Task Allocation Based on Improved Genetic Algorithm. IEEE Access, 9, 100369-100379, 2021.
  • 54. Xu G., Long T., Wang Z. Target-Bundled Genetic Algorithm for Multi-Unmanned Aerial Vehicle Cooperative Task Assignment Considering Precedence Constraints. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 234 (3), 760-773, 2020.
  • 55. Yan P., Tan B. Evolutionary Group Theoretic Tabu Search Approach to Task Allocation of Autonomous Unmanned Aerial Vehicles. 10th IEEE International Conference on Control and Automation (ICCA), 687-692, 2013.
  • 56. Ye F., Chen J., Sun Q., Tian Y., Jiang T. Decentralized Task Allocation for Heterogeneous Multi-UAV System with Task Coupling Constraints. The Journal of Supercomputing, 77 (1), 77-86, 2021.
  • 57. Yi S., Long Z., Lin J. Task Assignment of Heterogeneous UAV for Antiradar Mission Using CTAP Models. IEEE International Conference on Mechatronics and Automation (ICMA), Tianjin, Çin, 1980-1985, 2019.
  • 58. Zhang X., Chen X. UAV Task Allocation Based on Clone Selection Algorithm. Wireless Communications and Mobile Computing, 1-9, 2021.
Toplam 57 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Konular Karar Desteği ve Grup Destek Sistemleri, Bilgi Sistemleri (Diğer), Algoritmalar ve Hesaplama Kuramı, Modelleme ve Simülasyon, Otonom Ajanlar ve Çok Yönlü Sistemler
Bölüm Makaleler
Yazarlar

Emre Ayvaz 0009-0003-7876-609X

Yılmaz Atay 0000-0002-3298-3334

İsmail Babaoğlu 0000-0002-2503-1482

Erken Görünüm Tarihi 13 Mayıs 2025
Yayımlanma Tarihi
Gönderilme Tarihi 16 Temmuz 2024
Kabul Tarihi 16 Ocak 2025
Yayımlandığı Sayı Yıl 2025 Cilt: 40 Sayı: 3

Kaynak Göster

APA Ayvaz, E., Atay, Y., & Babaoğlu, İ. (2025). Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 40(3), 1673-1688. https://doi.org/10.17341/gazimmfd.1517020
AMA Ayvaz E, Atay Y, Babaoğlu İ. Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması. GUMMFD. Mayıs 2025;40(3):1673-1688. doi:10.17341/gazimmfd.1517020
Chicago Ayvaz, Emre, Yılmaz Atay, ve İsmail Babaoğlu. “Çoklu İHA’larla kısıt Tatmin Problemi Temelli çok amaçlı görev Planlaması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 40, sy. 3 (Mayıs 2025): 1673-88. https://doi.org/10.17341/gazimmfd.1517020.
EndNote Ayvaz E, Atay Y, Babaoğlu İ (01 Mayıs 2025) Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 40 3 1673–1688.
IEEE E. Ayvaz, Y. Atay, ve İ. Babaoğlu, “Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması”, GUMMFD, c. 40, sy. 3, ss. 1673–1688, 2025, doi: 10.17341/gazimmfd.1517020.
ISNAD Ayvaz, Emre vd. “Çoklu İHA’larla kısıt Tatmin Problemi Temelli çok amaçlı görev Planlaması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 40/3 (Mayıs 2025), 1673-1688. https://doi.org/10.17341/gazimmfd.1517020.
JAMA Ayvaz E, Atay Y, Babaoğlu İ. Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması. GUMMFD. 2025;40:1673–1688.
MLA Ayvaz, Emre vd. “Çoklu İHA’larla kısıt Tatmin Problemi Temelli çok amaçlı görev Planlaması”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, c. 40, sy. 3, 2025, ss. 1673-88, doi:10.17341/gazimmfd.1517020.
Vancouver Ayvaz E, Atay Y, Babaoğlu İ. Çoklu İHA’larla kısıt tatmin problemi temelli çok amaçlı görev planlaması. GUMMFD. 2025;40(3):1673-88.