České vysoké učení technické v Praze Fakulta elektrotechnická Katedra kybernetiky
Bakalářská práce
Řízení letového provozu dle pravidel Pavel Kabourek
Vedoucí práce: RNDr. Jan Tožička
Studijní program: Otevřená informatika Obor: Informatika a počítačové vědy Květen, 2014
Poděkování Rád bych zde poděkoval vedoucímu práce RNDr. Janu Tožičkovi a Bc. Štěpánu Kopřivovi, MSc. Za jejich čas a rady, kterém mi věnovali při řešení dané problematiky. Dále bych rád poděkoval jednomu bývalému zaměstnanci společnosti CSSOFT (který si nepřeje být jmenován) za jeho čas a asistenci při studiu řízení letového provozu.
Prohlášení autora práce Prohlašuji, že jsem předloženou práci vypracoval samostatně a že jsem uvedl veškeré použité informační zdroje v souladu s Metodickým pokynem o dodržování etických principů při přípravě vysokoškolských závěrečných prací.
V Praze dne 22.5.2014
..........................................
České vysoké učení technické v Praze Fakulta elektrotechnická Katedra kybernetiky
ZADÁNÍ BAKALÁŘSKÉ PRÁCE Student:
Pavel K a b o u r e k
Studijní program:
Otevřená informatika (bakalářský)
Obor:
Informatika a počítačové vědy
Název tématu:
Řízení letového provozu dle pravidel
Pokyny pro vypracování: 1. Nastudujte systém AgentFly a jeho rozšíření pro firmu CS-SOFT. 2. Nastudujte základy řízení letového provozu. 3. Naimplementujte dodaný pravidlový systém pro řízení letového provozu. 4. Experimentálně ověřte implementovanou metodu a porovnejte s aktuálním stavem.
Seznam odborné literatury: Dodá vedoucí práce.
Vedoucí bakalářské práce: RNDr. Jan Tožička Platnost zadání: do konce zimního semestru 2012/2013
L.S.
prof. Ing. Vladimír Mařík, DrSc. vedoucí katedry
prof. Ing. Pavel Ripka, CSc. děkan V Praze dne 9. 1. 2012
Abstrakt Cílem práce je porovnat systém pro řízení letového provozu dle dodaných pravidel s aktuálním stavem. Na začátku je provedena analýza trajektorií, kolizí a možných řešení. V další části jsou provedeny simulace aktuálního letového provozu a simulace letového provozu dle dodaných pravidel. Za účelem porovnání jsou provedeny simulace dle pravidel s různými vstupními parametry. Na konci jsou jednotlivé metody řízení porovnány na základě počtu řešených kolizí, množství spotřebovaného paliva a doby letu.
Abstract The goal is to compare the rule based air traffic control and the current system. There are analysis of trajectories, way-points and possible solutions at the beginning. Next part contains simulations of the current system and and the rule based system. There are simulations of rule based system with different input parameter for better comparison. Systems are compared on the basis of the number of solved collisions, the amount of consumed fuel and the time of flight.
Obsah 1 Vysvětlení pojmů.......................................................................................................1 1.1 Letová hladina....................................................................................................1 1.2 Kolize.................................................................................................................1 1.3 Separace.............................................................................................................1 2 Zadání........................................................................................................................3 2.1 Poskytnutá pravidla............................................................................................3 3 AgentFly....................................................................................................................5 4 Předběžná analýza......................................................................................................7 4.1 Azimut................................................................................................................7 4.2 Stoupání a klesání..............................................................................................9 4.3 Kolize...............................................................................................................10 4.4 Simulace...........................................................................................................10 5 Analýza dat..............................................................................................................13 6 Implementace...........................................................................................................17 6.1 Trajektorie........................................................................................................18 6.2 Detekce kolizí...................................................................................................18 6.3 Simulace aktuálního stavu................................................................................18 7 Porovnání výsledků..................................................................................................19 7.1 Výsledky simulace pouze nad ČR....................................................................19 7.2 Výsledky celkové simulace..............................................................................21 8 Závěr........................................................................................................................25
Seznam obrázků Obr. 4.1: Základní azimuty dle světových stran...........................................................7 Obr. 4.2: Azimut na startu a v cíli.................................................................................9 Obr. 5.1. Histogram azimutů.......................................................................................14 Obr. 5.2. Počet kolizí v daném úhlu (logaritmické měřítko)......................................14 Obr. 7.1. Průměrná spotřeba paliva nad ČR................................................................19 Obr. 7.2. Počet kolizí nad ČR.....................................................................................20 Obr. 7.3. Průměrná doba letu nad ČR.........................................................................20 Obr. 7.4. Průměrná spotřeba paliva celkem................................................................21 Obr. 7.5. Počet kolizí celkem......................................................................................22 Obr. 7.6. Průměrná doba letu celkem..........................................................................22
1 Vysvětlení pojmů 1.1 Letová hladina Letová hladina udává výšku letadla. Jedna letová hladina odpovídá sto stopám. Letadla létají pouze v hladinách, které jsou násobky desíti, důvodem je vertikální separace.
1.2 Kolize Každé letadlo má okolo sebe pomyslný válec, takzvanou bezpečnostní zónu. Výška zóny odpovídá výšce deseti letových hladin. Poloměr je pět námořních mil. Letadlo je uprostřed této zóny. Kolize nastává, pokud jedno letadlo vstoupí do bezpečnostní zóny druhého letadla.
1.3 Separace Separace znamená odstranění kolize z trajektorií dvou letadel. Důsledkem využívání pouze letových hladin, které jsou násobkem deseti, je přirozeně dosaženo vertikální separace.
1
2
2 Zadání První částí zadání je nastudování systému AgentFly a jeho rozšíření pro společnost CS-SOFT. Dokumentace není příliš rozsáhlá, je tedy potřeba funkcionalitu a možnosti použití zkoumat přímo v poskytnutých zdrojových kódech a ukázkových simulacích. Publikace shrnující základy řízení letového provozu v době vniku této práce není dostupná. Potřebné informace je potřeba dohledat především v leteckých příručkách poskytovaných FAA (Federal Aviation Administartion) [1]. Programovací jazyk pro implementaci pravidel je daný systémem AgentFly. Implementace bude provedena v jazyce Java. Během simulace se budou shromažďovat data o počtu řešených kolizí, spotřebě paliva a době letu. Algoritmus bude mít jeden vstupní parametr a to počet úseků do kterých bude rozdělen azimut (více viz 2.1). Implementace bude použita pro simulaci letového provozu nad Českou Republikou v časovém úseku 24 hodin. Informace o aktuálních trajektoriích letadel byly dodány společně se zadáním práce. Výsledná data budou vyhodnocena a porovnána s aktuálním stavem řízení letového provozu.
2.1 Poskytnutá pravidla Součástí zadání jsou pravidla poskytnutá společností CS-SOFT. Dle pravidel budou letové hladiny rozděleny na základě azimutu, pod kterým dané letadlo momentálně letí. Rozdělíme-li azimut do navrhovaných čtyřech úseků, dostaneme skupiny po čtyřiceti letových hladinách. Letadlo letící pod azimutem v prvním úseku smí letět v libovolné skupině, ale vždy pouze v první letové hladině v rámci této skupiny. Letadlo letící pod azimutem z druhého úseku, vždy pouze v jedenácté letové hladině libovolné skupiny, atd. 3
Ke kolizi trajektorií tak může dojít pouze mezi letadly letícími pod azimuty ze stejného úseku. Pokud ke kolizi dojde, upraví jedno z letadel svou letovou hladinu, aby předešlo reálné kolizi. Ve skutečnosti to znamená, že letadlo klesne nebo nastoupá do odpovídající hladiny v jiné skupině.
4
3 AgentFly AgentFly je založený na systému Aglobe, jedná se o komplexní multiagentní systém. Hlavní předností je možnost autonomního řízení letadel pomocí umělé inteligence. V průběhu letu je umožněna komunikace mezi letadly a společné řešení kolizí. Dále je možné letadla rozdělit do jednotlivých skupin, které mezi sebou mohou a nemusí spolupracovat. Díky použití BADA (Base of Aircraft Data), probíhá simulace za reálných fyzikálních podmínek daných letadel. BADA je soubor základních fyzikálních a letových vlastností letadla. S využitím těchto dat je nejen možné kontrolovat výšku a rychlost letu, stoupání či klesání, ale i počítat tah motorů a spotřebu paliva. Dále je v systému umožněna vizualizace scénáře. Rozšíření pro společnost CS-SOFT je diskrétní simulace využívající části systému AgentFly. Je zde vidět příklad načítání trajektorií, využití systému pro hledání detekcí nebo postupnou úpravu stavu letu v čase.
5
6
4 Předběžná analýza 4.1 Azimut Azimut je orientovaný úhel který svírá směr pohybu a směr k severnímu pólu. Měří se po směru hodinových ručiček od směru severního, tedy od severu k východu.
Obr. 4.1: Základní azimuty dle světových stran.
7
Pro výpočet azimutu bude při simulaci použit následující vzorec. Část vzorce pro výpočet azimutu je převzata z Movable Type Scripts [2]. Vzorec pro arctan2 je převzat z Wikipidie [3].
α =norm(arctan 2(sin( Δ long )⋅cos(lat 2), cos (lat 1)⋅sin( lat 2)−sin(lat 1)⋅cos (lat 2)⋅cos ( Δ long))) norm(β)=
{β+β2:β⩾0 π: jinak
Δ long=lon 1−lon2
Vstupními proměnnými jsou lat1, lon1, lat2, lon2. Lat1 odpovídá zeměpisné šířce aktuální pozice, lon1 odpovídá zeměpisné délce aktuální pozice. Lat2 a lon2 odpovídají zeměpisné šířce a délce cílového bodu. Výsledkem funkce arctan2 je azimut v radiánech v intervalu ( -π, π>, tato hodnota je pak funkcí norm normalizována do intervalu <0, 2π). Přestože cílový bod zůstává stejný, azimut se v průběhu cesty mění. Důvodem je změna pozice a tedy změna sklonu spojnice aktuální pozice se severním pólem. Může se tedy stát, že během letu letadlo přejde z jednoho úseku do druhého a je potřeba upravit jeho letovou hladinu.
8
Obr. 4.2: Azimut na startu a v cíli.
4.2 Stoupání a klesání Cílem simulace je porovnat efektivitu pravidel při řízení letového provozu. Pravidla nejsou určena pro řešení kolizí při startu a při přistání, tyto části budou tedy při každé simulaci stejné. V rámci zjednodušení problému je možné fázi startu i přistání vypustit a uvažovat počátek trajektorie v již stanovené výšce, stejně tak její konec.
9
Změna letové hladiny při separaci nebo změně azimutu bude počítána pomocí systému AgentFly. Díky BADA modelu tak bude možné zvolit optimální manévr s ohledem na typ letadla, čas i spotřebu paliva.
4.3 Kolize Pro zjištění kolize mezi trajektoriemi bude použit systém AgentFly, který implementuje následující algoritmus. Trajektorie je v určitých časových úsecích nahrazena přímkami, jejich souřadnice jsou posléze převedeny na kartézské. Postupně je počítána vzdálenost přímky v jedné trajektorii od odpovídající přímky v trajektorii druhé. Pokud je vzdálenost menší, než poloměr bezpečnostní zóny, znamená to, že trajektorie kolidují. Kolize bude řešena dle pravidel. Jedno z letadel klesne nebo stoupne do odpovídající hladiny v jiné skupině. Pokud ke kolizi dojde během stoupání čí klesání, bude manévr posunut v čase tak, aby ke kolizi nedošlo.
4.4 Simulace Systém AgentFly je příliš obsáhlý a komplexní. Simulace tedy bude diskrétní aplikace využívající pouze části tohoto systému. Dále budou použity části rozšíření pro společnost CS-SOFT, především načítání trajektorií. V rámci optimalizace nebude probíhat simulace v předem stanovených časových intervalech, ale v intervalech určených událostmi. Za událost je považováno přistání nebo start letadla a změna letové hladiny letadla (řešení kolize, překročení hranice úseku azimutu). Každý časový úsek simulace tak bude nejdelší možný vzhledem k dané situaci. Každý časový úsek bude simulován pomocí části AgenFly systému, která provádí přesné výpočty na základě BADA modelu. Tím bude dosaženo přesnosti potřebných výpočtů při zachování jednoduchosti a rychlosti aplikace. Pro účely simulace je nutné uchovávat kompletní informace o aktuálním stavu letadla. Na konci si-
10
mulace budou provedeny výpočty pouze s daty, stanovenými jako kritéria pro porovnání jednotlivých systémů.
11
12
5 Analýza dat Před samotnou simulací byly provedeny výpočty na základě poskytnutých dat. Za tímto účelem byly napsány jednotlivé aplikace. Dle těchto výpočtů bylo možné odhadnout, zda bude mít nový systém přínos. Data obsahují lety přes území České republiky ze dne 13. 4. 2011. Trajektorie obsahují vždy počáteční i cílové letiště a trasové body na území ČR. Trasové body mimo ČR nejsou obsaženy. Letadlo tedy letí přímočaře z počátečního letiště až k prvnímu bodu nad naším území. Po opuštění vzdušného prostoru ČR letí opět přímočaře k cílovému letišti. Předběžné výpočty jsou provedeny na přímočarých trajektoriích z počátečního do cílového letiště.
13
Obr. 5.1. Histogram azimutů. Obrázek 5.1 zobrazuje počty letů pod jednotlivými azimuty. Z grafu je možné odhadnout, jak rozdělit azimut do jednotlivých úseků.
Obr. 5.2. Počet kolizí v daném úhlu (logaritmické měřítko).
14
Obrázek 5.2 zobrazuje počty kolizí v jednotlivých úhlech. Úhel je měřen od vodorovné osy proti směru hodinových ručiček. Délka čáry reprezentuje počet kolizí (podobně jako u histogramu). Vzhledem k velkým rozdílům je měřítko logaritmické. Při rozdělení azimutu do čtyřech úseků se vertikální separací vyřeší kolize v úhlu vetším než devadesát stupňů, tedy všechny kolize v levé polovině grafu. Předběžné výpočty a odhady ukazují rozdělení azimutu do čtyřech úseků jako efektivní pro separaci. Přesná čísla ukáže až simulace, z odhadů ovšem vyplývá, že by tento způsob mohl vyřešit přes osmdesát procent kolizí. Přestože se rozdělení do čtyřech úseků jeví být efektivním, z obrázků 5.1 a 5.2 se dá usuzovat, že jemnějším dělením bychom mohli dosáhnout ještě lepších výsledků. Všeobecně se dá očekávat snížení počtu kolizí s rostoucím počtem úseků. To ovšem přináší častější změnu letové hladiny a větší odchylku od optimální výšky, což může mít za následek složitější trajektorie a vyšší spotřebu paliva. V krajním případě je možné uvažovat o rozdělení do tři sta šedesáti úseků. Ani v tomto případě však není jistota úplného odstranění všech kolizí. Problémem je omezení minimální a maximální letové výšky. Letadlo by nebylo schopné operovat v rozmezí tří tisíc šesti set letových hladin.
15
16
6 Implementace Simulace včetně aplikací pro předběžné výpočty je na přiloženém CD ve složce rule_controle. Dále jsou přiloženy potřebné závislosti ze systému AgentFly a jeho rozšíření pro společnost CS-SOFT. Simulace začíná načtením trajektorií, posléze je v jednotlivých trasových bodech upravena výška letu, aby odpovídala azimutu. Pokud azimuty ve dvou po sobě jdoucích bodech nespadají do stejného úseku, je metodou půlení intervalu nalezena pozice, kde dochází k překročení hranice a výška je upravena. Samotná simulace postupuje po proměnných časových intervalech. Interval je určen první událostí. Nejprve je ze seznamu trajektorií vybrána trajektorie s nejbližším trasovým bodem, tím je určen časový interval. Následně jsou vyhledány a vyřešeny všechny kolize v tomto intervalu. V rámci každého kroku je provedena aktualizace stavu letadla pomocí systému AgentFly. Tím je dosaženo výpočtu reálného času, vzdálenosti a spotřeby paliva. Po ukončení simulace jsou vyhodnocena data. Výsledkem simulace jsou hodnoty ve formátu CSV, připravené k importu do tabulkového procesoru. Konkrétně se jedná o průměrnou spotřebu paliva na jeden let, průměrný čas jednoho letu a celkový počet řešených kolizí. Pro možnost porovnání je simulace provedena několikrát, pokaždé pro jiný počet úseků. Aplikace je navržena tak, aby na jeden běh odsimulovala a vypsala data pro zadaný rozsah úseků. Aktuální konfigurace simuluje od jednoho do dvaceti úseků. Výsledná data jsou zpracována do grafů a vyhodnocena v následující kapitole.
17
6.1 Trajektorie V simulaci je pro uchování trajektorie použit rozšířený objekt Trajectory z rozšíření pro CS-SOFT. Rozšíření umožňuje uložit aktuální stav letadla, počet řešených kolizí a také informace o BADA modelu pro konkrétní typ letadla. Trajektorie se skládá ze seznamu trasových bodů – objekt Waypoint, který obsahuje informace o aktuální pozici, času a rychlosti letadla. Logika načítání trajektorií ze souboru byla částečně převzata z rozšíření AgentFly, ovšem především kvůli úpravě trajektorií a potřebě načítat BADA modely letadel, musela být velká část upravena a nešlo tedy použít dědičnost. V rámci načítání dat jsou trajektorie upraveny pro simulaci nebo předběžné výpočty. To je důvod, proč projekt obsahuje více tříd pro načítání dat. Data pro simulaci byla původně načítána bez letišť, posléze bylo zjištěno, že trajektorie neobsahuje body mimo ČR. Bylo tedy potřeba implementovat možnost přidat letiště na začátek a konec trasy. Trajektorie začíná v požadované výšce nad počátečním letištěm, končí opět ve finální výšce nad koncovým letištěm.
6.2 Detekce kolizí Trajektorie letadel která doposud nevzlétla nebo již přistála nejsou brány v úvahu. Kolize se detekují pouze mezi letadly ve stejném sektoru. Výjimku tvoří pouze úseky, kde letadlo klesá nebo stoupá, v těchto případech je potřeba detekovat kolizi se všemi ostatními letadly. Pro detekci je použita třída SphericalCollisionDetection ze systému AgentFly.
6.3 Simulace aktuálního stavu Aby bylo možné porovnat výsledky s aktuální stavem, je potřeba získat data pro let dle aktuálních neupravených trajektorií. Použita je stejná aplikace s počtem úseků nastaveným na jeden. Tím je docíleno letu v letové hladině dle aktuálního letového plánu.
18
7 Porovnání výsledků Simulace byla provedena dvakrát. Poprvé pouze pro provoz nad územím ČR. Podruhé pro celou trajektorii letu. Je tak možné porovnat účinnost pravidel pro provoz na malém území i rozsáhlé ploše. Hodnoty pro aktuální stav jsou v grafech vždy uvedeny pod číslem jedna.
7.1 Výsledky simulace pouze nad ČR Následující tři grafy zobrazují spotřebu paliva, počet kolizí a dobu letu pro simulaci pouze nad územím České republiky.
1040 1035
Palivo [kg]
1030 1025 1020 1015 1010 1005 1
3
5
7
9
11
13
Počet úseků
Obr. 7.1. Průměrná spotřeba paliva nad ČR
19
15
17
19
250
Počet kolizí
200 150 100 50 0 1
3
5
7
9
11
13
15
17
19
15
17
19
Počet úseků
Obr. 7.2. Počet kolizí nad ČR
1210
Doba letu [s]
1205 1200 1195 1190 1185 1
3
5
7
9
11
13
Počet úseků
Obr. 7.3. Průměrná doba letu nad ČR
20
Počet kolizí se rozdělením do úseků výrazně snížil. Spotřeba paliva značně kolísá, v některých případech klesá pod spotřebu při aktuálním stavu. Doba letu kolísá také. Při rozdělení do čtyřech úseků klesl počet kolizí z 203 na 5, tedy o cca 97 %. Spotřeba paliva klesla o 1 kg.
7.2 Výsledky celkové simulace Následující tři grafy zobrazují výsledky pro trajektorie s přidanými letišti.
12100 12000 11900 Palivo [kg]
11800 11700 11600 11500 11400 11300 1
3
5
7
9
11
13
Počet úseků
Obr. 7.4. Průměrná spotřeba paliva celkem
21
15
17
19
1000
Počet kolizí
100
10
1 1
3
5
7
9
11
13
15
17
19
15
17
19
Počet úseků
Obr. 7.5. Počet kolizí celkem
10150 10100
Doba letu [s]
10050 10000 9950 9900 9850 1
3
5
7
9
11
13
Počet úseků
Obr. 7.6. Průměrná doba letu celkem
22
I v tomto případě výrazně klesá počet kolizí, při rozdělení do osmnácti úseků je počet kolizí 0. Palivo i doba letu opět kolísají nad i pod hodnoty za aktuálního stavu. Při rozdělení do čtyřech úseků klesl počet kolizí z 339 na 1, tedy téměř o 100%. Spotřeba paliva klesla o 48 kg.
23
24
8 Závěr Odhady z předběžných výpočtů se v simulacích potvrdily. Obava z neúměrného nárůstu spotřeby paliva se v tomto konkrétním případě ukázala jako neopodstatněná. Na základě počtu kolizí lze systém pro řízení letového provozu hodnotit jako velmi efektivní. Již rozdělení azimutu do čtyřech úseků má za následek redukci téměř sta procent kolizí. S rostoucím počtem úseků konverguje počet kolizí k nule. Dalším pozitivem je klesající spotřeba, z výsledků se dá usuzovat, že let mimo optimální letovou hladinu je levnější, než časté řešení kolizí. Všeobecně však nelze určit zda je nový systém efektivnější. Spotřeba značně kolísá, dá se tedy předpokládat, že na jiném vzorku dat se bude chovat rozdílně. Přesto lze usuzovat, že spotřeba nijak výrazně neporoste. Zajímavým jevem je snížení počtu kolizí při prodloužení trajektorií. Příčinou je změna azimutu a tedy i letové výšky cestou k prvnímu trasovému bodu. Tím je způsobeno, že letadlo přilétá do letového prostoru ČR v jiné výšce, než bylo původně plánováno. Dojde tak k přirozené separaci a kolize nevzniká.
25
26
Seznam použité literatury 1: DEPARTMENT OF TRANSPORTATION (USA), AERONAUTICAL INFORMATION PUBLICATION, 2013, http://www.faa.gov/air_traffic/publications/atpubs/AIP/AIP_22nd_Edition.pdf 2: Chris Veness, Calculate distance, bearing and more between Latitude/Longitude points, 2010, http://www.movable-type.co.uk/scripts/latlong.html 3: Uživatelé Wikipedie, Atan2, 2012, http://en.wikipedia.org/wiki/Atan2
27
