Task assignment and scheduling in UAV mission planning with multiple constraints

Abstract

In the recent years, unmanned aerial vehicles (UAVs) have started to be utilized as the first choice for high risk and long duration tasks, because UAVs are cheaper; they are hard to be noticed and they can perform long duration missions. Furthermore, the utilization of UAVs ensures to reduce the risk to the human life. Examples of this kind of missions includes signal collection, surveillance and reconnaissance and combat support missions. It is valuable to develop a fully autonomous UAV fleet to perform these kinds of tasks when it is needed, because this kind of missions usually start at unexpected times. Other problems which is in the set of high risk and long duration tasks are multiple constraint UAV scheduling, and target assignment problem. In this problem, a fleet of UAVs are supposed to traverse a set of target areas within a limited area. The targets are only available within certain time windows and need to be traversed promptly. Moreover, for some large target areas multiple UAVs are needed to perform the task. The objective of this problem is to find a complete scheduling and UAV-target assignment that minimizes the total fuel consumption of the UAVs. This problem is a highly critical real time problem and needs to be solved almost in real-time. Therefore, methods doing exhaustive search are infeasible. Most of the methods in the literature, try to solve this problem by evolutionary approaches. In this thesis, we developed an algorithmic method to solve this problem. This method uses divide and conquer method to solve this problem. In this way, the problem is transformed into a combination of multiple small problems. We designed a method to convert these small problems into transportation problems. Each transportation problem is solved with simplex algorithm. The method proposed is compared with various methods and has been shown to provide fast, acceptably optimal and reliable results.

Son yıllarda yüksek risk içeren ve uzun zaman gerektiren görevler için insansız hava araçları (İHA'lar) ilk tercih olarak seçilmeye başlanmıştır. Çünkü İHA'lar ucuz, farkedilmesi zor ve uzun süreli işlere uygun araçlardır. Dahası İHA'ları kullanmak insan hayatının riske atıldığı durumları azaltmaktadır. Bu tip görevlere örnek olarak sinyal toplama, keşif ve gözetleme görevleri ve muharebe destek görevleri gösterilebilir. Bu tip işleri gerektiği zaman yapabilecek tamamen otonom bir İHA filosuna sahip olmak değerlidir. Çünkü genellikle bu tip görevler beklenmedik zamanlarda başlamaktadırlar. Yüksek risk içeren ve uzun zaman gerektiren görevlere bir başka örnekte İHA'lar ile zaman planlaması ve hedef görevlendirmesi problemidir. Bu problemde İHA filosu belirli bir alandaki bir dizi hedef alanını katetmelidir. Hedefler sadece belirli bir zaman aralığında uygun olup o zaman aralığı içinde katedilmelidirler. Dahası bazı geniş alana yayılmış hedefleri katetmek için birden fazla İHA gerekmektedir. Bu problemde amaç İHA'lar için tam bir zaman planlaması ve İHA-hedef görevlendirmesi yapmanın yanı sıra yakıt tüketimini de azaltmaktır. Bu problem oldukça kritik ve gerçek zamanlı bir problemdir ve hızlı bir şekilde çözülmesi gerekmektedir. Bu sebepten dolayı tam kapsamlı arama yapmak bu problem için uygun değildir. Literatürdeki çoğu metod, bu problemi evrimsel metodlarla çözmeye çalışmaktadır. Bu tezde biz problemi çözebilmek için algoritmik bir metod üretmiş durumdayız. Bu metod, problemi çözmek için böl ve yönet yöntemini kullanmaktadır. Böylece, problem bir çok küçük probleminin birleşimine dönüştürülmektedir. Biz oluşan bu alt problemleri, ulaştırma problemlerine çeviren bir dizayn ürettik. Ortaya çıkartılan ulaştırma problemleri simplex algoritması ile çözülmektedir. Önerilen metod bir çok farklı metodla karşılaştırılmış olup hızlı, yeterince optimal ve güvenilir sonuçlar ortaya çıkarttığı görülmüştür.