Interactive approaches for bi-objective UAV route planning in continuous space

Abstract

Bu tezde, İnsansız Hava Aracı (UAV) rota planlama problemlerini ele alıyoruz. İlgili faktörlerin çoğunu kapsamalarından dolayı toplam mesafeyi en aza indirmeyi ve toplam radara algılanma tehdidini en aza indirmeyi amaçlarımız olarak belirledik. Rotalamayı iki boyutlu sürekli hareket alanında yapıyoruz,dolayısıyla, hedefler arasında sonsuz sayıda etkin güzargah bulunduğunu biliyoruz. İki temel tercih fonksiyonu (doğrusal ve konveks benzeri) için rota planlayıcısı'nın (RP) en çok tercih ettiği çözümü bulan etkileşimli algoritmalar geliştirdik. Rota planlama problemine algoritmaları uygulayabilmek için hedefler arasındaki etkin yolları tahmin eden yöntemleri kullandık. Doğrusal durumda desteklenen çözümler bulmak için, rota planlama problemini iki kısımda çözdük. İlk kısımda her hedef ikilisi arasında en iyi yolu bulduk. İkinci kısımda tüm hedefleri gezen turu bulduk (gezgin satıcı problemi). Konveks benzeri fonksiyonlar için geliştirilen algoritmada hem desteklenen hem desteklenmeyen etkin çözümleri arıyoruz. Öncelikle RP'nin en çok tercih ettiği çözümü içinde bulunduran dikdörtgen alanlar elde ediyoruz. Sonrasında bu bölgelerin içinde yeni çözüm (desteklenen/desteklenmeyen) arıyoruz. Algoritmalara RP'nin iki alternatif arasındaki tercihi ile ilerliyoruz ve karşılaştırılacak çözümler yeterince yakın olunca algoritmaları durduruyoruz. Rastgele problemler oluşturmak için, belli bir alana radarlar yerleştiren bir model geliştirdik. Çalışmanın sonunda, doğrusal fonksiyonlar için geliştirdiğimiz algoritmayı rastgele oluşturulmuş iki problem üzerinde gösteriyoruz.

We study the route planning problem of unmanned air vehicles (UAVs). We consider two objectives; minimizing total distance traveled and minimizing total radar detection threat since these objectives cover most of the other related factors. We consider routing in a two-dimensional continuous terrain, in which we have infinitely many efficient trajectories between target pairs. We develop interactive algorithms that find the most preferred solution of a route planner (RP), who has either of the underlying preference function structures: linear or quasiconvex. To implement the algorithms to route planning problems, we use approximated nondominated frontiers of the trajectories between targets. In the linear case, we search for supported efficient solutions in two stages. In the first stage, we find the best trajectory between each target pair. In the second stage, we find the tour visiting all targets (traveling salesperson problem, TSP). In the quasiconvex case, we search for both supported and unsupported efficient solutions. We first reduce the objective space to rectangular regions around at most three supported efficient solutions. We then search inside these rectangular regions to find supported/unsupported efficient solutions and narrow our search region. We proceed with pairwise comparisons from the RP and reduce our search space until the two solutions to be compared are close enough. To generate random problem instances, we develop a mathematical model that randomly locates radars in a terrain with known target locations. We then demonstrate the interactive algorithm developed for linear preference functions on two randomly generated problems.