2014 IEEE 22nd Signal Processing and Communications Applications Conference (SIU 2014)
3 BOYUTLU ARAZİ ÜZERİNDE ÇOKLU OTONOM İNSANSIZ HAVA ARACI ROTA
PLANLAMASI
AUTONOMOUS MULTI UNMANNED AERIAL VEHICLES PATH PLANNING ON
3 DIMENSIONAL TERRAIN
Nuri Ozalp1, Ozgur Koray Sahingoz2, Ugur Ayan1
1. Bilişim ve Bilgi Güvenliği İleri Teknolojiler
Araştırma Merkezi
TÜBİTAK
2. Bilgisayar Mühendisliği Bölümü
Hava Harp Okulu
34149, Yesilyurt/ISTANBUL
{nur.ozalp,[email protected]
[email protected]
rahatlıkla kullanılabilir. İnsan hayatını riske atan taarruz ve
hava savunma gibi durumlarda İHA’ların kullanılması başarılı
sonuçlar vermekte ve riski en aza indirgemektedir. Araştırma
ve geliştirmelerde daha hızlı ve daha ucuz çözüm alma adına
İHA’lar kullanılabilir. İHA’ların avantajları sıralandığında
daha az enerji sarfiyatı, gürültü düşüklüğü ve dışarıya
bıraktığı atık azlığı yönünden daha çevre dostu olması gibi
durumlar da göze çarpmaktadır. Aynı görevi kullanan
uçaklarla karşılaştırdığımızda bakım masrafı ve yakıt
tasarrufu bakımından da daha avantajlıdır. Hedef sayısının ve
İHA’ların artması bunları uzaktan kumanda edip yönetmenin
ortaya çıkarmış ve İHA’ların otonom çalışması önem
kazanmıştır. Günümüzde İHA’lar dinamik ortamlarda
kullanılmaktadır ve coğrafi şekiller, hava durumu, engeller ve
tehditler gibi birçok durum İHA’ların görevlerini yerine
getirmelerini etkilemektedir.
Otonomi aynı zamanda operatörün iş yükünü azaltır. Bu
yüzden bir operatör ile birden fazla İHA kontrol
edilebilmektedir. Otonomi ve görevlerin operasyonel
değişiklikleri ile yeni koşullara hızla uyum sağlanır. İHA’ların
askeri alandaki en büyük avantajı; dış dünyaya daha duyarlı
ve iletişimin her daim devam ettiği sistem geliştirmeyi
kolaylaştırmasıdır. Otonomi ile daha hızlı ve daha kolay bir
şekilde sürekli istihbarat toplanabilmekte ve insanın fiziki
kısıtlarından kurtulunmasına olanak sağlanmaktadır.
F. Schøler’e göre otonomiyi aşağıda listelenen 6 ana
başlık altında toplamak mümkündür [2]. Bunlar görev
dağılımı, engel tehditli, bölge tespiti, yol planlama,
çarpışmadan kaçınma, yörünge üretimi, araç kontrolüdür.
Çoklu otonom İHA’lar, birden çok İHA ile otonom bir
şekilde birçok görevi yerine getirebilen, homojen ve heterojen
yapılara sahip İHA toplulukladır. Çoklu otonom İHA’lara ait
birçok özellik vardır. Bunlar kendi rotasını çizebilen ve
kendisine atanan görevleri icra edebilen, çevre algılama ve
yörünge planlama yetilerinin yanında haberleşme ve
koordineli hareket edebilen, belirli bir görevi birbirlerinden
farklı menzil, irtifa, hız, manevra, yakıt kapasitesi, radar,
korunma ve saldırı özelliklerine sahip İHA’lara atayarak
başarıyla sonlandırabilen, dinamik etkenlere bağlı olarak anlık
karar verebilen, takımın çıkarına olacak şekilde ferdi görevler
üstlenebilen İHA’lardır.
Bu çalışmada paralel GA ile bilinmeyen engeller üzerinde
3 boyutlu rota planlaması üzerine durulmuş olup radar alanları
göz önünde bulundurularak adaptif evrimsel rota planlayıcısı
geliştirilmiştir. Radarlar çevrimiçi şekilde tespit edilmiştir.
Engele tam yaklaşınca engel etrafından dönme algoritmaları
ile takılmadan hedefe ulaşılması sağlanmaktadır. GA'da
kullanılan uygunluk fonksiyonunun değeri iki nokta
ÖZETÇE
Bu çalışmada otonomi konusunda öncelik arz eden tekli ve
çoklu İnsansız Hava Araçları(İHA) için tehditli ve engelli
ortamlarda güvenli rota planlama konusu üzerine
yoğunlaşılmıştır. Genetik Algoritma (GA) kullanılarak
İHA’lara ait kinematik kısıtları ve arazi şartlarını göz önünde
bulundurarak en uygun rotanın planlanması üzerinde
çalışılmıştır. Kullanılan arazi verileri NASA’ya ait gerçek 3
boyutlu uydu verilerinden oluşmaktadır. Bu sayede yükseklik
verisine erişim sağlanmış ve böylece arazi üzerindeki dağların
tespiti yapılmıştır. Gerçek coğrafik koordinat sistemi
kullanılarak ve dünyanın geometrik şekli göz önünde
bulundurularak yüksek hassasiyetli hesaplamalar yapılmıştır.
GA ile global rota planlaması yapılırken noktalar arasındaki
geçişlerde yerel rota planlaması üzerinde durulmuştur. Elde
edilen sonuçlara bakınca çoklu İHA kullanımının ilgili
görevlerin yerine getirilmesinde zaman ve performans
açısından büyük fayda sağladığı görülmektedir.
ABSTRACT
Leave Secure route planning in environments with obstacles
and threats, which is of first priority for single and multiUnmanned Aerial Vehicles (UAVs), is the main focus of this
study. Planning the optimum route by using genetic algorithms
by considering kinematic constraints and terrain conditions is
investigated. The terrain used in this study consists of real 3D
satellite data of NASA. Thus, access to altitude data is
achieved and mountains over the terrain are detected. Real
geographic coordinate system is used and the geometric shape
of the earth is considered for high precision calculations.
While global route planning is made by the GA, local route
planning is considered for transitions between waypoints.
According to experimental result, usage of multi-UAV brings a
great benefit in the fulfillment of the missions in terms of time
and performance.
1.
GİRİŞ
Son yıllarda İHA’lar üzerinde yapılan çalışmalar
göstermektedir ki; bu tür araçların farklı alanlarda kullanımı
ve bu alanda çalışan araştırmacı sayısı da gelecek yıllarda
artmaya devam edecek. Normal uçaklarda uzun keşif ve
gözetleme gerektiren işlerde insan zaafından kaynaklı bazı
sıkıntılar çıkma ihtimalinin yüksek olmasına karşın, İHA’lar
taşıdıkları kamera, duyarga ve radarlar yardımı ile daha
verimli ve etkin kullanılabilmektedir. Özellikle, tehlike arz
eden kimyasal ve nükleer vb.[1] riskli durumlarda İHA’lar
978-1-4799-4874-1/14/$31.00 ©2014 IEEE
228
2014 IEEE 22nd Signal Processing and Communications Applications Conference (SIU 2014)
arasındaki mesafeye, eğer arada radarlar da varsa radarları
geçmek için dönüş yaptığı toplam yol miktarına göre
hesaplanmaktadır [3].
2.
gerekmektedir. Şekil 2’de görüldüğü gibi çoklu kromozom
yapısında her bir kromozom bir İHA’yı temsil etmektedir. 4
İHA ile 15 adet kontrol noktası temsili olarak gösterilmiştir.
İLGİLİ ÇALIŞMALAR
İnsansız helikopterin binalar gibi engellerin yoğun olduğu
yerlerde uçuş hareket algoritmaları ile ilgili bir strateji de
Koyuncu ve İnalhan[4] tarafından geliştirilmiştir. Puanlama
tabanlı hareket algoritması dar geçitlerde dinamik kısıtlar göz
önünde bulundurularak birçok robotik problemlerde başarılı
sonuçlar vermiştir.
Bu çalışmada kino-dinamik hareket algoritması üzerinde
çalışılmış ve 2 aşamalı algoritma önerilmiştir. İlk aşamasında
Ağaç Tabanlı Planlayıcı (Rapidly-Exploring Random Trees)
(RRT)) algoritması kullanılarak yaklaşık çizgi segmenti
modeli çevreyi keşfeder. Sonuçta bulmuş olduğu noktaları
birleştirerek görüş alanındaki uçuş yolunu bulur. İkinci
aşamada ise çıkan noktalar B-Spline eğri algoritması ile
birleştirilir ve bu bulunan noktalar dinamik uçuş kriterlerini
de göz önüne alınarak olasılıksal olarak iyileştirilir [4].
Yol planlaması her zaman İHA için çok önemli bir konu
olmuştur. Birden fazla görevin yüklenmesi ile İHA’larda yol
planlaması önemli bir en iyileme problemi haline gelmiştir.
GA iyi bir olasılıksal arama yöntemi olarak bu tip
problemlerin çözümünde yaygın olarak kullanılır.
3.
Şekil 2: Çoklu kromozom yapısı
Genetik algoritmanın temel operatörleri şu şekilde
tasarlanmıştır.
3.2. Yer Değiştirme Operatörü
Yer değiştirme Şekil 3’te görüldüğü gibi klasik GA yer
değiştirme operatörüne benzer, fakat çoklu-kromozom
yapısından dolayı rastgele seçilen 2 kromozomun gene
rastgele seçilen bir veya birden çok kesim noktalarından
genlerinin karşılıklı yer değiştirmesi temeline dayanmaktadır.
Şekil 4’de yer değiştirme sonucu oluşan yeni kromozom
görülmektedir.
ALGORİTMA
Birden çok gezgin satıcı problemi (Multi Traveling Salesman
Problem (mTSP)) karmaşık bir problemdir. Gezgin satıcı
probleminin bir türevi niteliğindedir. Birden çok satıcının
başlangıç noktaları aynı olmak koşulu ile verilen noktaları en
uygun biçimde gezip başlangıç noktalarına dönmesi amaçlanır.
Çoklu İHA’larda genel olarak rota planlama probleminin
çözümü mTSP problemine dayanmaktadır. Kalkış noktaları
aynı olmak koşulu ile birden çok İHA’nın kısıtları göz önünde
bulundurularak otonom güzergâh planlaması mTSP
probleminin temelini oluşturmaktadır. Problemi mTSP’den
daha zor hale getiren 3 boyutlu olması ve noktalar arasında
statik ve dinamik engellerin bulunmasıdır. Bunun yanında
İHA’lara ait birçok kinematik kısıtın güzergâh planlamada
oldukça büyük öneme sahip olması, rota planlarken birçok
zorluk oluşturmaktadır. Bu nedenle performansı artırmak için
Şekil 1 de görüldüğü gibi paralel GA yapısı kullanılmıştır.
Şekil 3: Çoklu kromozomun yer değiştirme operatörü
uygulanacak noktalarının seçimi
Şekil 4: Yeni kromozom
3.3. Mutasyon Operatörü
Mutasyon sadece tek bir birey üzerinde yapılan işlem olarak
tanımlanmıştır. Şekil 4’de görüldüğü gibi mutasyonun temeli,
mTSP probleminde olduğu gibi, genlerin birbiri arasında
rastgele seçilen nokta veya noktalardan yer değiştirmesidir [5].
Şekil 1: Paralel GA akış diyagramı (n tane core için)
Şekil 4: Çoklu kromozom mutasyon işlemi
3.1. Kromozom Yapısı
3.4. Seçim Operatörü
Klasik GA’dan farkı artık tek bir parçalı kromozom yerine çok
parçalı kromozom yapısı kullanılmasıdır. Kromozomun
başlangıç noktasının kalkış-iniş pistinin noktalarını göstermesi
Bu çalışmamızda Ozalp’ın[6] önerdiği en iyi elitizm oranı
içerisinden rastgele ata seçimini tercih ettik. Bu sayede hem
229
2014 IEEE 22nd Signal Processing and Communications Applications Conference (SIU 2014)
eniyiler arasından seçimle çözüm kalitesi artırılmakta hem de
rasgeleliği kullanarak çeşitlilik sağlanmaktadır
3.5. Uygunluk Fonksiyonu
Klasik TSP probleminde uygunluk fonksiyonu tek bir
kromozom üzerindeki noktaların aralarındaki mesafelerin
toplamı şeklinde hesaplanmaktadır. mTSP probleminin
uygunluk fonksiyonu ise problemin içerdiği çoklu
kromozomların her birisinin uygunluk değerlerinin
bulunduktan
sonra
bu
değerlerin
toplanmasıyla
hesaplanmaktadır [5]. Üç boyutlu hesaplamalar daha önceki
çalışmamızda
coğrafik
sistemdeki
hesaplamalara
dayanmaktadır [7].
4.
Şekil 6: Dağların Tespiti
UYGULAMA
Dağların tespiti için kullanılan algoritma aşağıda anlatıldığı
gibidir:
1.adım: İki nokta arasındaki alanın taranması ile yükseklik
matrisini oluştur
2.adım: İki nokta arasındaki bütün yükselti verisi elde
edildikten sonra maksimum ve minimum yüksekliği hesapla
3.1. adım: Maximum yükseklik İHA’nın mevcut
yüksekliğinden düşük ise adım bitiş noktasına git.
3.2.adım: Maximum yükseklik ile başlangıç noktası
arasındaki eğim eğer maksimum yükseklik açısından düşük ise
maksimum bitiş noktasına gitmeden önce maksimum noktaya
git daha sonra bitiş noktasına git.
3.3 adım: Maximum yükseklik ile başlangıç noktası
arasındaki eğim eğer maksimum yükseklik açısından büyük ise
maksimum dönme yarıçapı ile etrafında yükselmeye başla.
3.3.1 adım: Öncelikle kaç tur dönmesi gerektiğini hesapla.
3.3.2 adım: Atılması gereken tur atıldıktan sonra adım 3.1
ve adım 3.2 durumlarını kontrol et.
İHA’ların güzergâhları üzerinde daha önceden bilinmeyen
ve uçuş anında karşılaşılan engellere dinamik engeller denir.
Bunlar radar, füze, başka bir İHA veya savaş uçağı olabilir.
Bu uygulamada dinamik engel olarak radar kullanılmıştır.
Daha önceki çalışmada radar tespit algoritması detaylıca
anlatılmıştır [7].
4.1. Kısıtlar
İHA’ların güzergâh planlaması yapılırken birçok kısıt söz
konusudur. Bu kısıtlar, maksimum hız, yakıt miktarı,
dolaşılacak toplam maksimum ve minimum mesafe, gezilecek
nokta sayısı, uçuş sırasındaki maksimum ve minimum yerden
yükseklik, havada kalma süresi, maksimum ve minimum
yükselme, alçalma ve dönme açıları, maksimum haberleşme
mesafesi gibidir. GA uygunluk fonksiyonu hesaplanırken
uygulamamızda kullanılan İHA’lara ait temel alınan 10 adet
kısıt Tablo 1’de belirtilmiştir.
Tablo 1: Kısıtlar
Kısıtlar
Maksimum dönüş yarıçapı
Maksimum dolaşılacak nokta
sayısı,
Minimum dolaşılacak nokta
sayısı,
Maksimum dolaşılacak
mesafe
Minimum dolaşılacak mesafe
Maksimum Yerden yükseklik
Başlangıç yerden yükseklik
Minimum Yerden yükseklik
Maksimum yükseliş açısı
Maksimum dönüş açısı
Değerleri
500m,
Kullanıcı girişi ile belirlenir
Kullanıcı girişi ile belirlenir
20000m,
5000m,
2500m,
1500m,
300m,
45o
40o
4.4. GA’ya Ait Uygunluk Fonksiyonunun Hesaplanması
GA’ya ait uygunluk fonksiyonu hesaplanırken noktalar
arasındaki toplam mesafeler bulunur. Toplam mesafe
Denklem 1’deki gibi hesaplanmaktadır.
t
n
M   L  M  R  D
4.2. Engeller
(1)
a 0 k 0
İHA’ların uçuş güzergâhlarında karşılaşabileceği bir takım
statik engeller vardır. Bunlar dağlar, yüksek binalar olabilir.
Bu engellere statik engel denmesinin sebebi sabit olmaları ve
yerlerinin önceden bilinmesidir. Geliştirilen uygulama
WorldWind altyapısını kullanmaktadır. Şekil 6’da görüldüğü
gibi, bu çalışmada NASA tarafından sağlanan çevrimiçi uydu
görüntüleri ile gerçek arazi verisi ve gerçek koordinat verileri
kullanılmıştır. Yükseklik verisi kullanılarak dağlar tespit
edilmiştir.
Tablo 2: Uygunluk fonksiyonuna ait terimler
Parametreler
Toplam maliyet
Radar geçiş maliyeti
Dağ geçiş maliyeti
İki nokta arasındaki mesafe
Her bir kromozoma ait
toplam kontrol noktası sayısı
Toplam İHA sayısı
4.3. Tehditler
Özellikle harekat ortamında İHA’ların varlığı tehdit eden
temel etkenler radarlar ve uçaksavarlardır. Bu birimler
kapsama alanı ve sahip oldukları radarlar çerçevesinde tehdit
oluşturmaktadır ve güzergah planlaması sırasında bunlarda bir
engel
hükmünde
değerlendirilerek
rota
planlaması
gerekmektedir.
Kısaltmalar
M
R
D
L
n
t
Bu şekilde en az maliyeti olan kromozom seçilir ve ekrana
çizdirilir. Şekil 7’de 3 İHA’nın 250 kontrol noktasını
gezinmesi gösterilmektedir. İlgili örnekte, her bir İHA’nın
minimum gezineceği nokta sayısı 75 olarak ayarlanmıştır.
230
2014 IEEE 22nd Signal Processing and Communications Applications Conference (SIU 2014)
Şekil 11: Görev süresinin nokta sayısına göre değişimi
5.
Şekil 7: 3 İHA’nın için örnek rota planlaması
SONUÇLAR
Bu çalışma ile çoklu otonom İHA’ların kullanımına ait
avantajların sayısal verilere dayanarak gösterimi yapılmıştır.
Bir İHA yerine birden çok İHA kullanımı, daha fazla araziyi
daha sık kontrol etmeyi sağlamıştır. Bir İHA’nın verilen
görevi yerine getirmesi için geçen süre ve maliyetin birden
çok İHA ile görevi yerine getirmeye göre daha fazla olduğu
ispatlanmıştır. Bu sayede silahlı kuvvetlerin pilot ihtiyacından
ve yetişmiş eleman ihtiyacından tasarruf edilmiş olacaktır.
Tek bir büyük İHA yerin birlikte çalışan birden fazla İHA’nın
kullanılması maliyet etkin bir çözüm olarak göze
çarpmaktadır. Bu çalışmanın devamında etmen sistemleri
kullanılarak gerçek zamanlı rota planlaması daha çok kısıt
kullanılarak yapılması hedeflenmektedir. Dağların aralarından
geçişleri sağlamak ve engelleri tespit etmek için daha geniş
bir arazinin taranması gerekmektedir. Engellere çarpmadan
hareket planı ve iki nokta arasındaki hareket algoritmaları BSpline veya Bezier gibi eğriler kullanılarak yapılması
planlanmaktadır.
4.5. Simülasyon Test Sonuçları,
Aşağıdaki grafiklerde Çoklu İHA’lara ait test sonuçları yer
almaktadır.1, 2, 3 ve 4 adet İHA için testler yapılmıştır. Her
bir test 10 kez çalıştırılmış ve sonuçlar bu testlerin
ortalamaları alınarak bulunmuştur. İlgili test sonuçları Şekil 811 arasında gösterilmiştir.
6.
Şekil 8: İterasyon sayısının nokta sayısına göre değişimi
KAYNAKÇA
[1] SSM 2011-2030 Türkiye İHA Yol Haritası,
http://www.ssm.gov.tr/_layouts/images/İHA_ekatalog_w
eb/index.html (21.01.2014)
[2] Schøler, F., “3D Path Planning for Autonomous Aerial
Vehicles in Constrained Spaces”, Ph.D. Thesis, Aalborg
University, 2012.
[3] Ozalp N. and Sahingoz O.K., “Optimal UAV path
planning in a 3D threat environment by using parallel
evolutionary algorithms,” International Conference on
Unmanned Aircraft Systems (ICUAS), pp. 308–317, 2013.
[4] Koyuncu, E., Ure, N. K ve Inalhan, G., “Integration of
Path/Maneuver Planning in Complex Environments for
Agile Maneuvering UCAVs.”, J Intell Robot Syst, vol.57,
Issue, 1-4, Sf.143-170, 2009.
[5] Király, A. ve Abonyi, J., “Optimization of Multiple
Traveling Salesmen Problem by a Novel Representation
based Genetic Algorithm”, Intelligent Computational
Optimization in Engineering Studies in Computational
Intelligence, Vol.366, Sf. 241-269, 2011.
[6] Ozalp N., 3 Boyutlu Arazi Üzerinde Çoklu Otonom
İnsansız Hava Aracı Rota Planlaması, Yüksek Lisans
Tezi, Hava Harp Okulu, 2013.
[7] Ozalp, N., Sahingoz, O.K., Ayan, U., “Autonomous
unmanned aerial vehicle route planning,” in Proc. of
IEEE 21st Signal Processing and Communications
Applications Conference (SIU), 2013.
Şekil 9: Çalışma süresinin nokta sayısına göre değişimi
Şekil 10: Toplam mesafenin nokta sayısına göre artışı
231
Download

Autonomous multi unmanned aerial vehicles path planning on 3