Savunma Bilimleri Dergisi, Mayıs 2012, 11 (1), 119-132. 119 Gerçek Zaman Kısıtları Altında Seyrüsefer Planlamaya Yeni Bir Yaklaşım Ferhat Uçan1 D. Turgay Altılar 2 Öz Gerçek zaman kısıtları altında seyrüsefer planlama, değişken ortam koşullarında hava aracı için minimum yakıtla en güvenilir, en kısa yoldan intikali tamamlayabilmesi için gerekli çözümün bulunmasını gerektirir. Enlem, boylam koordinatları ve yükseklik değerleri ile tanımlanan uçuş noktalarının bazıları arasında geçiş yolları bulunmaktadır. Bu yol parçalarının uzunluk, güvenlik, yükseklik gibi rastlantısal olarak değişebilen kısıtları mevcuttur. Problemin en uygun çözümü, tüm amaç fonksiyonlarını birlikte eniyileyen çözümdür. Böyle bir çözüme ulaşmak çoğunlukla zordur. Çünkü genellikle göz önüne alınan kısıtlar birbiriyle çelişkili ve negatif yönde etkileşimlidir. Problem uzunluk, yükseklik ve güvenlik koşullarını kısıt olarak değerlendirildiğinden çok amaçlı eniyileme problemidir. Gerçekleştirilen sistem uçuş planı tasarlama ve yürütme olmak üzere iki alt sistemden oluşmaktadır. Uçuş planı tasarlama alt sisteminde, hava araçlarının, bir intikal başlangıç noktasından hedef noktasına en güvenilir, en kısa, en düz yoldan intikali evrimsel yöntemle, genetik algoritma ile planlanmıştır. Uçuş planı yürütme alt sistemi sağladığı yatay ve dikey seyrüsefer güdüm fonksiyonlarıyla tüm uçuş bacakları için, istenilen kalkış noktasından bir sonraki varış noktasına planlanan intikali gerçekleştirir. Problem çözümünde tasarlanan alt sistemler üç boyutlu çizge yapısını kullanmaktadır. Anahtar Kelimeler: Seyrüsefer Planlama, Uçuş Planı Simülasyonu, Çok Amaçlı Eniyileme, Karar Destek Amaçlı Modsim A New Approach to Navigation Planning Under Real Time Constraints Abstract Navigation planning under real time constraints requires finding the necessary solution for the transition of the air vehicle from the most secure, shortest path with minimum fuel consumption under changing environment conditions. There are transition paths between some of the waypoints that are defined by latitude, longitude and altitude values. There are constraints of the transition paths like distance, security and altitude that can change casually. The optimum solution of the problem is the solution which optimizes all objective functions. Finding such a solution is usually difficult because usually constraints that are considered in the problem are contradictory and interact negatively with each other. Since the problem considers distance, altitude and security conditions as distinct constraints, it is a multi-objective optimization problem. The system consists of two subsystems, one of these subsystems is flight planning subsystem and the other one is flight plan execution subsystem. In the flight planning subsystem, the most secure, shortest and smoothest flight path transition of the 1 Yazışma adresi: Yüksek Mühendis, TÜBİTAK Bilgem, Bilişim Teknolojileri Enstitüsü, Gebze, Kocaeli, [email protected] 2 Yrd.Doç.Dr., İstanbul Teknik Üniversitesi, Bilgisayar Mühendisliği Bölümü, Maslak, İstanbul. Makalenin geliş tarihi: 09.09.2011 Kabul tarihi: 29.12.2011 120 UÇAN–ALTILAR air vehicles from the source waypoint to the target waypoint is planned by evolutionary method and genetic algorithm. Flight plan execution subsystem executes the planned flight path from the desired departure waypoint to the next arrival waypoint owing to the lateral and vertical navigation guidance functions. The two subsystems developed uses 3-D graphs for the solution. Keywords: Navigation Planning, Flight Plan Simulation, Multi Objective Optimization, Decision Support Motivated Modsim Giriş İntikal problemi çok genel bir problemdir. Trafikte araç rotalamada, askerî uygulamalarda, robotik uygulamalarda, şehir ulaşımında bir yerden bir yere hangi hat üzerinden gidileceğini belirlemede, ağ üzerinde veri paketlerini yönlendirmede kullanılabilir. Bu çalışmada hava araçları için seyrüsefer planlama çalışması yapıldığı için bir uçuş sisteminde kullanılması olası koşullar ve amaçlar düşünülerek çözüm geliştirilmiştir. Yapılan çalışmalar incelendiğinde standart yol bulma problemi için geliştirilen Dijkstra, Floyd algoritmaları, Neural Network çözümü gibi yöntemlerin problemin kısıtları gerçek zamanlı olduğunda düzgün sonuç vermediği görülmüştür. Evrimsel yöntemler ise uygunluk fonksiyonu sayesinde sadece yolun uzunluğuna değil, güvenliğine ve yoğunluğuna da bakabilmekte, dinamik değişen ortam şartları için problemin çözümüne uygun bir yaklaşım sunabilmektedir (Hocaoglu ve Sanderson, 1996). Dinamik intikal planlama probleminin, çok iyi bilinen üç çözümü; Franciosa, Ramalingam Reps ve Frigioni çözümleridir. Franciosa tarafından geliştirilen çözüm kullanılamaz hâle gelen bir düğümün daha sonra sisteme tekrar eklenebilme durumunu gözetmemiştir (Franciosa, Frigioni ve Giaccio, 1997). Ramalingam Reps yöntemi ortalama çalışma zamanı açısından iyi performans vermektedir (Ramalingam ve Reps, 1996). Frigioni yöntemi ise en kötü durumdaki çalışma zamanı açısından üstündür (Frigioni, Marchetti ve Nanni, 2000). Fakat bu algoritmalar aşağıdaki durumlar göz önüne alındığında bazı kısıtlara sahiptir: Mevcut dinamik yol bulma algoritmaları, topolojideki eş zamanlı değişimlere duyarlı değildir, yani herhangi bir anda sadece tek bir değişim olan durumlarda başarılı olarak çalışmaktadır, fakat çevrede eş zamanlı birçok değişim olduğunda bu algoritmalar çözüm üretememektedir. Kenar ağırlıklarının istatistiksel olarak ve sürekli değiştiği senaryolar için mevcut algoritmaların başarımı iyi değildir. Savunma Bilimleri Dergisi, Mayıs 2012, 11 (1), 119-132. 121 Büyük topolojilerde ve düğüm ve bağlantı sayılarının çok olduğu ağlarda eş zamanlı olarak birçok değişikliğin olduğu durumlarda zaman kısıtı da var ise mevcut algoritmaların kullanımı pek uygun değildir. Bu ve benzeri senaryolar dinamik algoritmaların koşmasını gerektiren ortamlar olduğundan mevcut çözümler sınırlı olarak kullanılabilir. Dinamik eniyileme probleminin verileri ve girdileri zamanla değiştiğinden, her seferinde yeni bir matris ile çözüme baştan başlamak yerine, bu çalışmada olduğu gibi, sezgisel algoritmanın üretim döngüsü ve amaç fonksiyonu kullanılarak bir önceki nesildeki çözüme yakın bireylerin seçimiyle daha iyi çözümler üretilebilir. Bilgisayar dünyasında çözümsüz veya NP karmaşık olarak nitelendirilen bazı gerçek hayat problemlerine son yıllarda evrimsel eniyileme sınıfındaki yöntemlerle çözümler getirilmeye çalışılmaktadır (Uğur, 2008). Çizge Kuramı Çizge Teorisi, bir olay ve ifadenin düğüm ve çizgiler kullanılarak gösterilmesi biçimidir. Çizgeler birçok bilgisayar uygulama alanında ve uygulama modellerinde sık sık kullanılmaktadır. Günümüzde birçok örnek çizgelere benzetilebilir. Mesela şehirlerarası uçak seferleri veya internetteki bilgisayarların birbirine bağlanması çizge yapısı temel alınarak örneklenebilir. Bağlantı noktaları bulunan ve aralarında yol bağlamında birşey bulunan her tür uygulama çizge yapısına yaklaştırılabilir. Birçok problem çizge veri modeli şeklinde modellendiğinde karmaşık bir hâlden daha anlaşılır hâle gelmektedir. Çizge yapısı, düğümler ve kenarlar kümesinden oluşur. Düğümler kenarların kesişme noktasıdır ve kenarlar da bu düğümleri birbirine bağlar. Uçuş planı tasarlama alt sisteminde Şekil 1’deki gibi bir şehir haritasında hava araçlarının, bir intikal başlangıç noktasından hedef noktasına en güvenilir, en kısa, en düz yoldan intikali geliştirilen yöntemle planlanmıştır. Şehir haritasında şehirlerarası her bağlantı uzunluk, güvenlik, yükseklik olmak üzere üç değerden oluşan bir vektörle temsil edilmektedir. Uçuş planlaması yapıldığı için, şehirlerarası yolun yüksekliği de dikkate alınmakta ve üç boyutlu çizge ile çözüm yapılmaktadır. Uçuş planı yürütme alt sisteminde kullanılan çizge uçuş noktalarının enlem, boylam ve yükseklikleri ile oluşturulur. 122 UÇAN–ALTILAR Şekil 1. Uçuş Planı Tasarlama Alt Sistemi Çizge Yapısı Şekil 2. Dinamik İntikal Çözümü Sistem Şekil 1’de gösterilen başlangıç durumunda çözüm üretirken, dinamik olarak Şehir 1 – Şehir 3, Şehir 8 – Şehir 9 ve Şehir 8 – Şehir 11 arasındaki bağlantılar koptuğunda algoritmanın önerdiği yeni intikal planı Şekil 2’de gösterildiği gibidir. Algoritma hem güvenlik, hem uzunluk, hem de uçuş yüksekliği koşullarını dikkate almakta ve en güvenilir, en kısa, en düz uçuşu planlamaktadır. Savunma Bilimleri Dergisi, Mayıs 2012, 11 (1), 119-132. 123 Evrimsel Uçuş Planlama Alt Sistemi Uçuş planı tasarlama evresinde başlangıçta uçuş noktalarının enlem, boylam ve yükseklik değerleri ve üç boyutlu çizge yapısındaki rota parçası vektörü okunmaktadır. Daha sonra uçuş noktalarının enlem ve boylam bilgilerinden yararlanarak, arasında yol tanımlı olan noktalar için mesafe hesabı yapılmaktadır. Çok kısıtlı eniyileme problemi için kısıtlar [uzunluk, güvenlik, yükseklik farkı] şeklinde üçlü bir vektör olarak düşünülebilir. Tüm uçuş planı için uzunluğu d(x), güvenliği s(x), yükseklik farkı f(x) olarak düşünülürse eniyileme fonksiyonunun kısıtları şunlardır; min∑d(x), max∑s(x),min ∑ │f(x)│; {d:Z R+,s:Z  [0..100], f : Z  R} Her x için; d (x) > 0, 0 < s(x) < 100, f(x) > 0 Hava aracı için bulunan uçuş planını gerçekleştirmek için gereken yakıt miktarını gösteren fonksiyon y (x) ve yakıt tankında ölçülen yakıt miktarı Y ise, y (x) < Y şartı sağlanmalıdır. Eğer bu şart sağlanmıyorsa alternatif uçuş planları araştırılır. Eğer yakıt tankındaki yakıt miktarı istenen kalkış noktasından varış noktasına gidiş için hiçbir şekilde yeterli değilse mevcut yakıtla gidilebilecek en yakın uçuş noktasına intikal için gerekli planlama yapılır. S70-A Sikorsky atak helikopterine ilişkin gerçek uçuş verileri ve ortam koşulları kullanılarak alınan veri kümesine göre regresyon analizi yapılmış ve uygun yakıt akış hızı denklemi bulunmuştur. Yakıt akış hızı tahmini için regresyon yöntemiyle bulunan formüller şu şekildedir; Sıcaklık <= 0 durumu için: Yakıt akış hızı = - 66.7 + 0.5817 *(Sıcaklık) - 0.9395 * Yükseklik + (1) 17.3483 * Havahızı + 5.8181* Ağırlık Sıcaklık > 0 durumu için: Yakıt akış hızı = - 147.77 + 0.4257 *(Sıcaklık) - 0.7765 * Yükseklik + (2) 13.651 * Havahızı + 6.9755* Ağırlık Geliştirilen regresyon analizi ile hesaplanan tahmini yakıt akış hızı bilgisi ile uçuş planlama alt sistemi tarafından bulunan en iyi uçuş planındaki toplam uçuş menzilinin tamamlanıp tamamlanamayacağı bulunur. S70-A Sikorsky helikopterinin ortalama uçuş hızı pilot tarafından ayarlanabilir durumdadır. Varsayılan ortalama uçuş hızı 150 deniz mili / saat, yani yaklaşık 277 km/saat olarak alınmıştır, bu değer güncellendiğinde algoritma yakıt akış hızına göre görevin tamamlanabilme durumunu güncel yakıt akış hızı değerine göre hesaplamaktadır. Regresyon ile bulunan yakıt 124 UÇAN–ALTILAR akış hızı ile ortalama hız değeri çarpılarak mevcut yakıtla gidilebilecek menzil değeri hesaplanır. Eğer uçuş planı alt sisteminin çok kısıtlı eniyileme ile ürettiği uçuş planının gerektirdiği toplam uçuş menzili mevcut yakıtla gidilebilecek uçuş menzilinden daha büyük ise alternatif uçuş planı bulunur. Eğer hiçbir şekilde mevcut yakıtla tamamlanacak bir uçuş planı bulunamıyorsa en güvenilir, en kısa, en düz uçuş rotasında hava aracının gidebileceği uçuş noktasına kadar gidebilmesi için gerekli uçuş planı üretilir ve uçuş planı çalıştırma alt sitemine girdi olarak verilir. Şekil 3’de Sikorsky S-70A helikopteri için sıcaklık, yükseklik, hız ve ağırlık kısıtlarına göre değişen gerçek yakıt akış hızı değerleri ve regresyonla tahmini olarak hesaplanan yakıt akış hızı değerleri ve regresyon analizinin hata yüzdesi gösterilmiştir. Gerçek yakıt akış hızı verileri Sikorsky S70-A helikopteri teknik el kitabından alınmıştır (TM 1-70-28D-10, 2002). Şekil 3. Sikorsky S-70A Helikopteri Yakıt Akış Hızı Bilgileri Uçuş planlama alt sistemindeki işlem akışı Şekil 4’deki kod bloğunda gösterilmiştir. Bireylerin kromozomlarla temsili gerçekleştirildikten sonra başlangıç nüfusu oluşturulur. Dinamik ortam şartlarının güncel hâli alınarak tasarlanan uygunluk fonksiyonu ile başlangıç nüfustaki bireyler değerlendirilir. Bireyler ebeveyn seçimi aşamasında çiftlere ayrılır ve her bir ikili için çaprazlama yapılır. Çaprazlama aşaması Savunma Bilimleri Dergisi, Mayıs 2012, 11 (1), 119-132. 125 sonrası çevrim içeren yollardaki çevrimler temizlenir. Bazı bireyler için mutasyon yapılarak çeşitlilik sağlanır. Mutasyon sonucu, ebeveyn ve çocuk kromozomlar tekrar uygunluk fonksiyonu ile değerlendirilir, uygunluk değeri yüksek olan bireyler yaşatılır, diğerleri öldürülür. Bu çevrim birey benzerliği ölçütü sağlanıncaya kadar sürdürülür (Harik, Cantu-Paz ve Goldberg, 1999). Şekil 4. Uçuş Planlama Alt Sistemi Evrimsel Algoritma Akışı Evrimsel algoritmanın seyrüsefer planlama amacıyla kullanılmasında, her birey başlangıç noktasından bitiş noktasına olan bir rotayı göstermektedir ve kromozom ile kodlanarak gösterilir. Geliştirilen sezgisel yöntemde yolların temsili için değişken uzunluklu kromozomlar kullanılmıştır. Kromozomun ilk geni başlangıç noktası, son geni de bitiş noktasını göstermektedir. Kromozomlar permutasyon kodlama ile kodlanırlar. Her kromozom, rotada üzerinden geçilen düğümlerin numaralarından oluşan bir tamsayı dizisi şeklindedir. Uçuş planlama sisteminde ilk nüfus, rastlantısal olarak oluşturulur. Nüfustaki birey sayısı nesiller boyunca sabit kalan ve genetik algoritmanın çalışmasına etki eden önemli bir faktördür. İlk nüfustaki bireyler rastlantısal olarak üretildiğinden dolayı, herhangi bir veya birden fazla düğüm üzerinde çevrimler oluşabilir. Kullanılan genetik algoritma yaklaşımında bireylerde oluşan çevrimler 126 UÇAN–ALTILAR temizlenmektedir, çünkü bu çevrimler oluştuğu anda kaldırılmazlarsa, çaprazlama sonucu bozuk bireylerin oluşmasına neden olabilirler (Ahn ve Ramakhrisna, 2002). Bireylerin, yani çözüm adaylarının kalitesi ve sonuca yakınlığı uygunluk fonksiyonu ile belirlenir. Tüm objektifleri bağlamak amacıyla genel bir uygunluk fonksiyonu tasarlanmıştır. Evrimsel yöntemin bireyleri değerlendirmek için kullandığı amaç fonksiyonu aşağıdaki gibidir: segmansayısı 1 / uzunluk 1 / 100 güvenlik 1 / yükseklik farkı (3) i 1 Bireye ait kromozomun uygunluk değeri, rotayı oluşturan her bağlantının uzunluk, güvenlik ve önceki bağlantıya göre yükseklik farkı değerleri kullanılarak bulunur ve bu değer rotayı oluşturan bağlantı sayısına bölünür. İlk bağlantı için yükseklik farkı dikkate alınmaz. Kromozomlar uygunluk değerlerine göre azalan sıra ile sıralanırlar. Toplumun toplam kalitesini arttırmak için uygunluk değeri yüksek kromozomların bir sonraki neslin gen havuzuna alınma şansını yükselten bir seçim operatörü kullanılır. Seçim operatörü sonucun araştırılmasını, çözüm uzayının belirli bölgelerinde yoğunlaştırır. Önerilen algoritmada, sonraki nesil için, en iyi kromozomların korunması ve örneklemeden kaynaklanacak istatistiksel hataların önlenmesi amacıyla rulet tekeri isimli seçim tekniği kullanılmıştır. Rulet tekeri tekniğine göre topluluktaki tüm bireylerin uygunluk değerleri toplanır. Bir bireyin seçilme olasılığı, uygunluk değerinin bu toplam değere oranı kadardır. Çaprazlama aşamasında, çaprazlama bölgesinden sonraki genler, ebeveyn kromozomlar arasında takas edilir. Çaprazlama noktaları iki kromozdaki genlerin aynı olduğu noktadır. Geliştirilen algoritmada iki kromozom ancak ortak gene sahipse çaprazlanabilir. Çaprazlama işlemi sonucu tekrarlı genler içeren çevrimler oluşabilir. Algoritma bir art-işlem gerçekleştirerek oluşan çevrimleri temizler ve kromozomu kısaltır. Mutasyon toplumdaki genetik çeşitliliği arttırır ve aday kromozomun genlerini değiştirerek bölgesel en iyi çözümlere takılma durumunu engeller. En kısa yol probleminde bir kromozomun herhangi bir geni değiştiğinde kromozom geçerliliğini yitirebilir. Bu nedenle tek bir gen değişimi için bir dizi gen değiştirilerek kromozomun uygunluğu korunur. Seçilen iki nokta arası alternatif bir rota ile kromozom genetik değişime uğratılır. Örnek bir çaprazlama işlemi Şekil 5’te, örnek bir mutasyon işlemi de Şekil 6’da gösterilmiştir (Ahn ve Ramakhrisna, 2002). Savunma Bilimleri Dergisi, Mayıs 2012, 11 (1), 119-132. 127 Şekil 5. Çaprazlama operatörü Şekil 6. Mutasyon operatörü Evrimsel algoritmanın en önemli üç parametresi çaprazlama oranı, mutasyon oranı ve toplumdaki birey sayısıdır. Çaprazlama ve mutasyon oranının belirlenmesi için farklı değerlerle denemeler yapılarak en uygun değerler bulunmuştur. Çaprazlama oranı için denemeler sonucu en uygun değer %80, mutasyon oranı için en uygun değer %1 olarak belirlenmiştir. Kromozom sayısı ise çizgenin karmaşıklığına göre belirlenmektedir. Geliştirilen evrimsel algoritmada, nesiller ilerledikçe uygunluk değeri daha yüksek, çözüme daha yakın bireyler popülâsyonda yayılır. 50 uçuş noktalı, 250 bağlantı içeren bir çizge için nesiller boyu hata oranının nasıl azaldığı Şekil 7’deki grafikte gösterilmiştir. X ekseni nesil sayısını, Y ekseni de nesil içindeki uygunluk değeri en yüksek olan bireyin sonuca uzaklığını gösteren hata yüzdesi değeridir. Bu örnek denemede nüfustaki birey sayısı N = 20 olarak seçilmiştir. 128 UÇAN–ALTILAR 25 20 is e d 15 z ü Y a 10 t a H 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Nesil Sayısı Şekil 7. Genetik Algoritma Hata Oranı ile Nesil Sayısı İlişkisi Uçuş Planı Yürütme Alt Sistemi Hava aracının rotasında, istenilen uçuş rotasına göre herhangi bir sapma olduğunda, sapmayla orantılı, hava aracını yeniden o rotaya sokacak yalpa komutu hesaplanır. Ayrıca hava aracının rota değiştirmesi gereken zamanlarda da, bir sonraki rotaya oturmasını sağlayacak yalpa komutunun hesaplanması gerekmektedir. Hava aracını istenilen rotaya oturtmada kullanılan yatay ve dikey güdümleme algoritmaları kod blokları Şekil 8’de görüldüğü gibidir.