Exemple de cluster d'avions

De nouvelles techniques pour le contrôle aérien

Dossier : Trafic aérienMagazine N°535 Mai 1998
Par Nicolas DURAND (87)
Par Jean-Marc ALLIOT (83)

Principes généraux

Le but pre­mier du con­trôle du traf­ic aérien est d’as­sur­er la sécu­rité des aéronefs. Le but sec­ond, d’as­sur­er un écoule­ment aus­si opti­mal que pos­si­ble des flux de traf­ic, en par­ti­c­uli­er en ter­mes de retards.

Nous allons tout d’abord pos­er quelques déf­i­ni­tions indis­pens­ables pour la com­préhen­sion du reste de notre exposé.

Route aéri­enne : le chem­ine­ment d’un avion dans l’e­space est une série de seg­ments de droite, reliant des points de report appelés balis­es. His­torique­ment, ces balis­es étaient bien sou­vent des points équipés de moyens de radionavigation.

Plan de vol : il con­tient tous les élé­ments indi­cat­ifs décrivant le vol prévu pour un avion (heure de départ, niveau de vol, route prévue).

Con­trôle en route : il s’ag­it du con­trôle à l’ex­térieur des zones entourant les aéro­ports (dans ces dernières, on par­le de con­trôle d’approche).

Secteurs de con­trôle : l’e­space aérien est divisé en secteurs de con­trôle. Chaque secteur est con­fié à un, ou plus sou­vent deux, con­trôleurs, qui ont la charge d’as­sur­er la sépa­ra­tion des aéronefs dans cette por­tion de l’e­space. Le trans­fert d’un avion d’un secteur à un autre secteur fait l’ob­jet d’une coor­di­na­tion entre les con­trôleurs en charge de cha­cun des deux secteurs.

Sépa­ra­tions : on définit une dis­tance hor­i­zon­tale exprimée en milles nau­tiques3 (NM), la sépa­ra­tion hor­i­zon­tale4, et une dis­tance ver­ti­cale exprimée en pieds5 (ft), la sépa­ra­tion ver­ti­cale6. On dit que deux avions sont séparés quand la dis­tance qui sépare leurs pro­jec­tions sur un plan hor­i­zon­tal est supérieure à la sépa­ra­tion hor­i­zon­tale ou quand la dif­férence de leurs alti­tudes est supérieure à la sépa­ra­tion verticale.

Con­flit élé­men­taire : deux avions sont dits en con­flit lorsqu’ils ne sont plus séparés. Si l’on se fixe une durée T, deux avions seront dits en con­flit poten­tiel pen­dant T, si durant le temps T, ils ont une prob­a­bil­ité non nulle7 d’être en conflit.

Fig­ure 1 – Exem­ple de cluster

Clus­ter : un clus­ter d’avions est une fer­me­ture tran­si­tive d’avions en con­flits poten­tiels. Si un avion A est en con­flit avec B à l’in­stant t < T (où T est l’hori­zon tem­porel exploré) et B est en con­flit avec C à l’in­stant t + Dt < T alors A, B et C appar­ti­en­nent au même clus­ter. Ain­si dans la fig­ure 1, les avions A et B ne sont jamais en con­flit mais ils appar­ti­en­nent au même clus­ter. Une dévi­a­tion de C pour éviter B peut lui per­me­t­tre d’éviter A.

L’ex­pres­sion con­flit à n avions sig­ni­fie en fait clus­ter à n avions.

Améliorer l’écoulement du trafic

Il existe plusieurs approches pour ten­ter d’amélior­er l’é­coule­ment du traf­ic. Elles se divisent en deux grandes caté­gories : d’une part, l’amélio­ra­tion de l’or­gan­i­sa­tion de l’e­space aérien et des flux de traf­ic, d’autre part, l’amélio­ra­tion du con­trôle aérien lui-même.

L’or­gan­i­sa­tion de l’e­space et des flux : on peut ten­ter tout d’abord d’amélior­er la façon dont l’e­space est découpé en secteurs. Jusqu’à présent, ce découpage a sou­vent été fait de façon empirique, et une approche plus sci­en­tifique peut per­me­t­tre d’e­spér­er une amélio­ra­tion capac­i­tive. Il faut cepen­dant garder en mémoire :

1) que le découpage actuel est le résul­tat d’une longue expéri­ence, et qu’il sera dif­fi­cile de l’améliorer,

2) que l’on ne peut aug­menter indéfin­i­ment le nom­bre de secteurs, car lorsque les secteurs devi­en­nent trop petits, la ges­tion des flux entrant et sor­tant devient plus coû­teuse que le con­trôle lui-même8.

On peut égale­ment ten­ter d’amélior­er l’é­coule­ment des flux en amélio­rant les mod­èles de capac­ité secteur, en pro­posant des tar­i­fi­ca­tions du con­trôle dif­férentes en fonc­tion des horaires, ou en pro­posant des routes alter­na­tives aux aéronefs pour décon­ges­tion­ner cer­taines zones. Enfin, on peut imag­in­er un change­ment rad­i­cal du découpage de l’e­space en prévoy­ant par exem­ple une zone de type ” Free Flight ” où le con­trôle serait assuré dif­férem­ment. Toutes ces tech­niques sont actuelle­ment à l’étude.

Le con­trôle aérien : la prin­ci­pale rai­son des retards observés aujour­d’hui en Europe (et par­ti­c­ulière­ment en France) est la sat­u­ra­tion des secteurs de con­trôle ” en route “. Pour ten­ter d’aug­menter la capac­ité du con­trôle en route, de nom­breuses solu­tions sont à l’é­tude. Les prob­lèmes à traiter sont bien iden­ti­fiés : il faut savoir prévoir les tra­jec­toires des avions, détecter les con­flits, regrouper ces con­flits par clus­ters, don­ner des manœu­vres sim­ples les résolvant, etc.

Si les prob­lèmes liés à la réso­lu­tion de con­flits aériens sont donc bien iden­ti­fiés, les tech­niques à employ­er le sont moins. Avant de ren­tr­er dans les détails tech­niques du prob­lème, nous allons nous employ­er à présen­ter quelques con­cepts généraux.

Prévision de trajectoires et détection de conflits

Avant de songer à résoudre les con­flits, il faut d’abord les détecter. Or, la détec­tion de con­flits se base avant tout sur une bonne prévi­sion de trajectoires.

Charles de Gaulle, tour de contrôle, salle IFR
Aéro­port Charles de Gaulle, tour de con­trôle, salle IFR © P. GILBERT — AÉROPORTS DE PARIS

La pre­mière erreur con­sis­terait à croire que l’on peut con­sid­ér­er les vitesses des avions comme con­stantes. En France, env­i­ron trois con­flits sur qua­tre com­pren­nent au moins un avion qui est en mon­tée ou en descente ; or, si l’on prend l’ex­em­ple d’un air­bus A320, il va en dix min­utes pass­er d’une alti­tude de 1 000 ft à une alti­tude de 26 000 ft, et sa vitesse va pass­er de 200 à 400 km/h.

La prévi­sion de tra­jec­toires pour­rait donc pass­er soit par la liai­son de don­nées, auquel cas le FMS de l’avion pour­rait ren­voy­er une tra­jec­toire rel­a­tive­ment pré­cise ; cepen­dant, cette prévi­sion resterait tout de même trib­u­taire d’in­cer­ti­tudes externes : si un avion de ligne est capa­ble de suiv­re pré­cisé­ment une route et une alti­tude, maîtris­er pré­cisé­ment sa vitesse sol n’est pas pos­si­ble en rai­son notam­ment des vents (une quin­zaine de nœuds).

Il est d’autre part impos­si­ble de cor­riger en per­ma­nence la vitesse car les réac­teurs ont un régime de con­som­ma­tion idéal dont il ne faut pas trop s’é­carter. Enfin, ils ne doivent pas, pour des raisons mécaniques, être soumis à des change­ments de régime permanents.

Enfin, s’il est impos­si­ble de récupér­er directe­ment les tra­jec­toires cal­culées par les FMS, on peut recourir à une sim­u­la­tion de tra­jec­toires faite à par­tir de mod­èles préétab­lis ; les incer­ti­tudes seront alors extrême­ment fortes, en rai­son de nom­breuses incon­nues (masse de l’avion, con­signes de la com­pag­nie, etc.).

Ain­si, il est à peu près incon­cev­able d’e­spér­er dépass­er la dizaine de min­utes en ter­mes d’hori­zon tem­porel pour la prévi­sion de trajectoires.

Différentes approches pour l’aide à la résolution

On peut grossière­ment class­er les dif­férentes approches de la façon suivante :

Approche anti-cal­cu­la­toire : la pre­mière approche con­siste à con­stru­ire un mod­èle, dit ” cog­ni­tif “, du con­trôleur, spé­ciale­ment dans ses modes d’ap­préhen­sion des paramètres du con­flit, et d’u­tilis­er ce mod­èle dans un cal­cu­la­teur afin de con­stru­ire des out­ils de fil­trage de l’in­for­ma­tion et d’as­sis­tance élec­tron­ique au con­trôleur. Cette méth­ode a l’im­mense avan­tage d’être facile­ment inté­grable au sys­tème de con­trôle actuel, car elle s’emploie à chang­er le moins pos­si­ble les modes opéra­toires existants.

Elle est cepen­dant sous les feux de deux cri­tiques, d’une part, les lim­i­ta­tions main­tenant bien con­nues pro­pres aux approches dites ” expertes ” ou ” cog­ni­tives ” : coût très élevé de développe­ment et de main­te­nance, prob­lème de général­i­sa­tion des maque­ttes au cas général, dégra­da­tion bru­tale de l’ex­per­tise aux lim­ites du domaine, fail­li­bil­ité du sys­tème expert [Dre79, Fox90] ; d’autre part, lais­sant l’homme totale­ment en charge de toutes les déci­sions, elle se con­tentera de repouss­er le ” mur de la capac­ité [Vil87] ” dont nous par­lions plus haut, sans faire dis­paraître les caus­es fon­da­men­tales de son exis­tence. Il s’ag­it donc d’une approche essen­tielle­ment à court ou moyen terme.

Automa­ti­sa­tion cen­tral­isée com­plète : il existe main­tenant des débuts de preuves mon­trant que la réal­i­sa­tion d’un sys­tème automa­tisé de con­trôle n’est pas une pure chimère. Dans une telle hypothèse, un sys­tème cen­tral gère l’ensem­ble des avions présents dans l’e­space, et leur donne les ordres de con­trôle néces­saires à la réso­lu­tion des con­flits. Cette approche a été abor­dée pour la pre­mière fois par le pro­jet AERA-III [Cel90, SPSS83, NFC+83, Nie89b, Nie89a, PA91] aux États-Unis, ou plus récem­ment le pro­jet ARC 2000 [K+89, FMT93, MG94] du Cen­tre expéri­men­tal Eurocontrol.

Le grand avan­tage de cette méth­ode est qu’elle per­met d’aug­menter de façon con­sid­érable la capac­ité de l’e­space, la flu­id­ité de l’é­coule­ment du traf­ic et per­met de garan­tir l’op­ti­mal­ité glob­ale des solu­tions obtenues. Le prin­ci­pal prob­lème est la tran­si­tion vers un tel sys­tème depuis le sys­tème actuel. Il ne peut donc s’a­gir que d’une approche à long ou très long terme.

Délé­ga­tion de tâch­es : dans ce cas, l’on tente de réalis­er un partage dynamique des tâch­es entre l’homme et la machine au sein d’un même secteur de con­trôle ; l’or­di­na­teur prendrait en charge cer­tains con­flits et lais­serait l’homme en charge du traf­ic restant. Cette méth­ode pour­rait être intéres­sante à moyen terme : elle devrait per­me­t­tre de soulager l’opéra­teur en cas de pointe de traf­ic tout en main­tenant sa vig­i­lance et ses qual­i­fi­ca­tions. L’in­con­vénient majeur est qu’elle sup­pose une totale con­fi­ance de l’homme envers le cal­cu­la­teur, et envers la répar­ti­tion de traf­ic et les réso­lu­tions qu’il exé­cute. Trop peu d’ex­péri­men­ta­tions ont été menées jusqu’i­ci pour pou­voir conclure.

Approche autonome : dans ce type d’ap­proche, on sup­pose que les avions se trou­vant dans une cer­taine zone de l’e­space (par exem­ple au-dessus de 32 000 ft) utilisent des senseurs et des algo­rithmes embar­qués pour réalis­er eux-mêmes la détec­tion et la réso­lu­tion de con­flits. Déjà exam­inée dans le cadre du pro­jet ATLAS [DA93], le Cen­tre expéri­men­tal d’Eu­ro­con­trol tra­vaille dans le cadre du pro­jet FREER à la déf­i­ni­tion d’al­go­rithmes pou­vant per­me­t­tre la réal­i­sa­tion de ce type de sys­tème ; les doc­u­ments définis­sant les divers­es straté­gies de R&D font d’ailleurs une place impor­tante à ce type de méthodes. 

Son prin­ci­pal avan­tage est sa rel­a­tive com­pat­i­bil­ité avec le sys­tème actuel : sa mise en place pour­rait se faire pro­gres­sive­ment par une tac­tique d’encer­clement (en com­mençant par les espaces transocéaniques et les espaces supérieurs). D’autre part, elle per­me­t­trait de don­ner aux avions les tra­jec­toires directes orig­ine-des­ti­na­tion qu’ils deman­dent à l’in­térieur de ces zones ” libres “.

Il sub­siste cepen­dant de nom­breux prob­lèmes : d’une part, chaque avion n’a qu’une vision lim­itée du monde qui l’en­toure ; il est donc par­faite­ment sus­cep­ti­ble de choisir des manœu­vres d’évite­ment à court terme qui peu­vent se révéler désas­treuses sur le long terme, soit en ter­mes de sécu­rité, soit en ter­mes d’ef­fi­cac­ité ; il n’ex­iste encore aujour­d’hui aucun algo­rithme ayant prou­vé son effi­cac­ité sur des échan­til­lons de traf­ic réel. Enfin, les prob­lèmes d’in­ter­face entre les zones ” libres ” et les zones con­trôlées ont été peu abordés.

Notons enfin que ce type d’ap­proche est par­fois con­fon­du avec l’A­CAS (Air­borne Col­li­sion Avoid­ance Sys­tem) ; ceci mérite une petite pré­ci­sion. L’ACAS, et par­ti­c­ulière­ment son implan­ta­tion actuelle à bord des avions : le TCAS [TCA90], est un sys­tème embar­qué conçu pour faire de l’évite­ment à très court terme (de l’or­dre de la minute). Il s’ag­it avant tout d’un sys­tème de dernier sec­ours pour éviter des col­li­sions, et non d’un moyen de con­trôle ou de main­tien de séparation.

En fait, le dilemme dans lequel nous nous trou­vons enfer­més est un peu le suiv­ant : les out­ils capac­i­tifs sont dif­fi­cile­ment inté­grables dans le sys­tème actuel, et les out­ils facile­ment inté­grables risquent fort d’être peu capacitifs.

La résolution de conflits

Complexité théorique

Résoudre un con­flit impli­quant n avions con­siste dans le meilleur des cas à assur­er les sépa­ra­tions en don­nant aux avions des ordres de manœu­vre, tout en min­imisant les allonge­ments de tra­jec­toire liés aux dévi­a­tions induites.

La dif­fi­culté du prob­lème est assez facile à appréhen­der. Pour un con­flit à deux avions dans le plan hor­i­zon­tal, l’e­space des solu­tions admis­si­bles com­prend deux com­posantes con­nex­es (à con­di­tion que les avions ne fassent pas de boucles) : soit l’avion 1 passe devant l’avion 2, soit il passe der­rière. Un clus­ter à n avions con­tient n(n‑1)/2 paires d’avions. Le nom­bre théorique de com­posantes con­nex­es est alors de 2 puis­sance n(n‑1)/2. Ceci explique l’échec des méth­odes d’op­ti­mi­sa­tion locale sur ce type de problème.

Des ten­ta­tives d’é­val­u­a­tion de la com­plex­ité théorique ont été faites. Il sem­ble prob­a­ble qu’il s’ag­it d’un prob­lème NP-com­plet, une classe de prob­lèmes n’ad­met­tant aujour­d’hui aucun algo­rithme poly­no­mi­al les résolvant.

Modèle de manœuvre et d’incertitude

Les ordres de manœu­vre don­nés aux avions doivent être facile­ment com­préhen­si­bles et exé­cuta­bles par les pilotes. On peut, dans le cadre d’une mod­éli­sa­tion rel­a­tive­ment sim­ple, se lim­iter à la typolo­gie suivante :

Fig­ure 2 – Mod­èle de manoeu­vre et d’incertitude​
Modèle de manoeuvre et d’incertitude
  • dans le plan hor­i­zon­tal, un avion peut mod­i­fi­er son cap d’un angle s valant 10, 20 ou 30 degrés à l’in­stant t0 et repren­dre la direc­tion de sa des­ti­na­tion finale à tt (fig­ure 2) ;
  • dans le plan ver­ti­cal, le type de manœu­vre dépend de la phase de la tra­jec­toire de l’avion :
    — pen­dant la mon­tée, on peut inter­rompre la tra­jec­toire à t0 et repren­dre la mon­tée à t1,
    — pen­dant la phase de croisière, on peut descen­dre de 1 000 ft à t0 et repren­dre à t1,
    — la phase de préde­s­cente com­mence une cinquan­taine de milles nau­tiques avant le début de la descente. On peut alors anticiper la descente en t0 et sta­bilis­er l’avion à t1,
    — au cours de la descente, aucune manœu­vre n’est pos­si­ble dans le plan vertical.


Pour tenir compte des incer­ti­tudes sur les vitesses, on peut mod­élis­er les avions non par des points matériels mais par des poly­gones con­vex­es. La taille des poly­gones aug­mente dans la direc­tion de la vitesse. On passe ain­si d’un point t = 0 à un seg­ment, puis un par­al­lélo­gramme, puis un hexa­gone, etc. Il suf­fit alors de véri­fi­er, pour que la con­trainte hor­i­zon­tale soit respec­tée, que les con­vex­es qui mod­élisent les avions soient séparés par la sépa­ra­tion stan­dard (voir fig­ure 2).

Dans le plan ver­ti­cal, l’in­cer­ti­tude est beau­coup plus forte, on maîtrise très mal le taux de mon­tée d’un avion qui dépend de paramètres aus­si var­iés que la masse, ou la mise en route de la cli­ma­ti­sa­tion. En con­séquence, le même principe que dans le plan hor­i­zon­tal est repris mais les incer­ti­tudes sont beau­coup plus grandes. On com­prend mieux, en regar­dant la fig­ure 2, l’im­por­tance de la qual­ité de la prévi­sion : les con­vex­es con­tenant l’en­veloppe des posi­tions pos­si­bles crois­sent rapi­de­ment, et si les incer­ti­tudes sont trop fortes, le nom­bre d’avions en con­flits poten­tiels devient en quelques min­utes très, voire trop, impor­tant. D’autre part, une mau­vaise prévi­sion peut amen­er à résoudre des con­flits qui n’au­raient en fait pas lieu. Enfin, l’in­stant de début de manœu­vre est com­plète­ment dépen­dant de la qual­ité de la prévi­sion et son choix en est ren­du par­ti­c­ulière­ment difficile.

Techniques de résolution

On peut trou­ver plusieurs approches pour abor­der le prob­lème de réso­lu­tion de conflits.

N. Durand [Dur96] traite le prob­lème comme un prob­lème de com­mande opti­male, F. Médioni [MDA94] pro­pose un mod­èle per­me­t­tant de le trans­former en prob­lème linéaire, celui-ci demeu­rant forte­ment com­bi­na­toire. É. Féron [OSF97] pro­pose d’u­tilis­er des algo­rithmes de relax­ation con­vexe du prob­lème com­bi­na­toire ini­tial. Toutes ces tech­niques con­sid­èrent le prob­lème comme global.

Une autre approche con­siste à con­sid­ér­er le prob­lème des con­flits à n avions comme un prob­lème sépara­ble : des méth­odes d’op­ti­mi­sa­tion sont appliquées suc­ces­sive­ment sur cha­cun des avions impliqués ; il s’ag­it alors de résoudre n prob­lèmes rel­a­tive­ment sim­ples et non un seul prob­lème de grande taille, ceci au détri­ment de la qual­ité des solutions.

Enfin, une dernière méth­ode tend à employ­er des tech­niques de type réac­t­if : dans ce cas, la notion d’op­ti­mal­ité dis­paraît com­plète­ment et l’on ne retient que l’ad­mis­si­bil­ité des trajectoires.

Nous allons rapi­de­ment présen­ter quelques exem­ples de ces dif­férentes approches.

Un exemple de méthode globale de résolution

Si l’on dis­pose de toutes les infor­ma­tions con­cer­nant l’ensem­ble des avions, et que l’on peut agir à sa guise sur un avion plutôt que l’autre, le prob­lème de la réso­lu­tion de con­flits est un prob­lème d’op­ti­mi­sa­tion glob­ale : pour un con­flit à n avions, et suiv­ant la mod­éli­sa­tion présen­tée ci-dessus, il s’ag­it d’op­ti­miser 3n vari­ables cor­re­spon­dant aux t0, t1 et s de chaque avion.

Pour un élé­ment com­posé de 3n vari­ables, la fonc­tion d’é­val­u­a­tion à opti­miser simule les tra­jec­toires (avec incer­ti­tudes) sur T min­utes à venir, mesure les con­flits et s’il n’y a pas de con­flit, prend en compte le retard dû aux manœu­vres, la durée des manœu­vres et le nom­bre total de manœu­vres. Une solu­tion sans con­flit est tou­jours préférée à une solu­tion avec con­flit. On min­imis­era le nom­bre de manœu­vres pour lim­iter le tra­vail des pilotes, la durée des manœu­vres pour libér­er les avions le plus tôt pos­si­ble pour une éventuelle autre manœuvre.

Il existe de nom­breuses méth­odes d’op­ti­mi­sa­tion glob­ale sus­cep­ti­bles d’être appliquées à ce prob­lème : branch and bound par inter­valles, algo­rithmes A*, recuit simulé, etc. Par­mi les dif­férentes méth­odes, les algo­rithmes géné­tiques9 ont la par­tic­u­lar­ité de ne pas requérir d’hy­pothèse sur la fonc­tion à opti­miser (qui peut être le résul­tat d’une sim­u­la­tion), et de pou­voir fournir en un temps don­né plusieurs solu­tions proches de l’op­ti­mum. Par ailleurs, par­mi les algo­rithmes que nous avons testés seules les méth­odes géné­tiques per­me­t­tent de pren­dre en compte des con­flits de grande taille pou­vant aller jusqu’à une trentaine d’avions [DA96].

Fig­ure 3 – Archi­tec­ture générale

L’ar­chi­tec­ture générale de l’al­go­rithme est la suiv­ante (fig­ure 3) :

  • le proces­sus P1 est un sim­u­la­teur de traf­ic qui gère l’ensem­ble des vols pas­sant au-dessus de la France sur une journée,
  • le proces­sus P2 est chargé de détecter les paires d’avions en con­flit, de fab­ri­quer les clus­ters d’avions par fer­me­ture tran­si­tive des paires d’avions en con­flit. Il véri­fie égale­ment les tra­jec­toires nou­velles pro­posées par P3,
  • le proces­sus P3 est l’al­go­rithme de réso­lu­tion de con­flits pro­pre­ment dit.


Cet algo­rithme a été testé sur du traf­ic réel dans le cadre de sim­u­la­tions [DA97]. Pour une journée com­prenant 6 388 vols, et en prenant une incer­ti­tude de +/- 5 % dans le plan hor­i­zon­tal et +/- 10 % dans le plan ver­ti­cal, l’al­go­rithme résout tous les con­flits (1 694) qui se présen­tent au-dessus de 10 000 pieds. Le retard moyen lié aux manœu­vres sur l’ensem­ble des avions est de 5 sec­on­des, et le retard max­i­mal inférieur à 4 minutes.

Méthode ” diviser pour régner ”

Dans ce cadre, pour un prob­lème à n avions, on cherche à résoudre suc­ces­sive­ment n prob­lèmes à trois vari­ables, plutôt qu’un seul prob­lème à 3n variables.

Fig­ure 4 – Exem­ple de résolution
Exemple de résolution de conflits de trajectoires d'avions

Dans un pre­mier temps, on choisit une pri­or­ité entre les n avions pour savoir dans quel ordre ils vont con­stru­ire leur tra­jec­toire, puis cha­cun d’en­tre eux con­stru­it ladite tra­jec­toire en prenant comme con­traintes les avions déjà présents au moment où il résout. On peut employ­er là aus­si divers­es méth­odes pour fab­ri­quer les tra­jec­toires [AD97, MDA98]. Le prob­lème est rel­a­tive­ment clas­sique en robo­t­ique, et des méth­odes rel­a­tive­ment élé­men­taires comme les algo­rithmes A* peu­vent en venir aisé­ment à bout dans des temps raisonnables.

On peut voir sur la droite de la fig­ure 4 un tel exem­ple de réso­lu­tion. Le dernier avion est large­ment pénal­isé par rap­port aux autres. D’autre part, si l’on com­pare cette solu­tion à celle obtenue par la méth­ode glob­ale (à gauche de la fig­ure), on con­state qu’il est pos­si­ble de trou­ver une solu­tion de bonne qual­ité pour tous les avions et qui n’en pénalise grave­ment aucun.

En fait, cette méth­ode peut même ne trou­ver aucune solu­tion admis­si­ble, alors que la méth­ode glob­ale en trou­vera plusieurs. Ain­si, dans le sim­ple cadre d’un con­flit à trois avions, l’al­go­rithme échouera si les angles de con­ver­gence sont faibles et si, de plus, les pri­or­ités au point de pas­sage sont mal choisies. Le prob­lème se trou­ve ain­si en par­tie reporté sur le choix de l’or­dre de réso­lu­tion, ce qui est loin d’être simple.

Méthodes réactives

Le doc­u­ment le plus intéres­sant est cer­taine­ment [Zeg94]. Il intro­duit la notion de coor­di­na­tion d’ac­tions grâce à dif­férentes forces qui s’ex­er­cent sur les agents, dans notre cas les avions. 

Fig­ure 5 – Force répul­sive et force glis­sante, forces de glisse­ment coordonnées
Force répulsive et force glissante, forces de glissement coordonnées

La méth­ode, ini­tiale­ment dévelop­pée dans le domaine de la robo­t­ique ([Khat­ib]), se base sur l’analo­gie physique d’une charge dans un champ de poten­tiel. Pour l’évite­ment, le poten­tiel est une mesure du risque de col­li­sion. On définit ain­si trois types de forces qui devront agir suiv­ant l’urgence :

  • les forces attrac­tives qui per­me­t­tent aux avions d’at­tein­dre leur objec­tif (une balise ou leur des­ti­na­tion finale par exemple),
  • les forces répul­sives qui per­me­t­tent aux avions d’éviter un obsta­cle proche donc dan­gereux. Cet obsta­cle peut être un avion ou une zone interdite,
  • les forces de glisse­ment qui per­me­t­tent de con­tourn­er les obstacles.


Les avions ont alors une action coor­don­née (voir fig­ure 5). Une force de glisse­ment est définie de la manière suiv­ante : si l’on observe l’équipo­ten­tielle de dan­ger pas­sant par l’avion, une force de glisse­ment est tan­gente à cette équipo­ten­tielle, alors que la force répul­sive est nor­male. Il y a donc plusieurs forces de glisse­ment pos­si­bles. Si l’on reste dans le plan hor­i­zon­tal, la fig­ure 5 mon­tre que l’on peut définir deux sens de glisse­ment (droite ou gauche). Le sens opti­mal (il s’ag­it ici d’op­ti­mal­ité locale, pour l’avion con­cerné) est celui qui favorise le rap­proche­ment vers l’objectif.

Dans le cas d’un obsta­cle mobile, on définit une action coor­don­née d’évitement.

Pour traiter les con­flits à plus de deux avions, on addi­tionne les forces rel­a­tives à chaque avion, con­for­mé­ment au mod­èle physique (addi­tion des poten­tiels). Si les résul­tats pra­tiques sont bons pour de faibles den­sités, les expéri­ences menées dans le cadre de fortes den­sités sem­blent mon­tr­er un effon­drement rapi­de du sys­tème qui en vient à génér­er plus de con­flits qu’il n’en résout. Ceci est lié à la mécon­nais­sance des inten­tions des avions ain­si qu’à la vis­i­bil­ité lim­itée de l’en­vi­ron­nement ; dif­férentes amélio­ra­tions per­me­t­tent de pal­li­er par­tielle­ment ces prob­lèmes, sans toute­fois par­venir à les résoudre [Bos97].

Conclusion

Au terme de ce rapi­de sur­vol, il faut avant tout sig­naler que la recherche dans le domaine du traf­ic aérien est une activ­ité extrême­ment récente. Les tech­niques présen­tées ici ont besoin d’être soumis­es à l’épreuve du monde opéra­tionnel pour être validées.

Pour­tant, il sem­ble que les bonnes ques­tions com­men­cent à être posées ; l’aug­men­ta­tion du traf­ic et les con­traintes économiques ren­dront néces­saires une sérieuse évo­lu­tion des tech­niques de ges­tion du traf­ic aérien. Cer­taines répons­es sci­en­tifique­ment étayées com­men­cent à être apportées aux prob­lèmes posés ; il faut cepen­dant se rap­pel­er que la valeur tech­nique d’une solu­tion ne sera pas le seul critère inter­venant dans les choix qui seront faits dans les années à venir : d’autres fac­teurs comme l’ac­cept­abil­ité ou la facil­ité de tran­si­tion seront cer­taine­ment plus déterminants.

_________________________________
1. Flight Man­age­ment System.
2. Glob­al Posi­tion­ing System.
3. 1 mille nau­tique vaut 1 852 m (1 minute d’arc sur un méridien).
4. Elle est de 8 NM en France mais devrait bien­tôt descen­dre à 5 NM.
5. 1 pied vaut 30,48 cm.
6. Elle vaut 1 000 ft au-dessous du FL 290 et 2 000 au-dessus.
7. Il ne peut y avoir de cer­ti­tude lorsque l’on traite de la prévi­sion de tra­jec­toires, les avions étant soumis à de nom­breux fac­teurs non com­plète­ment con­nus, comme le vent, par exemple.
8. On estime générale­ment que la charge de tra­vail est pro­por­tion­nelle au nom­bre d’avions dans le secteur, aux flux entrant et sor­tant, et au nom­bre de con­flits qui se pro­duisent dans le secteur. Le mod­èle théorique mon­tre que le nom­bre de con­flits devrait vari­er avec le car­ré du nom­bre d’avions. Les sim­u­la­tions mon­trent en fait qu’il croît, beau­coup plus rapi­de­ment, en rai­son de l’or­gan­i­sa­tion du traf­ic réel, ce qui ne manque pas d’inquiéter.
9. Les algo­rithmes géné­tiques sont des algo­rithmes d’op­ti­mi­sa­tion s’ap­puyant sur des tech­niques dérivées de la géné­tique et de l’évo­lu­tion naturelle : croise­ments, muta­tions, sélec­tion, etc. Ils ont déjà une his­toire rel­a­tive­ment anci­enne puisque les pre­miers travaux de John Hol­land sur les sys­tèmes adap­tat­ifs remon­tent à 1962 [Hol62].

Références

  • [AD97] Jean-Marc Alliot and Nico­las Durand. Using A* algo­rithms to solve ATC con­flicts. Tech­ni­cal report, École nationale de l’avi­a­tion civile, 1997.
  • [Bos97] Jean-François Bosc. Tech­niques d’évite­ment réac­t­if et sim­u­la­tion du traf­ic aérien. Thèse de doc­tor­at, École nationale de l’avi­a­tion civile, 1997.
  • [Cel90] Joseph C. Celio. Con­troller per­spec­tive of AERA 2. Tech­ni­cal report, MITRE, Feb­ru­ary 1990. MP-88W00015.
  • [cotRbod95] Select com­mit­tee of the RTCA board of direc­tors. Free Flight. Tech­ni­cal report, RTCA, 1995.
  • [DA93] Nico­las Durand and Jean-Marc Alliot. Exist­ing algo­rithms for col­li­sion avoid­ance, and what the future might hold. Tech­ni­cal report for the ATLAS project, CENA, 1993.
  • [DA96] N. Durand and J.-M. Alliot. Réso­lu­tion de con­flits aériens par algo­rithmes géné­tiques. Revue de l’As­so­ci­a­tion Aéro­nau­tique et Astro­nau­tique de France, 1996.
  • [DA97] Nico­las Durand and Jean-Marc Alliot. Opti­mal res­o­lu­tion of en route con­flicts. In Pro­ceed­ings of Europe-USA con­fer­ence on Air Traf­fic Man­age­ment, 1997.
  • [Dre79] Hubert Drey­fus. What com­put­ers can’t do : the lim­its of arti­fi­cial intel­li­gence. Harp­er and Row, 1979. ISBN : 0–06-090624–3.
  • [Dur96] Nico­las Durand. Opti­mi­sa­tion de tra­jec­toires pour la réso­lu­tion de con­flit en route. Thèse de doc­tor­at, INPT, 1996.
  • [FMT93] Xavier Fron, Bernard Maudry, and Jean-Claude Tumelin. Arc 2000 : Auto­mat­ic radar con­trol. Tech­ni­cal report, Euro­con­trol, 1993.
  • [Fox90] Mark Fox. AI and Expert Sys­tems : Myths, Leg­ends and Facts. IEEE Expert, févri­er 1990.
  • [Hol62] John Hol­land. Out­line for a log­i­cal the­o­ry of adap­tive sys­tems. Jour­nal of the Asso­ci­a­tion of Com­put­ing Machin­ery, 3, 1962.
  • [K+89] Fred Krel­la et al. Arc 2000 sce­nario (ver­sion 4.3). Tech­ni­cal report, Euro­con­trol, April 1989.
  • [Kha86] Ous­sama Khat­ib. Real-time obsta­cle avoid­ance for manip­u­la­tors and mobile robots. The Inter­na­tion­al Jour­nal of Robot­ics Research, 5 (l) : 90–98, 1986.
  • [MDA94] Frédéric Médioni, Nico­las Durand, and Jean-Marc Alliot. Algo­rithmes géné­tiques et pro­gram­ma­tion linéaire appliqués à la réso­lu­tion de con­flits aériens. In Pro­ceed­ings of the Journees Evo­lu­tion Arti­fi­cielle Fran­coph­o­nes. EAF, 1994.
  • [MDA98] Frédéric Médioni, Nico­las Durand, and Jean-Marc Alliot. Branch and bound opti­mi­sa­tion using inter­val meth­ods applied to con­flict solv­ing. Pro­ceed­ings of Inter­vals’ 98 con­fer­ence, 1998.
  • [MG94] Dr. C. Meck­iff and Dr. P. Gibbs. PHARE : High­ly inter­ac­tive prob­lem solver. Tech­ni­cal report, Euro­con­trol, 1994.
  • [NFC+83] W. P. Niedring­haus, I. Frol­ow, J. C. Corbin, A. H. Gisch, N. J. Taber, and F. H. Leiber. Auto­mat­ed En Route Air Traf­fic Con­trol Algo­rith­mic Spec­i­fi­ca­tions : Flight Plan Con­flict Probe. Tech­ni­cal report, FAA, 1983. DOT/FAA/ES-83/6.
  • [Nie89a] W. P. Niedring­haus. Auto­mat­ed plan­ning func­tion for AERA 3 : Maneu­ver Option Man­ag­er. Tech­ni­cal report, FAA, 1989. DOT/FAA/DS-89/21.
  • [Nie89b] W. P. Niedring­haus. A math­e­mat­i­cal for­mu­la­tion for plan­ning auto­mat­ed air­craft sep­a­ra­tion for AERA 3. Tech­ni­cal report, FAA, 1989. DOT/FAA/DS-89/20.
  • [OSF97] Jae-Hyuk Oh, J. Marc Shew­chun, and Éric Féron. Design and analy­sis of con­flict res­o­lu­tion algo­rithms via pos­i­tive semi­def­i­nite pro­gram­ming. Tech­ni­cal report, Mass­a­chu­setts Insti­tute of Tech­nol­o­gy, Cam­bridge, MA 02139, 1997.
  • [PA91] Tekla S. Per­ry and John A. Adam. Improv­ing the world’s largest, most advanced sys­tem ! IEEE Spec­trum, Feb­ru­ary 1991.
  • [SPSS83] E. M. Schus­ter, F. R. Pet­ros­ki, R. K. Sci­ambi, and M. MC Stokrp. AERA 2 func­tion­al design and per­for­mance descrip­tion. Tech­ni­cal report, MITRE, Sep­tem­ber 1983. MtR-83W136.
  • [TCA90] TCAS-III col­li­sion avoid­ance algo­rithms ver­sion 3. Tech­ni­cal report, The MITRE Cor­po­ra­tion, Novem­ber 1990.
  • [TM+97] ATMRD Paul Thomas, Bernard Miailler, et al. ATM R&D Strat­e­gy. Tech­ni­cal report, Euro­con­trol, 1997.
  • [Vil87] Jacques Vil­liers. L’in­tel­li­gence arti­fi­cielle dans le con­trôle de la cir­cu­la­tion aéri­enne. ITA Mag­a­zine, 43 : 7–14, mai-juin 1987.
  • [Zeg94] Karim Zeghal. Vers une théorie de la coor­di­na­tion d’ac­tions, appli­ca­tion à la nav­i­ga­tion aéri­enne. Thèse de doc­tor­at, Uni­ver­sité Paris VI, 1994.

Poster un commentaire