Data-driven delay estimation and anomaly detection: A study on European and Turkish air traffic
Veri güdümlü gecikme tahmini ve anomali tespiti: Avrupa ve Türkiye hava trafiği üzerine bir çalışma
Yazar: MUHAMMET AKSOY
Danışman: DR. EMRE KOYUNCU
İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Uçak ve Uzay Mühendisliği Ana Bilim Dalı / Uçak ve Uzay Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Havacılık Mühendisliği = Aeronautical Engineering

Özet:
Hava trafiği ağları oldukça karmaşık ve birbirine bağlı fiziksel sistemleri temsil eden ağlardır. Diğer ulaşım ağlarının aksine, hava trafiği çok sıkı bir şekilde regüle edilir ve fiziksel olarak daha fazla kısıtlamaya sahiptir. Uçuş yolları (airway) ve hava sahaları, karayolu taşımacılığı sistemlerine kıyasla daha fazla esneklik getirse de, uçakların yalnızca havaalanlarında konumlanabilmesi ve yalnızca buralarda uçuş operasyonlarına katılabilmesi aslında fiziksel olarak çok limitli bir ağ oluşmasına neden olur. Hava trafiği, güvenliği sağlamak ve güvenlik sağlanırken de seyahat hacmini mümkün olan en üst düzeyde tutma amacıyla regüle edilir. Bu düzenlemeler hava seyahatinin güvenli ve sistematik bir şekilde yapılmasını sağlarken, hava trafik ağında oluşan herhangi bir bozuntuyu engellemede bu düzenlemelerin pek de etkili olduğu söylenemez. Bu sebeple hava trafiğinde hava muhalefeti, kapasite sınırları gibi gecikmelere sebep olan bozuntular oldukça büyük çaplı tıkanmalara ve aksamalara sebep olabilir. Hava trafik ağlarındaki bu bozuntu ve aksaklıkların nedenleri arasında hava koşulları, kazalar, kapasite kısıtlamaları, personel grevleri vb. faktörler yer alır. Ancak, olumsuz etkilerin ortaya çıkardığı sonuç çoğunlukla aynıdır: uçakların kalkış veya inişlerinde gecikmelere sebep olurlar. Hava trafiğinin ve havaalanlarının birbirine çok yakından bağlı doğası nedeniyle, bir yerde gecikmeye sebep olan bir olay meydana geldiğinde, ağın diğer noktalarındaki üyeler, yani başka havalimanları, bu gecikmeyi aynı şekilde hatta daha büyük ölçüde hissedebilir. Bu olaylar sebebiyle, meydana gelen gecikme bir dalga gibi ağda yayılıp, ek olarak kartopu etkisiyle de ilk oluştuğu ana kıyasla çok daha fazla büyüyebilir. Hava trafiğini düzenleyen kuruluşlar, bu tip gecikme oluşturan olayların etkilerini hafifletmek için olaylar meydana geldikten sonra bazı düzeltici aksiyonlar alırlar. Örneğin belirli havaalanlarının veya hava yollarının kapasitesini azaltmayı, NOTAM'lar vermeyi, uçakları yerde veya havada bekletmeyi (holding patterns) içerebilir. Tüm bu işlemler "tepkisel" olduğu için, gecikme yaratan olaylar meydana geldikten sonra işleme koyulurlar, çünkü bu geniş ve kompleks sistemde gecikmelerin ağ içerisinde nasıl yayılabileceğini isabetli şekilde hesaplamak matematiksel ve işlem yükü açısından maliyetli bir hesap gerektirmektedir. Bu çalışmada kurgulanan hipoteze göre, hava trafiği epidemiyolojiden adapte edilen bölmeli hastalık yayılım modeli ile modellenebilir, parametreleri gelecek zaman adımları için tahmin edilebilir, daha sonra da bu tahmin edilen parametreler kullanılarak optimal aksiyon üretebilecek bir model oluşturulabilir.
Hava trafiğinin bölümlü model ile modellenmesinde, meta popülasyon modeli denilen yaklaşım benimsenmiştir. Normal şartlarda bölümlü model yaklaşımında bölümler popülasyonu oluşturan bireyleri temsil etmektedir. Hava trafik ağını oluşturan bireyler de bu yaklaşımda uçakların kendisine tekabül etmektedir. Ancak meta popülasyon yaklaşımı ile, tüm uçaklar münferit olarak değerlendirmek yerine, uçuşların yoğunluğu ve frekansları olasılıksal ağırlık olarak temsil edilip, "popülasyon üstü popülasyon" oluşturularak havalimanları hava trafiği modeli popülasyonun en ufak elemanı olarak temsil edilebilir. Bölümlü modelde hastalığın, ya da bu çalışmadaki uygulamasıyla gecikmelerin yayılımını açıklayan bir dizi diferansiyel denklem bulunmaktadır. Bu denklemlerde kullanılacak parametreler; enfeksiyon oranı, iyileşme oranı ve meta popülasyon yaklaşımıyla elde edilen mevcut hastalık oranıdır. Bu modeli hava trafik ağına uyarlarken, enfeksiyon oranı gecikme etkisinin bir havalimanından diğer havalimanına aktarılma olasılığını temsil eder. Fiziksel karşılığında bu olasılık, bu iki havalimanı arasındaki uçuş sayısı ile ifade edilir. Örneğin toplamda 100 uçuş veren bir A havalimanının, belli bir periyotta 20 adet uçuşu B havalimanına oluyorsa, A havalimanın B havalimanına olan enfeksiyon oranı \%20 olarak ifade edilir. Buna göre bir havalimanında, spesifik bir OD çifti sabit tutularak uçuş sayısı arttırılırsa, o OD çifti özelindeki enfeksiyon oranı düşecektir. Havalimanı toplamda ne kadar uçuş veriyorsa, OD çiftlerinden birine düşen enfeksiyon oranı o kadar azalcaktır. Fiziksel olarak yorumlandığında, büyük ve yoğun trafik alan havalimanları operasyonları geniş olduğu için herhangi bir bozuntuyu ve gecikme durumunu yüksek bir oranda bir başka havalimanına aktaramaz denilebilir. Ancak kısıtlı sayıda OD çiftine hizmet veren bir havalimanında yaşanan bir gecikme, yüksek bir oranla diğer havalimanlarına aktarılabilir. Mantıksal olarak, hedef havalimanı başlangıç havalimanının operasyonlarında ne kadar fazla yer tutuyorsa, enfeksiyon riskinin yani gecikmeyi hedef havalimanına aktarma riskinin o kadar büyük olduğu söylenebilir. Dolayısıyla enfeksiyon oranı her havalimanı için ayrı ayrı hesaplanan, o havalimanında operasyon gösteren OD çiftlerine ve toplam uçuş sayısına bağlı matris formunda bir parametre olmaktadır. Enfeksiyon oranı 0 ile 1 arasında bir olasılığı temsil ettiğinden dolayı, havalimanının hizmet verdiği her OD çiftindeki frekans sayısı toplam uçuş sayısına bölünerek normalize edilir ve bu sayede uçuş sayılarıyla enfeksiyon oranı birbirine bağlanmış olur. Tabii ki uçuş planları ve dolayısıyla enfeksiyon oranı gibi parametrelerin ifade edilebilmesi için zamansal olarak bir ayrıklaştırma yapılması gerekmektedir. Havacılıktaki yetkin kuruluşlarca iniş veya kalkış zamanlarındaki 15 dakikalık artı veya eksi kayma bir gecikme olarak kabul edilmemektedir. Dolayısıyla bu çalışmada da ayrık zaman pencerelerinin 15 dakika olarak seçilmesi uygun görülmüştür. Buna göre hava trafik ağındaki bir $t$ zamanında bir havalimanının enfeksiyon oranı parametresine bakılmak istendiğinde, 15 dakikalık süre içerisinde kalkacak veya inecek olan uçakların bilgisiyle oluşturulmuş bir enfeksiyon oranı matrisi ya da trafik akışı matrisi görülmüş olur. Bölümlü modelde diğer bir önemli parametre olan iyileşme oranı, enfeksiyon oranının aksine 0 ile 1 arasında olmak zorunda değildir. Negatif veya pozitif herhangi bir skalar değere sahip olabilecek bu parametre aslında havalimanlarının gecikmeleri ne kadar iyi idare edebilecekleriyle belirli seviyede orantılı olan bir metriktir. Bu metrik havalimanlarının gecikmeleri idare etme performansını temsil etmesine rağmen, herhangi bir operasyon verisine bağlı şekilde değil tamamen bölümlü modelin diferansiyel denkleminde iyileşme oranının yalnız bırakılmasıyla hesaplanmaktadır. Daha önce bahsedildiği gibi bu denklemdeki 3 parametreden, mevcut gecikme oranı ve enfeksiyon oranları bilinmektedir, bu sayede iyileşme oranı hesaplanabilmektedir. Mevcut gecikme oranı ve enfeksiyon oranı, çalışmada kullanılan verisetinde mevcuttur. Bu sayede tüm parametreleri bilinen, hava trafik ağına uyarlanmış bölümlü model elde edilir. 
Metodolojinin ikinci kısmında ağın gelecek zaman aralığındaki durumu tahmin edilmek istenmektedir. Yani her havalimanının gelecek zaman adımındaki gecikme oranı hesaplanmalıdır. Bunun için enfeksiyon oranı ve iyileşme oranı parametreleri kullanılır. Enfeksiyon oranı zaten uçuş trafiği planıyla önceden bilindiği için, yalnızca iyileşme oranı gelecek adım için tahmin edilmelidir. Bunun için derin öğrenme metodu kullanılmaktadır. Buna göre bir derin öğrenme modeli, verisetindeki veri kategorilerini kullanarak bunlarla iyileşme oranı arasında bir ilişki kurmaya çalışır. Bu sayede modele veri beslendiğinde o verilerin ait olduğu havalimanıyla ilgili bir iyileşme oranı tahmin eder. Bu model kullanılarak ağdaki tüm havalimanları için gelecek zaman adımındaki iyileşme oranları tahmin edilir. Bu sayede gelecek zaman adımındaki gecikme oranlarını epidemik model ile hesaplamak için gereken iki parametre bilinmiş olur ve hava trafik ağının bir sonraki zaman adımındaki durumu tahmin edilmiş olur. Yapılan bu tahminle geleceğe dair bilgi edinilir. Bu bilgi aksiyon üreten modele beslenir ve modelden optimal bir aksiyon elde edilir. Bu model pekiştirmeli öğrenme metoduyla eğitilmiş bir modeldir. Onbinlerce yapay senaryo ile eğitilen bu model temelde epidemik modelin diferansiyel denklemindeki gecikme oranı değişimini olabildiğince minimuma çekmeye çalışır. Bu amaç tüm sistem için geçerli olduğu için, toplamdaki gecikme oranı düşecekse bazı havalimanların gecikmelerinin artmasına müsaade edilebilir. Pekiştirmeli öğrenme ile eğitim sırasında, mevcut verisetindenden referans alınarak, rastgele aksiyonlar denenir ve bu aksiyonların ağda iyileşmeye sebeb olup olmadığı kontrol edilir. Bu iyileşme epidemik modeldeki diferansiyel denklemlerin lineerleştirilip, özdeğerlerinin hesaplanmasıyla bulunur. Gecikme oranıyla çarpım halinde olan matrisin en büyük özdeğerinin reel kısmı olabildiğince minimize edilmeye çalışılır. Aksiyon sonrasında bu değer artıyorsa sistem stabilitesi kötüye gitmiş, azalırsa da iyiye gitmiş demektir. Bu geri beslemeyle pekiştirmeli model eğitilir ve bu hedef değeri düşüren aksiyonlara yüksek ödül atanır. Bu sayede pekiştirmeli öğrenme modelinin iç parametrelerine çeşitli senaryolarda en optimal aksiyonu üretebilecek şekilde ince ayar yapılmış olur. Çalışmanın son kısmı, hava trafik ağında bozuntulara sebebiyet verdiği için kuraldışı uçuşlar ve bunların otomatik tespitini sağlayan bir model ile ilgilenmektedir. Uçuş rotaları birbirinden çok farklı olabilse de, bazı belli başlı kurallar ve örüntüler çerçevesinde, uçuş verimliliği için optimize şekilde oluşturulmaktadırlar. Bu kurallar ve örüntüler havasahası kullanımı, kontrolörlerin bilinç düzeyi, hava muhalefetleri NOTAMlar gibi birçok faktöre bağlı olarak basit ya da kompleks olabilir. Tüm bu ortam içerisinde uçuşların parametreleriyle, yani sadece istatistiki bilgilerle, sınıflandırma ve anomali tespiti yapılması oldukça zorlu bir problemdir. Probleme çözüm olarak bu çalışmada, uçuşların zaman temelli karakteristiklerini dikkate alıp, herhangi bir kuraldışılık olup olmadığını tespit edebilen bir model önerilmiştir. LSTM Otokodlayıcı mimarisi ile oluşturulan bu model nispeten kısa zaman aralıklarıyla (16 saniyelik veri akışı) bir uçuşun hangi uçak tipine ait olduğunu ve kuraldışı bir durum olup olmadığını tanıyabilmektedir. Bu sayede hava trafik ağı üzerinde çalışan diğer modellerin paralelinde, anomali barındıran uçuşları yakalayabilmek için havasahasındaki tüm uçuşları dinleyebilen bir model elde edilmiş olur. Elde edilen sonuçlara göre, önerilen algoritma mimarisi ticari uçuşların yoğun olduğu havasahalarında askeri uçuşları, dolayısıyla havasahasında bozuntu oluşturan uçuşları başarıyla tespit edebilmektedir. Bu tez çalışması neticesinde derin öğrenme ve pekiştirmeli öğrenme sayesinde veri güdümlü olarak bir modeller bütünü elde edilmiş olur. Çalışma sonucunda epidemik modele oturtulmuş hava trafik ağı modelindeki iyileşme oranları tahmin eden derin öğrenme modeli, gelecek zaman adımındaki ağ durumu tahminine göre de optimal bir aksiyon oluşturan pekiştirmeli öğrenme modeli ve havasahasını tarayarak anomali barındıran uçuşların tespitini yapabilen bir derin öğrenme modeli olmak üzere 3 ana model elde edilmiştir. Elde edilen sonuçlara göre bu yaklaşım, çeşitli senaryolarda hava trafik ağı sisteminin gecikmelere olan direncini ve yayılıma olan stabilitesini artırmaktadır ve havasahasındaki kuraldışı uçuşları tespit edebilmektedir. Metodolojinin veri ağırlıklı olması, veri kalitesiyle ve veride bulunan eğilimlerden etkilenebilse de, epidemik modelin kullanılmasıyla en azından trafik ağının modellenmesi yükü matematiksel temele oturtulmuş olup, genel performans açısından tatmin edici performans sağlayabilen bir yaklaşım elde edilmiştir.

Abstract:
Air traffic networks represent highly complex and interconnected physical systems. Unlike other transportation networks, air traffic is very heavily regulated and physically constrained. Although the airways and airspaces are somehow more flexible compared to land based transportation systems, the fact that aircrafts can only positioned on and operated by airports make them quite dependent on the operations of the airports. Air traffic is regulated to ensure safety, while also maintaining the throughput of travel from one location to another. While these regulations does a decent job on keeping the air travel safe and systematical, they fall short when there are disruptions among the network that hinders the air traffic. There are numerous reasons for disruptions in air transportation; weather conditions, accidents, capacity constraints, personnel strikes etc. Yet their negative effect to the air traffic is mostly the same: introducing delays. Due to the connected nature of the air traffic and airports, when a delay generating event occurs at one place, the other members of the network could experience the similar effects, if not at a larger degree. This delay propagation means there is a ripple effect through the network which can snowball the delay generations and cause very large congestions. To relieve the effects of delay generating events, air traffic federators regulate the air traffic in a reactionary way. This may include reducing the capacity on certain airports or airways, giving NOTAMs, holding aircrafts on the ground or in the air (with hold patterns). Since all these actions are \emph{reactionary}, they are set in place after the delays already propagates through the network since it is trivial to asses and quantify the propagations in a large and complex network system. This study hypothesis that if the air traffic network can be modeled so that the propagations can be accurately calculated, it becomes possible to take proactive actions instead of reactive ones. Proactive actions are significantly more important when there is a risk of snowballing and propagation. It allows to take action when the ill effects are still contained on fewer members with smaller intensities. This paves the way for a more effective and less costly approach. Hence, the study proposes a method with 3 main parts; first one is to model the air traffic network so that propagations can be quantified, second one is to estimate the parameters of this model to keep a short-sighted vision into the upcoming network state and third one is to come up with a comprehensive action generating model to find optimal proactive actions that can keep the delay spreading at minimum and improve system resiliency. The air traffic modeling part is done via adopting compartmental model from epidemiology. This model explains the tranmission of disease within a population. When it is applied to the physical network system, instead of disease and humans, the delay amount and aircrafts is used. Additionally with the meta population model, instead of considering aircrafts one by one, airports can be used as they are focused points of aircraft populations. By linking transmit rate to the flight frequency between airports and the recovery rate to the delay handling characteristics of the airport, The parameter estimation part is done by calculating the historic recovery rates of the airports and then using deep learning inference to predict the next time step's recovery rates. The other parameters of the air traffic model, such as the traffic flow, is already known before hand (flight plans). Therefore through the estimation of recovery rate the network state of the upcoming states can be accurately predicted. This prediction can then be fed to the action generating algorithm to make the most informed decision. The action generating algorithm therefore must fundamentally be a deterministic state to action mapper. Reinforcement learning approach is utilized to train this state to action mapper to make it capable of generating optimal decisions under a sufficiently large spectrum of conditions. 
The final part of this study concerns with anomalous flight detection in air traffic as these types of flights are one of the sources of disruptions in an air traffic network. Although flight paths naturally diverge from one another, they still adhere to a set of patterns that have been tested in various environments and are optimized for them. These patterns may or may not be simple, depending on a number of factors, such as airspace use, the cognitive complexity of controllers, the weather, and NOTAMs. It is a challenging task to accurately classify flights just by their trajectories into a desired set of categories based solely on its statistical properties because of the high variance. For this purpose, the study incorporates a statistical approach that takes into account the time-based characteristics of the flight trajectories to determine whether they are abnormal or not. This statistical method with LSTM autoencoders makes it possible to train the model with historical data and quickly predict the flight class, taking into account the time-based characteristics of a flight trajectory. LSTM autoencoders can capture the class of a flight with relatively shorter time windows (16 second intervals). Therefore the air space can be periodically sweeped for anomalies while the network model and action algorithm runs in parallel.  The obtained results demonstrate that the suggested architecture is quite capable of classifying abnormal flight trajectories as it successfully detects simulated fighter aircraft trajectories in airspaces with high commercial flight density. With the applications of deep learning and reinforcement learning, this whole methodology ensembles is largely data-driven, however the introduction of the compartmental model from epidemiology lays out a strong and accurate mathematical formula to support these data-centric approach. As the results suggests, The whole network's resiliency, i.e. its ability to keep delays from spreading and absorbing them, significantly increases when the optimal actions are reflected on the parameters. Additionally with the help of unsupervised learning, anomalous flights are also detected and represented as a disruption source to the network. Possible biases and shortcomings due to the data-driven approach is recognized throughout the study yet the overall method is deemed to be of significant importance in terms of managing resiliency through air traffic networks.