Çoklu İHA’larla Kısıt Tatmin Problemi Temelli Çok Amaçlı Görev Planlaması

Abstract

İ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.