Sürü İnsansız Hava Araçlarında Görev Planlama için Bütüncül Bir Optimizasyon Yaklaşımı

Abstract

Çok sayıda ve farklı tipte İnsansız Hava Aracını (İHA) kapsayan görev planlama problemleri, her aracın sensör paketi, konumu, yakıtı ve faydalı yük kapasitesi gibi çeşitli kısıtlarına göre hangi görevlere atanabileceğini belirlemeyi amaçlar. Bu çalışma, böyle bir heterojen sürüde yakıt tüketimini, toplam görev süresini ve iniş-kalkış sayısını ve buna bağlı olarak riskini aynı anda en aza indiren çok-amaçlı bir planlama çerçevesi sunmaktadır. Literatürde yaygın olan Kısıt Tatmin Problemi (KTP) yaklaşımları, çoğu zaman statik kabuller ve açgözlü seçimler yüzünden büyük ölçekli, dinamik senaryolarda yetersiz kalmaktadır. Bu eksikliği gidermek için İyileştirilmiş Zamansal KTP (İZKTP) ve Adaptif Mutasyon Tabanlı Fizibilite-ve Restorasyon (AMFR) adlı iki arama stratejisi önerilmiştir. Problemin biçimsel temeli Zamansal KTP'dir (ZKTP); burada görevler zamansal kümelere ayrılır ve geri izleme, ileri kontrol, yay tutarlılığı ile düğüm tutarlılığını içeren, bunun yanı sıra havacılık problemleri özelinde hibrit bir çözücü geliştirilir. Çözücü, iniş yapmadan ardışıl görevlere geçiş veya havadan yakıt ikmali gibi havacılığa özgü dinamikleri hesaba katar. İlk aşamada sentetik ancak operasyonel gerçekliğe yakın verilerle çok sayıda atama senaryosu simüle edilir; ikinci aşamada ise her atama sonrası dinamik programlama temelli etki-alanı güncellemeleri çalıştırılarak zaman pencereleri yeniden düzenlenir. Yeni dinamik etki-alanı tekniği, eşdeğer zaman karmaşıklığında klasik ZKTP'den anlamlı ölçüde daha iyi çözümler üretmiştir. Buna karşılık AMFR, karmaşıklığı düşürmek amacıyla geliştirilmiş olup aynı problem kümesinde üretilen İZKTP çözümleriyle sistematik olarak karşılaştırılmıştır. Sonuçlar, İZKTP'nin global optimuma yakın çözümler bulma olasılığının yüksek fakat nispeten yavaş olduğunu; AMFR'nin ise daha kısa sürede düşük maliyetli çözümler sağlayabildiğini, ancak bu performansı her koşulda tutarlı biçimde koruyamadığını göstermiştir. Deneysel doğrulama için literatürden türetilen veri seti, yedi farklı İHA, on görev ve on bir lokasyondan oluşacak biçimde genişletilmiştir. Görevler irtifa, sensör gereksinimi, yetki seviyesi ve zaman pencereleri bakımından; İHA'lar ise yakıt kapasitesi, hız profili ve faydalı yük açısından heterojendir. Performans ölçütleri toplam yakıt tüketimi (litre), toplam uçuş süresi (dakika), iniş-kalkış sayısı ve görevi tamamlayabilen İHA yüzdesi olarak belirlenmiştir. Deneyler göstermiştir ki İZKTP, on görevlik paketler üzerinde klasik ZKTP'ye göre yakıt ve süre maliyetini üç kata varan, yani yüzde 67'ye ulaşan oranlarda düşürmüştür. Doksan görevlik tam senaryoda İZKTP, otuz görevi havada yeni göreve atama yaparak iniş-kalkış sayısını 90'dan 60'a azaltmış ve yakıt tüketimini 3565 litreden 1953 litreye indirerek yüzde 45 tasarruf sağlamıştır. AMFR yönteminde ise, en kötü koşullarda İZKTP'den yüzde 15 daha fazla yakıt tasarrufu üretmesine rağmen, yüz görevlik simülasyonda toplam uçuş süresini 818 dakika artırmış; buna karşın İZKTP 19 kez daha az iniş-kalkış yaparak risk faktörünü azaltmıştır. Bu bulgular, dinamik etki-alanı güncellemeli İZKTP'nin KTP ile aynı asimptotik karmaşıklıkta daha yüksek kaliteli çözümler üretebildiğini; AMFR'nin ise zincir iyileştirme mantığı sayesinde yerel tuzaklardan kaçarak özellikle ZKTP'nin zor örneklerinde maliyetleri düşürmek için etkin bir alternatif sunduğunu göstermektedir. Sınırlı veri setlerinde ve kısıtlı hesaplama süresinde bu iki yöntemin sağladığı başarı, yakıt ve zaman maliyetlerini uçuş emniyetinden ödün vermeden anlamlı ölçüde azaltabileceğimizi kanıtlamaktadır.

Mission planning problems involving large and heterogeneous fleets of Unmanned Aerial Vehicles (UAVs) aim to determine the feasible allocation of tasks to each vehicle, subject to diverse constraints such as sensor payload, location, fuel capacity, and useful load. This study introduces a multi-objective planning framework that simultaneously minimizes fuel consumption, total mission duration, and the number of takeoff–landing operations, thereby reducing the associated operational risks within such heterogeneous swarms. Conventional Constraint Satisfaction Problem (CSP) approaches in the literature often fail to cope with large-scale and dynamic scenarios due to their reliance on static assumptions and greedy selection strategies. To overcome these limitations, two search strategies are proposed: Improved Temporal CSP (ITCSP) and Adaptive Mutation-based Feasibility and Restoration (AMFR). The formal foundation of the problem is the Temporal CSP (TCSP), where tasks are partitioned into temporal clusters, and a hybrid solver is developed that integrates backtracking, forward checking, arc consistency, and node consistency, while further incorporating aviation-specific dynamics. The solver accounts for operational constraints such as consecutive task transitions without landing and in-flight refueling. In the first stage, numerous assignment scenarios are simulated using synthetic yet operationally realistic data. In the second stage, dynamic programming-based domain updates are executed after each assignment to reorganize time windows. The proposed dynamic domain updating technique consistently yields superior solutions compared to classical TCSP, while maintaining equivalent time complexity. Conversely, AMFR is designed to reduce computational complexity and is systematically benchmarked against ITCSP over identical problem sets. Results indicate that ITCSP has a higher likelihood of converging to near-global optima, though at slower rates, whereas AMFR can produce lower-cost solutions more rapidly but with less consistency across diverse conditions. For experimental validation, a dataset adapted from the literature was extended to encompass seven UAVs, ten tasks, and eleven locations. The tasks are heterogeneous in terms of altitude, sensor requirements, authorization levels, and time windows, while the UAVs differ in fuel capacity, speed profile, and payload characteristics. Performance metrics are defined as total fuel consumption (liters), total flight duration (minutes), number of takeoff–landing operations, and the percentage of UAVs successfully completing their assigned missions. Experimental results demonstrate that, for ten-task packages, ITCSP reduced fuel and time costs by up to a factor of three (67%) compared with classical TCSP. In a full-scale scenario with ninety tasks, ITCSP reassigned thirty tasks in-flight, thereby reducing the number of takeoff–landing operations from 90 to 60 and cutting fuel consumption from 3565 liters to 1953 liters, achieving a 45% reduction. Under worst-case conditions, AMFR achieved up to 15% greater fuel savings than ITCSP; however, in simulations with 100 tasks it prolonged total flight time by 818 minutes, while ITCSP performed 19 fewer takeoff–landing cycles, thereby reducing the associated operational risk. These findings demonstrate that ITCSP, enhanced with dynamic domain updates, is capable of producing higher-quality solutions at the same asymptotic complexity as conventional CSP. Meanwhile, AMFR, through its chain-improvement mechanism, offers an effective alternative for reducing costs in particularly challenging TCSP instances by escaping local optima. The demonstrated success of these two methods on limited datasets and under restricted computational budgets substantiates the potential for significantly reducing fuel and time costs without compromising flight safety.