1、Approcci multiagente al controllo del traffico aereo,Guagneli Luigi luigi.guagnelistudio.unibo.it II Facolt di Ingegneria Cesena,OUTLINE,Introduzione Contestualizzazione del problema Primo approccio Secondo approccio AgentFly Conclusioni,Introduzione: Definizione e valutazioni sullintroduzione della
2、 computerizzazione nel controllo del traffico aereo,Air Traffic Control (ATC),Servizio fornito da controllori a terra che dirigono gli aerei sulla terra e in aria. Scopo principale: separare gli aeromobili per evitare collisioni, per organizzare e accelerare il flusso del traffico, e per fornire inf
3、ormazioni e supporto per i piloti quando possibileprevenzione delle collisioni: separation“spazio aereo controllato” A seconda del tipo di volo e la classe di spazio aereo, lATC pu impartire Instructionsflight information (advisories),Computerizzazione dellATC,“Sistema di trattazione dellinformazion
4、e in tempo reale” sistema “fonetico-manuale” puro in cui le operazioni di controllo per lo pi di natura intellettuale, sono effettuate in maniera rigidamente coordinata e in tempo reale da un gruppo di individui operanti in “equipaggi”Limiti di capacit del sistema suddivisione dei compiti assegnatiA
5、ttualmente i Sistemi usati nei centri ATC sono il “Procedurale-Radar”Computerizzazione:riduzione dei carichi di lavoro mediante lesecuzione di operazioni attualmente eseguite dai controllori o dai loro assistenti; eliminazione degli errori umani; esecuzione di operazioni che superino le capacit dei
6、controllori, sottoposti alla pressione di unalta densit di traffico.,Contestualizzazione del problema,Incremento del traffico aereo e Approcci tradizionali,Decisioni di routing e condizioni aeroportuali 1.682.700 ore di ritardo nel 2007 Gestione del traffico aereo attuale sistema centralizzato, stra
7、tegia di routing gerarchico in grado di eseguire proiezioni di flussi che vanno da 1 a 6 ora,Approcci tradizionali:Modello Lagrangiano calcolo delle traiettorie dei singoli aeromobili (evitare le collisioni, ridurre la congestione)Modelli Euleriani pattern di flusso nello spazio aereo,Difficile appl
8、icazione a situazioni in cui le condizioni cambiano localmente o lautomazione lavora ancora con i controllori umani,Algoritmi centralizzati lenti Soluzione monilitica difficilmente distribuibile difficolt di esecuzione del “sanity check”,Controllo del traffico Aereo basato sugli agenti,Agenti autono
9、mi cercano di ottimizzare alcuni goal generali attraverso lapprendimento o la negoziazioneInterazioni ispirate da principi economici equit nella gestione del traffico aereo attraverso un sistema artificiale monetario che permette ritorsione contro gli agenti avidiLearning Agent con calcolo di ricomp
10、ense che incoraggino la cooperazioneAgentFly controllo del flusso del traffico aereo affidabile senza pianificazione centralizzata,Primo approccio,Universit della California, Santa Cruz in collaborazione con FAA e NASA,Configurazione dello spazio aereo,Flusso regionale e nazionale da 20 min 8 oreFac
11、et (Future ATM Concepts Evaluation Tool): modello basato sulla fisica dello spazio aereo USA. Strumento affidabile per la simulazione del traffico aereo, ampiamente usato dalla FAA, dalla NASA e dallindustria,USA - 20 centri regionali e 830 settori Due i problemi:(i) modellazione e simulazione di un
12、 grande sistema complesso (fedelt e affidabilit dei risultati)(ii) stabilizzazione del metodo con cui viene valutata la gestione del flusso (la riduzione diretta del ritardo totale pu portare ad ingiustizie verso particolari regioni o enti commerciali),Evoluzione del sistema,Funzione di valutazione
13、B(z) penalit di ritardo totale per tutti gli aerei nel sistema C(z) penalit totale di congestione costo di congestione,Quattro decisioni critiche: - definire gli agenti,- definire lo spazio di azione degli agenti, - selezionare gli algoritmi di apprendimento, - selezionare la struttura di ricompensa
14、.,Definizione degli agenti,Gli aerei: PRO: - azioni intuitive (cambio piano di volo, incremento o decremento velocit e altitudine) - alto livello di granularit (ogni agente la sua politica) CONTRO: - 40.000 aerei = spazio multiagente massiccio - campionamento dello spazio di stato lento,I fix (posiz
15、ioni individuali a terra per tutto lo spazio aereo):il numero pu variare a seconda delle necessitfix stazionari agenti possono raccogliere dati eriscontrano il comportamento da premiarepiani di volo di un aereo sono composti da fix gli agenti possono influenzare i pattern di flusso di traffico.fix i
16、mpiegati allinterno delle attuali procedure di routing di traffico aereo,Ogni agente responsabile di tutti gli aerei che passano attraverso il suo fix,e delle azioni,Tre tipi di azione Miles In Trail (MIT) - la distanza che il velivolo deve tenere da ogni altro mentre si avvicina al fix. MIT pi alto
17、, meno aerei saranno in grado di passare attraverso quel fix durante i periodi di congestione Ground Delay (Ritardo a terra) laereo arriver pi tardi al fix. Se alcuni agenti scelgono questa azione e altri no, la congestione decrementer perch verr sparsa. Rerouting (riindirizzare) gli aerei che attra
18、versano il suo fix. Deviando alcuni aeromobili lontano da particolari regioni, questa azione pu prevenire i casi specifici di congestione e quindi ridurre la congestione totale.,Algoritmi di apprendimento degli agenti,Ogni agente avr la propria funzione ricompensa e avranno lo scopo di massimizzarla
19、 utilizzando un algoritmo di reinforcement learning (-greedy learners con tasso di sconto 0).Ad ogni passo temporale, un agente compie unazione e riceve una ricompensa valutando tale azione. Lagente user poi tale ricompensa per aggiornare le sue politiche di azione in modo tale da cercare di intrapr
20、endere azioni che portino ad aumentare il premio. Dopo aver eseguito unazione e ricevuto una ricompensa R, un agente aggiorna il suo valore per lazione a, V (a) come segue:dove il tasso di apprendimento. Per promuovere lesplorazione di nuove azioni, ad ogni passo temporale lagente sceglie da una tab
21、ella lazione con il valore pi alto con probabilit 1 - e sceglieremo unazione casuale con probabilit .,V(a) (1-)V(a) + ()R,Struttura ricompensa dellagente,Approccio diretto (ogni agente riceva le prestazioni del sistema come sua ricompensa): non scala nei grandi sistemi Differenza di ricompensaStima
22、del difference rewardsDifference rewards precalcolatoCalcolo a priori della stima della differenza di premio, riducendo cos il numero di computazioni,Secondo approccio,Department of Computer and Digital Systems Engineering Polytechnic School, University of So Paulo,Considerazioni sullapproccio ad ag
23、enti,Ciascuna linea aerea ha BELIEFS, DESIRES e INTENTS relative allambiente del traffico aereo, ed una strategia opportuna per raggiungere i propri goal, risulta una buona soluzione trattarli come Agenti. Anche laeromobile, nonostante sia attivato e regolato da una strategia della linea aerea, ha u
24、n alto grado di autonomia quando ci sono da prendere decisioni riguardo la sicurezza del volo.Laeroporto visto come un entit autonoma la quale deve controllare luso sicuro delle sue risorse, come piste, zone di rullaggio e cancelli dimbarco.Tre classi di agenti: Airline, Aircraft e Airport. Il passe
25、ggero viene visto come un elemento passivo le decisioni in tempo reale di un volo non sono fatte dai passeggeri.,Definizione,Infrastruttura software,Tre livelli principali: SisBDPar: un sistema di database parallelo distribuito; JADE (Java Agent DEvelopment framework): fornisce un infrastruttura ad
26、agenti; Graphical ATM User Interface: pu essere accesa o spenta, in base agli scopi della simulazione. Allinterno di JADE, vengono sviluppati due distinti gruppi di agenti: Agenti ATM: implementazione del modello astratto di agente DASE (Distributed data Agent Service Environment): fornisce un grapp
27、olo di servizi dati che si integrano armonicamente con la piattaforma multi-agente JADE.,DASE,Obiettivi: Fornire agli agenti un semplice accesso ai dati distribuiti; Offrire risorse aggiuntive correlate allaccesso dati, come la garanzia di consistenza dei dati attraverso il controllo di concorrenza
28、distribuito,La maggior parte dei compiti degli agenti DASE vengono attivati dagli agenti client, al di fuori di DASE, e, rappresentati dagli agenti ATM. Ci sono tre gruppi principali di agenti funzionali:DASE Kernel Agents: Gli agenti Kernel sono responsabili dellavvio, lo spegnimento, il controllo
29、e il monitoraggio del sistema DASE. DASE Data Access Agents: Questo gruppo ha gli agenti che trattano con i client per le operazioni pi frequenti di accesso ai dati (dati ambiente, database). DASE Concurrency Control Agents: Gli agenti in questo gruppo garantiscono la coerenza dei dati in condizioni
30、 di concorrenza.,Terzo approccio: AgentFly,Czech Technical University,Simulazione, Pianificazione e Collision Avoidance (1/2),Ogni attivit di volo contenitore software per agenti intelligenti multipli. Ciascun agente: o modella una funzionalit hardware specifica (capacit sensoriale, controllo di vol
31、o dinamico), o di comunicazione, o incapsula unintelligenza in grado di prendere decisioni che supporti pianificazione o CA.AgentFly ha unarchitettura che supporta tre principali casi duso:modellazione multi agente e simulazione di volo liberopiattaforme di controllo di volo libero senza equipaggio
32、aereoApprocci alternativi alla pianificazione, che supporti il traffico aereo civile,Simulazione, Pianificazione e Collision Avoidance (2/2), Non necessita di componenti centralizzate. basato sulla tecnologia multi-agente Aglobe. Rilassa il problema di pianificazione ed esegue le simulazioni di volo
33、 multi agente. Invece di pianificare unoperazione anticollisione per numerosi aerei, viene costruito un piano di volo per ogni velivolo senza considerare possibili collisioni. Viene simulata tale operazione nellambiente AgentFly, che identifica possibili collisioni, e le risolve o attraverso ripiani
34、ficazione individuale o negoziazione peer-to-peer.,Pianificazione,Ogni agente un pianificatore di percorso che fornisce una traiettoria del piano di volo regolare, che rispetta tutti i vincoli e goal del modello dellaereo. Ciascun pianificatore trasforma i goal in una sequenza di waypoints, e prepar
35、a descrizioni dettagliate del singolo corridoio di volo. La traiettoria di volo data pu essere eseguita dallintegrazione dello standard Required Navigation Performance (RNP) in un processo di pianificazione, specificando in tal modo deviazioni ammissibili delle posizioni orizzontale e verticale dell
36、aereo allinterno del proprio corridoio.Quando un livello RNP non pi raggiungibile, il pianificatore cerca un altro piano.,Fasi di pianificazione,Il processo di pianificazione del percorso esegue due fasi accoppiate:1 fase: il pianificatore prepara la parte spaziale del piano di volo, rispettando le
37、restrizioni di traiettoria utilizzando lalgoritmo Accelerated A* (AA*). Lo spazio aereo, viene poi conservato in una struttura ad albero.2 fase: il pianificatore pianifica i cambiamenti di velocit di crociera, mappandoli sulle parti di traiettorie spaziali preparate. Il goal adattare tutte le restri
38、zioni di tempo e velocit di crociera date. Le fasi spaziale e temporale sono connesse in un loop cos che il sistema possa manipolare casi estremi.,Collision Avoidance,Quattro classi di meccanismi di CA: Rule-Based CA (RBCA)Algoritmo dominio-dipendente basato sul FAAs Visual Flight Rules (VFRs). Lage
39、nte determina il tipo di collisione sulla base dellangolo tra i vettori direzione degli aerei coinvolti. Ogni tipo di collisione = manovra fissa predefinitaIterative Peer-to-Peer Collision Avoidance (IPPCA)Negoziazioni multiagente volte a trovare la manovra CA pareto-ottimaleMulti-Party Collision Av
40、oidance (MPCA)Estende i primi due algoritmi permettendo diverse attivit per negoziare le loro manovre collettive CA.NonCooperative Collision Avoidance (NCCA)Supporta CA quando la comunicazione tra attivit impossibile,Conclusioni,La gestione efficiente, sicura ed affidabile del flusso del traffico ae
41、reo un problema complesso, che richiede soluzioni che integrano le politiche di controllo con orizzonti temporali che vanno da pochi minuti no ad un anno.Nellanalisi si visto come lo studio di una soluzione che utilizzi gli agenti, vada ad intaccare ambiti multidisciplinari (ricerca operativa, intelligenza artificiale, semplice applicazione algoritmica)Lutilizzo di sistemi multi agenti rappresenta sicuramente una buona base per lo sviluppo di algoritmi di facile implementazione e il cui utilizzo si affianchi alle attuali procedure, senza la necessit di modiche radicali.,
