Chapter 3 Optimisation de la résolution de conflits

Introduction

Le but premier du contrôle du trafic aérien est d'assurer la sécurité des aéronefs. Avant toute chose, nous allons introduire le vocabulaire indispensable à la description du problème :

Contrôle en route :

il s'agit du contrôle à l'extérieur des zones entourant les aéroports (dans ces zones, on parle de contrôle d'approche). Les avions utilisent alors le plus souvent des routes préétablies, les couloirs aériens (en anglais airways). Ces couloirs sont des tubes de sections rectangulaires. Historiquement, les routes ont été définies comme étant les segments de droite reliant les balises. Ces balises étaient généralement des moyens de radionavigation vers lesquels se dirigeaient les avions. C'est souvent autour de ces balises qu'apparaissent des conflits ; en effet, elles se situent souvent aux intersections des différentes routes.

Ces routes contournent les parties d'espace réservées aux militaires et permettent aux contrôleurs d'avoir une visualisation plus aisée de la situation spatiale des avions.

Plan de vol :

il contient tous les éléments indicatifs décrivant le vol prévu pour un avion. Ces informations sont déposées avant le départ auprès des services ATC avec, notamment, les éléments suivants :

l'heure de départ ;
le niveau de vol ¹ demandé pour la croisière ;
la route prévue : elle est décrite par une série de balises.

Séparations :

on définit une distance horizontale, qui est exprimée en milles nautiques ² (Nm), la séparation horizontale, et une distance verticale, qui, elle, est exprimée en pieds ³ (ft) : la séparation verticale. On dit que deux avions sont séparés quand la distance qui sépare leurs projections sur un plan horizontal est supérieure à la séparation horizontale OU quand la distance qui sépare leurs projections sur un plan vertical est supérieure à la séparation verticale. Ces séparations peuvent être différentes selon le type de zone dans laquelle se trouvent les avions, ou selon les outils de contrôle dont on dispose. Dans le cas du trafic en route, qui nous occupe ici, la séparation horizontale est généralement de 8 Nm en France mais devrait bientôt descendre à 5 Nm. La séparation verticale vaut 1000 ft au dessous du FL 290 et 2000 au dessus.

Conflit élémentaire :

deux avions sont dits en conflit quand ces avions ne sont plus séparés, c'est à dire quand les distances séparant leurs projections sur un plan horizontal et sur un plan vertical sont inférieures respectivement à la séparation standard horizontale ET à la séparation standard verticale. De façon plus générale, si l'on se fixe une durée T, deux avions seront dits en conflit potentiel pendant T si durant le temps T ils ont une probabilité non nulle d'être en conflit.

Cluster :

un cluster d'avions est une fermeture transitive d'avions en conflits potentiels. Si l'avion A est en conflit potentiel avec l'avion B et si l'avion B est en conflit potentiel avec les avions C et D, alors on dit que les avions A, B, C et D appartiennent au même cluster. On trouvera par la suite l'expression conflit à n avions qui signifie en fait cluster à n avions.

Le rôle du contrôleur est donc de prévenir les risques de conflit en donnant aux avions des ordres de contrôle (changement de cap ou d'altitude, etc.) permettant d'éviter les conflits.

Mais la gestion du trafic aérien ne se réduit pas à la seule action du contrôleur sur les avions. Il s'agit en fait d'un système complexe que l'on peut décrire comme une succession de cinq filtres agissant à des niveaux différents :

Organisation à long terme :

c'est le filtre le plus grossier. Son but n'est pas au sens strict d'éviter des conflits mais plutôt d'organiser le trafic de façon macroscopique à moyen et long terme (supérieur à 6 mois). On peut citer à titre d'exemple, les schémas d'orientation de trafic, les mesures du Comité des horaires ou encore, les accords inter-centres et les accords avec les militaires qui permettent aux civils d'utiliser leurs zones aériennes pour écouler les pointes de trafic du vendredi après-midi .

Organisation à court terme :

on parle souvent de pré-régulation. Il consiste à organiser une journée de trafic j la veille (j-1) ou l'avant-veille (j-2). On dispose pour cela de données relativement précises :

les plans de vol déjà connus ;
la capacité de contrôle que peut offrir chaque centre en fonction des effectifs qui seront présents le jour j ;
le nombre d'avions maximum pouvant se trouver dans un même secteur au même instant, encore appelé capacité du secteur ;
les données des années et des semaines précédentes. En effet, le trafic aérien est relativement répétitif : le lundi ressemble au lundi de la semaine passée, le pont de l'Ascension ressemble à celui de l'année passée, etc. Ceci permet de prévoir où vont apparaître les congestions, la capacité qu'il va falloir mettre en oeuvre pour répondre à la demande, voire éventuellement les mesures plus contraignantes à prendre.

Ce filtre a non seulement une action macroscopique car il organise les flux de trafic en fonction des capacités offertes mais également une action ponctuelle sur chaque avion en gérant les créneaux de décollage ⁴ . Effectué au niveau national jusqu'en 1995, ce filtrage est maintenant fait au niveau européen pour obtenir une meilleure coordination. C'est le rôle de la CFMU ⁵ .

Régulation en temps réel :

il consiste à organiser les différents flux en tenant compte des événements du jour. Il s'agit plutôt de mesures d'ajustement qui prennent en compte des événements encore mal connus la veille. Ainsi, le trafic transatlantique est mal connu à j-1 mais est bien connu entre 3 à 6 heures avant son arrivée. La fraction de la capacité offerte qui avait été réservée par la pré-régulation peut alors être adaptée. On peut envoyer sur d'autres centres les avions supplémentaires ou augmenter le nombre de vols non transatlantiques traités par le centre s'il y a moins de vols transatlantiques que prévu. De la même façon, on peut ré-allouer des créneaux horaires non utilisés pour une raison quelconque (retard ou incident technique) ou tenir compte de la météo du jour (terrains inaccessibles par exemple). Ce rôle est en général joué par les FMP ⁶ dans chaque centre.

Tactique :

c'est le dernier filtre de la chaîne du contrôle aérien : l'action du contrôleur sur son secteur. Le temps moyen passé par un avion dans un secteur est de l'ordre d'une quinzaine de minutes. La visibilité du contrôleur est un peu supérieure puisqu'il dispose des plans de vol quelques minutes avant l'entrée de l'avion dans le secteur.

La détection et surtout la résolution des conflits ne sont absolument pas automatisées. Les contrôleurs sont donc entraînés à reconnaître des types de conflits et à appliquer à ces derniers des manoeuvres connues. Le contrôleur ne peut éviter les conflits qu'en jouant sur la trajectoire des avions. Pour cela, il dispose de quatre types d'ordres :

des déviations de cap ;
des paliers intermédiaires pour les avions en montée ou en descente ;
des changements de niveaux de vol.
des mesures de régulation de vitesse (essentiellement sur des avions en descente) ;

Cependant les résolutions proposées ne sont pas toujours optimales. En outre, une fois une manoeuvre d'évitement choisie, le contrôleur doit également surveiller les avions impliqués pour vérifier que tout se passe bien. Tout ceci se fait au détriment de la charge ⁷ de travail du contrôleur et affecte donc la capacité du secteur dont il est responsable.

Urgence :

Ce filtre n'est censé intervenir que lorsque le système de contrôle est absent ou a été défaillant. L'objet de ce filtre n'est plus de séparer les avions (il est trop tard dans la plupart des cas) mais plutôt d'éviter une collision présumée. La prédiction temporelle est inférieure à la minute et varie entre 25 et 40 secondes. Il est trop tard pour que le contrôleur intervienne puisque l'on estime qu'il lui faut entre 1 et 2 mn pour analyser une situation, trouver une solution et la communiquer aux avions. Actuellement, cette fonction est assurée par le TCAS ⁸ qui détecte les avions environnants et donne un ordre de résolution au pilote (pour le moment dans le plan vertical).

Ce filtre doit résoudre les conflits non prévisibles comme par exemple dans le cas où un avion dépasse un niveau de vol donné par le contrôle ou dans le cas d'un accident technique qui dégraderait notablement les performances de l'avion.

Depuis 1980, le contrôle du trafic aérien connaît une progression régulière, qui fait craindre une saturation de l'espace. De plus, le nombre de données à traiter augmentera encore avec la mise en place de nouveaux moyens de communication entre le sol et les avions (Data-Link). Parallèlement, les avions s'équipent de moyens sophistiqués de navigation (FMS ⁹ , GPS ¹⁰ ) permettant des tenues plus précises de trajectoires.

Dans ce cadre, il faut s'interroger sur l'évolution des techniques de contrôle pour les années à venir. On se retrouve alors pris entre deux positions caricaturales : l'automatisation complète ou le refus complet de toute automatisation. Les tenants de l'une et l'autre approche ont des discours qui relèvent plus de l'émotionnel que du rationnel. On peut cependant penser que :

Le refus de toute automatisation est une politique à courte vue ; l'opérateur humain est actuellement le goulot d'étranglement du système de contrôle. On peut certes espérer améliorer ses capacités de traitement en améliorant la présentation des informations ; mais si l'augmentation du trafic se poursuit dans les mêmes proportions, il faudra déléguer au moins partiellement les tâches de résolution et de surveillance à la machine.
Une automatisation complète est irréaliste dans le contexte actuel, pour tout un ensemble de raisons ; certaines ont un caractère politique ou social : la transition d'un contrôle où l'homme a une responsabilité complète à un contrôle où il n'aurait qu'une activité de supervision pose de sérieux problèmes éthiques. D'autre part, il n'existe pour l'instant aucun système capable de résoudre l'ensemble des problèmes techniques qui se posent dans ce cadre.

La voie moyenne consiste sans doute à penser un système qui, dans un premier temps, serait susceptible de fournir une aide à la détection et à la résolution des conflits, et pourrait, à la demande de l'opérateur, effectuer automatiquement certaines résolutions. Le Centre d'Etudes de la Navigation Aérienne s'est intéressé à cette hypothèse dans le cadre de certains de ses projets, comme SPECTRA[Pla93].

D'autres projets, comme ARC-2000 (développé par le Centre Expérimental Eurocontrol de Brétigny), ont exploré des voies plus futuristes, tout en souhaitant utiliser dans les systèmes de contrôle actuels les algorithmes et concepts développés par des équipes de recherche pour les systèmes de contrôle du futur. Les problèmes d'évolution des systèmes de contrôle sont discutés plus en détail dans [DAM93], et l'on trouvera un large panorama des différents projets d'automatisation dans [Dur96].

Dans tous les cas, il faut savoir prévoir les trajectoires des avions, détecter les conflits, regrouper ces conflits par paquets, et donner des manoeuvres simples les résolvant, etc. Ces problèmes sont aujourd'hui identifiés, mais les techniques à employer pour les résoudre le sont moins. On peut globalement classer les approches employés pas les différentes équipes en deux catégories, qui ne sont d'ailleurs pas sans rappeler deux écoles de pensée du monde de l'Intelligence Artificielle :

la première approche consiste à construire un modèle, dit ``cognitif'', du contrôleur, spécialement dans ses modes d'appréhension des paramètres du conflit, et d'utiliser ce modèle dans un calculateur afin de construire des outils de filtrage de l'information et d'assistance électronique au contrôleur. Cette approche (à laquelle l'auteur de ces lignes participa fort modestement à ses débuts [LA91], alors qu'il terminait sa thèse de doctorat au sein de l'équipe ``formalisation du raisonnement'' à l'Institut de Recherche en Informatique de Toulouse) possède le grand avantage d'être facilement admissible pour un contrôleur actuellement en activité : en effet, il n'aura pas à changer son mode opératoire, puisque la machine sera censée le reproduire. Pourtant, cette problématique souffre directement des limitations propres aux approches dites ``expertes'' : coût très élevé de développement et de maintenance, problème de généralisation des maquettes au cas général, dégradation brutale de l'expertise aux limites du domaine, faillibilité du système expert, etc. Ces problèmes ont été mis en évidence dans de nombreux domaines, et sont largement présentés et discutés dans la littérature spécialisée depuis de nombreuses années maintenant ([Dre84, Dre79, Dre87, Fox90, Dav82]), nous n'y reviendrons pas ici ¹¹ . Ils semblent néanmoins justifier que l'on n'applique ce type d'approche qu'aux problèmes sur lesquels les approches plus classiques ne sauraient donner de résultats probants.
La seconde approche, que nous qualifierons de pragmatique, consiste à étudier mathématiquement le problème et à appliquer les algorithmes susceptibles de donner les meilleurs résultats possibles sans trop se soucier de savoir si ces algorithmes reproduisent ou non le raisonnement humain. On peut d'ailleurs rappeler ce qu'écrivent [AVAD52] : ``Une première légende prétend qu'il faut être un expert pour réaliser un bon programme. Pourtant, le développement d'un programme est un problème cybernétique qui demande au moins autant de travail sur les algorithmes que de connaissance du domaine. Cette dernière peut même avoir une influence négative, en raison de sa non formalisation. Une seconde légende dit qu'un ordinateur devrait penser ``comme un être humain'', et que ceci est un dogme absolu. Pourtant, si le but est de faire résoudre à un ordinateur des problèmes complexes, nous nous compliquons la tâche de façon injustifiée en tentant d'abord de résoudre le problème bien plus complexe de le faire raisonner comme nous.''

L'approche pragmatique a été employé dans AERA-III [Cel90, SPSS83, NFC⁺83, Nie89b, Nie89a, PA91] aux Etats-Unis. De la même façon, la philosophie du système ARC-2000 [K⁺89, FMT93, MG94] du Centre Expérimental Eurocontrol est trés proche de la nôtre. Comme l'écrivent [DFMN95] : ``Le démonstrateur ARC-2000 est basé sur une approche algorithmique, par opposition à une approche de type système expert, en ce qui concerne le problème de détection et de résolution de conflit. Les expérimentations ont montré qu'il était possible d'adopter une approche algorithmique de façon efficace en temps réel et avec une charge de trafic très importante. Il s'agit d'un avantage par rapport à l'approche ``système expert'', dans la mesure où cela permet d'avoir un moyen plus standardisé et plus ``certifiable'' de résoudre les problèmes''. Le travail que nous avons réalisé depuis 1992, et que nous allons présenter dans ce chapitre, s'inscrit également dans cette lignée.

Il faut également signaler que l'on a souvent trop tendance à confondre le but que l'on souhaite atteindre (automatisation complète, partielle ou simple aide au contrôleur) avec les techniques qu'il faut employer pour arriver à ses fins. Ce n'est pas parce que l'on souhaite fournir une aide au contrôleur, et non automatiser, que seule les méthodes ``cognitives'' sont applicables. On peut, par exemple, constater que l'aide la plus appréciable par tous de l'informatique a certainement été la machine à calculer, un objet fort peu cognitif. Je me plais souvent à rappeler ce petit texte d'un éminent spécialiste de l'IA, Jonathan Schaeffer : ``je considère l'esprit humain comme une machine, comme je considère mon ordinateur comme une machine. Ces deux machines ont leurs forces et leurs faiblesses. Mon cerveau est par exemple très fort pour la reconnaissance de formes et de situations, alors que mon ordinateur est très bon pour répéter des tâches et effectuer des calculs. En revanche, j'ai un sérieux problème à additionner un million de nombres en une second, et mon ordinateur n'est pas très doué pour le langage naturel, ou la reconnaissance de situations. Étant donné que chaque machine a des capacités différentes, il faut essayer d'exploiter les forces des machines et non leurs faiblesses.'' Ainsi, les algorithmes issus du système ARC-2000 sont en cours d'intégrations dans un système d'aide à la résolution de conflits [DFMN95] : ``Les principes généraux de résolution d'Arc-2000 ont prouvé leur grand efficacité. Ils sont actuellement appliqués de façon très satisfaisante à l'intérieur d'un système d'aide centré sur l'opérateur humain, appelé Highly Interactive Problem Solver''. Il n'y a pas opposition entre des algorithmes permettant de construire automatiquement des solutions, et des systèmes susceptibles de fournir de l'aide au contrôle. Il faut simplement remplir deux conditions : construire des algorithmes efficaces et fiables, quelle que soit leur structure, et présenter correctement l'information issue de ces algorithmes, de façon à la rendre directement utilisable. Si on peut discuter certains choix d'ARC-2000 (en particulier la non prise en compte des incertitudes), on ne peut en revanche que souscrire à la méthodologie appliquée.

3.1 Etude du trafic

3.1.1 Simulation du trafic

La première étape, avant de s'attaquer à la résolution de conflits, est de disposer d'un outil permettant de simuler le trafic afin de pouvoir étudier la sensibilité à chacun des paramètres, et de façon à pouvoir évaluer les différentes méthodes de résolution. Nous disposons actuellement d'un simulateur de trafic (Banc de Test) permettant de ``rejouer'' une journée complète du trafic français, en utilisant des données plan de vol établies à partir des archives du CAUTRA (GOETHE). Il fait voler les avions selon leur route prévue ou en route directe. Le modèle avion utilisé est très simple ¹² (figure 3.43). Il utilise en entrée le niveau de vol de l'avion ainsi que son attitude (montée, descente, en palier). Le modèle avion produit alors en sortie la vitesse sol, ainsi que le taux de montée ou de descente. On ne peux pas intervenir sur les taux de montée ou de descente, ni modifier la vitesse de l'avion.

Les avions suivent soit la route déposée dans le plan de vol (routes indirectes), soit une ligne droite entre le premier et le dernier point de leur route déposée (routes directes). A titre d'exemple, le simulateur introduit un écart de 4 mn par rapport à un vol réel Paris-Toulouse, phase d'atterrissage non comprise. L'écart moyen sur l'ensemble des vols, par rapport aux durées prévues, est de 13 s d'avance par vol (écart-type 6'53'') en routes indirectes, et 2'52'' d'avance (écart-type 8'14'') en routes directes, du fait du raccourcissement des trajectoires. Par ailleurs, il est possible de simuler un accroissement de la densité de trafic en comprimant les dates de décollage.

Enfin, une procédure de réattribution aléatoire des niveaux de vol permet d'augmenter le nombre de niveaux disponibles lorsque la séparation est réduite. Cette redistribution se fait par ajout d'une gaussienne d'écart-type 1500 ft sur le niveau de vol demandé, puis attribution du niveau effectif immédiatement inférieur à la valeur obtenue. Il n'y a pas doublement de l'espacement des niveaux au-dessus du FL 295.

A intervalles réguliers, le simulateur enregistre le nombre d'avions en vol par tranche de niveau, détecte les conflits selon les normes de séparation fixées, et enregistre les positions des avions aux dates de début et de fin de conflit. Un utilitaire permet de reconstituer les clusters, c'est-à-dire les ensembles d'avions en conflit 2 à 2 par fermeture transitive.

Le temps de simulation est d'environ 3 mn pour une journée de trafic, avec détection des conflits.

Les résultats sont observés dans une fenêtre temporelle d'étude, sur laquelles on va déterminer les clusters et extraire des données statistiques. L'utilisation d'une fenêtre est motivée par l'accroissement des incertitudes sur les positions prévues des avions. La planification des trajectoires ne peut-être efficace qu'en deçà d'un certain horizon temporel. Les clusters (ensembles d'avions en interaction) sont définis par fermeture transitive sur les conflits survenus dans la fenêtre.

Jean-François Bosc [Bos94a, Bos94b, Bos94c, Bos95a, Bos95b, Bos95c, Bos96a, Bos96b] a utilisé le banc de test en vue de déterminer l'influence sur le trafic, en termes de nombre de conflits et de clusters, des différents paramètres, que nous avons fait varier de la manière suivante :

séparations horizontales (NM) : 1, 2, 4, 6, 8, 10
séparations verticales (ft) : 300, 500, 800, 1000, 1300, 1500, 1800, 2000 (sans doublement au-dessus du FL195)
facteur de compression de temps : 1, 1.25, 1.5, 1.75, 2, 2.5, 4

soit 6³ = 216 simulations, effectuées en routes indirectes, en routes directes sans résolution, et en routes directes avec résolution. On utilise une redistribution aléatoire des niveaux de vol afin de tenir compte de la variation du nombre de niveaux disponibles lorsqu'on change la séparation verticale.

Par ailleurs, afin d'étudier l'influence de l'horizon temporel, nous avons utilisé une fenêtre d'étude de longueur variable, prise dans une période de trafic important et stable (typiquement entre 13 et 14 h). La durée des fenêtres varie de 10 à 60 mn par pas de 10 mn. La figure 3.1 montre la répartition des vols par niveau dans l'échantillon initial, avec utilisation des RVSM, et avec réduction des séparations à 500 ft.

Figure 3.1: Distribution du trafic

Les valeurs mesurées dans chaque fenêtre sont les suivantes :

nombre d'avions en vol,
nombre de conflits,
nombre de conflits stable-stable, stable-évolutif, et évolutif-évolutif,
nombre de clusters,
moyenne, écart-type et maximum du nombre de conflits par cluster,
moyenne, écart-type et maximum du nombre d'avions par cluster,
minimum du nombre d'avions dans les clusters dont le nombre de conflits est égal au maximum,
moyenne et maximum de l'écart-type par cluster du nombre de conflits par avion. Ces valeurs fournissent une indication sur la structure des clusters.

D'autre part, on mesure sur la journée complète les valeurs suivantes :

nombre de conflits (total et détaille en stable-stable, stable-évolutif, et évolutif-évolutif),
temps de vol moyen,
délai moyen et écart-type.

Enfin, on mesure pour chaque avion les heures de départ et d'arrivée et le retard, afin de fournir une loi d'évolution des délais pris dans la fenêtre, ce qui est plus réaliste qu'une observation sur la journée. En effet, les résultats sur la journée sont faussés par la répartition irrégulière du trafic.

3.1.2 Résultats

Les mesures relevées en routes directes et indirectes sont présentées dans les tables 3.1 (trafic actuel) et 3.2 (accroissement de 150% de la densité de trafic). Les deux dernières colonnes donnent les écarts en pourcentage dûs aux routes directes. On peut noter les points suivants concernant les routes directes par rapport aux routes indirectes :

réduction de 6 à 7% du volume de trafic. Ceci est directement lié à la réduction des temps de vol permise par les routes directes (6,4% en moyenne sur la journée).
réduction très nette du nombre de conflits et de clusters. Cette réduction est beaucoup moins marquée pour les conflits entre deux avions évolutifs.
réduction de la taille des clusters (nombre d'avions et de conflits).

On remarque toutefois que le gain en nombres de conflits obtenu en routes directes s'explique en grande partie par l'augmentation implicite du volume d'espace disponible, qui entraîne une diminution de la densité réelle du trafic.

Routes ind dir écart (%)

Séparation verticale STD RVSM STD RVSM STD RVSM

Nb de vols dans la fenêtre 225 221 210 207 -6.7 -6

Nb de clusters 49 42 33 21 -33 -50

Nb de conflits 69 56 40 30 -42 -46

stable-stable 22 9 11 4 -50 -56

stable-évolutif 35 35 20 14 -43 -60

évolutif-évolutif 12 12 9 12 -25 0

Moy du nb de conflits par cluster 1.41 1.33 1.21 1.43 -14 +7.5

Ecart-type du nb de conflits par cluster 0.70 0.64 0.54 0.73 -23 +14

Max du nb de conflits par cluster 3 3 3 3 -- --

Moy du nb d'avions par cluster 2.35 2.31 2.18 2.24 -7 -3

Ecart-type du nb d'avions par cluster 0.62 0.60 0.46 0.43 -26 -28

Max du nb d'avions par cluster 4 4 4 3 -- -25

Moy écart-type nb conflits par avion 0.12 0.11 0.06 0.11 -50 --

Max écart-type nb conflits par avion 0.87 0.87 0.50 0.82 -43 -6

Table 3.1: Trafic actuel.

Routes ind dir écart (%)

Séparation verticale STD RVSM STD RVSM STD RVSM

Nb de vols dans la fenêtre 569 559 531 521 -6.7 -6.8

Nb de clusters 224 202 170 139 -24 -31

Nb de conflits 491 355 271 215 -45 -39

stable-stable 181 72 84 39 -54 -46

stable-évolutif 200 179 99 96 -50 -46

évolutif-évolutif 110 104 88 80 -20 -23

Moy du nb de conflits par cluster 2.19 1.76 1.59 1.55 -27 -12

Ecart-type du nb de conflits par cluster 4.29 1.96 1.43 1.26 -67 -36

Max du nb de conflits par cluster 60 18 13 8 -78 -55

Moy du nb d'avions par cluster 3.00 2.63 2.51 2.50 -16 -5

Ecart-type nb d'avions par cluster 3.28 1.59 1.14 1.09 -65 -31

Max du nb d'avions par cluster 47 15 11 8 -77 -47

Moy écart-type nb conflits par avion 0.23 0.16 0.16 0.15 -30 -6

Max écart-type nb conflits par avion 1.27 1.50 1.20 1.16 -5.5 -23

Table 3.2: Accroissement de 150%.

La faible réduction du nombre de vols amenée par les RVSM s'explique par le fait que les avions dont le niveau de vol est modifié volent en général plus bas, et donc gagnent un peu de temps dans les phases de montée et de descente. Par contre le gain en nombre de conflits est important, du fait que les niveaux les plus chargés sont situés au-dessus du FL195 (voir figure 3.1).

On constate d'autre part que l'introduction des séparations RVSM touche essentiellement les conflits stable-stable, ce qui correspond à ce que l'on pouvait attendre. Les conflits impliquant au moins un avion évolutif sont rarement affectés.

Volume de trafic

On va tout d'abord s'intéresser aux valeurs mesurées dans la fenêtre temporelle. On obtient dans tous les cas (routes indirectes, et routes directes avec et sans résolution) une corrélation entre compression de temps et volume de trafic (nombre d'avions en vol dans la fenêtre) tout à fait conforme aux prévisions :

N_avions = K₁ C

alpha

avec a = 1, C étant la compression de temps. L'écart relevé sur la valeur de a est inférieur à 1.5%, et le taux de corrélation est de 99.9%. La taille de la fenêtre n'a donc pas d'incidence, tout au moins sur le trafic moyen observé dans la fenêtre. Il ne semble pas y avoir d'effet de bord (chute du trafic en fin de fenêtre) sensible, même pour les fenêtres les plus longue (jusqu'à 1 h) avec une forte compression de temps (qui réduit la durée de la plage de fort trafic).

Conflits et clusters

On remarque que les différents paramètres sont indépendants les uns des autres. On peut s'attendre à ce que le nombre de conflits augmente avec chacun des paramètres, et soit nul pour des valeurs nulles de ceux-ci. On cherche donc à modéliser le nombre de conflits sous la forme suivante :

N_conf = K C^c H^h V^v Iⁱ

C étant la compression de temps, H la norme de séparation horizontale, V la norme de séparation verticale, et I l'intervalle d'étude.

Routes indirectes :

Les résultats sont présentés dans la table 3.3. On remarque tout d'abord d'excellents coefficients de corrélation, qui montrent que le modèle choisi est adéquat.

On constate que le nombre de conflits augmente à peu près linéairement en fonction du carré de la densité de trafic, de la séparation verticale, et de l'intervalle d'étude. En ce qui concerne la séparation horizontale, le coefficient est un peu inférieur aux prévisions (les modèles, notamment [Ale70, Bos94c], prévoient une évolution linéaire en fonction de la norme, ou inversement proportionnelle au nombre de niveaux). Ceci est vraisemblablement dû aux conflits comprenant au moins un avion évolutif, pour lesquels la séparation verticale a peu d'incidence. On retrouve d'ailleurs une valeur proche de 1 pour les conflits stable-stable. De plus, la distribution des avions sur les niveaux de vol est imparfaite. On remarque quelques anomalies (écarts entre niveaux de même parité) sur la figure 3.1.

La valeur élevé du coefficient de la norme horizontale pour les conflits stable-évolutif, que l'on retrouve en routes directes (sans résolution), n'a pu être expliquée. Toutefois, [EO83] prévoit une composante en H² (correspondant au volume parcouru par le disque de rayon H) lorsque les vitesses verticales ne sont pas toutes identiques. Mais il reste a expliquer le coefficient plus faible pour les conflits stable-stable. De même pour le coefficient inférieur à 1 sur la taille de fenêtre d'observation, puisqu'on a vu qu'il ne semblait pas y avoir d'effet de bord.

Conflits Clusters

total stab-stab stab-évol évol-évol

c 1.95 2.24 1.81 1.91 1.61

h 0.99 0.68 1.30 0.87 0.68

v 0.75 0.92 0.71 0.69 0.52

i 0.90 0.91 1.08 0.67 0.80

r² 0.98 0.94 0.96 0.95 0.95

Table 3.3: Conflits et clusters en routes indirectes

Routes directes

Conflits Clusters

total stab-stab stab-évol évol-évol

c 2.16 2.04 2.07 2.08 1.81

h 1.34 1.00 1.48 1.28 1.05

v 0.85 0.96 0.86 0.72 0.69

i 0.92 0.86 0.93 0.81 0.83

r² 0.97 0.92 0.94 0.93 0.93

Table 3.4: Conflits et clusters en routes directes sans résolution

Les valeurs obtenues sont données dans la table 3.4. On obtient encore une corrélation très élevée, et les coefficients sont à peu près similaires à ceux relevés en routes indirectes. L'anomalie sur la norme horizontale est plus marquée.

Par ailleurs, l'évolution du nombre de conflits en fonction d'un paramètre lorsqu'on laisse les 3 autres fixes est visualisée sur les figures 3.2 et 3.3. Les valeurs fixées sont de 1 pour la compression de temps (trafic actuel), 6 NM pour la norme horizontale, 1000 ft pour la norme verticale (RVSM), et 30 mn pour la durée de la fenêtre. Sur la figure 3.2, le trafic standard correspond à une densité de 1.

Figure 3.2: Influence de la densité et de la norme horizontale sur le nombre de conflits.

Figure 3.3: Influence de la norme verticale et de l'intervalle sur le nombre de conflits.

L'évolution du nombre de clusters en fonction d'un paramètre lorsqu'on laisse les 3 autres fixes est visualisée sur les figures 3.4, et 3.5.

Figure 3.4: Influence de la densité et de la norme horizontale sur le nombre de clusters.

Figure 3.5: Influence de la norme verticale et de l'intervalle sur le nombre de clusters.

Enfin l'évolution du retard moyen (en secondes) observé dans la fenêtre apparaît sur la figure 3.6. La norme verticale et la durée de la fenêtre n'ont quasiment pas d'incidence. Sur chaque figure, une courbe correspond à l'ensemble des configurations de densité et de norme, l'autre est limitée à celles pour lesquelles au moins les deux tiers des conflits sont résolus.

Figure 3.6: Influence de la densité et de la norme horizontale sur les retards.

3.1.3 Conclusion

L'étude précédente montre que l'accroissement du nombre de conflit en fonction de l'accroissement du trafic est quadratique, alors que la diminution des normes de séparation n'a qu'une influence linéaire. La diminution des normes de séparation ne saurait donc être une panacée pour diminuer le nombre de conflits. Le problème de la résolution de conflits va donc se poser de façon de plus en plus aigu dans les années à venir.

3.2 Approche mathématique

Il est toujours indispensable de tenter de résoudre analytiquement un problème et d'évaluer sa complexité ¹³ avant de se lancer dans une approche de quelqu'autre forme que ce soit. Le principal travail effectué sur ce thème l'a été par Nicolas Durand dans le cadre de sa thèse [Dur96]. Ce travail a d'ailleurs fait l'objet de plusieurs publications [DAAS94, DAN94, DAN96b, DCA96, DAN96a, DA96].

3.2.1 Conflit entre des avions non contraints en vitesse

Résolution par une méthode de commande optimale

L'aéronautique utilise depuis longtemps maintenant les outils du Contrôle Optimal pour optimiser les trajectoires d'un avion [Cle90, MZ88, BH91, ME88, Sch90]. L'application de ces techniques au problème de la résolution de conflit de deux avions non contraints en vitesse est intéressante, mais montre rapidement ses limites, en raison de la forte complexité du problème.

On essaie de construire une résolution minimisant la consommation des avions, que l'on suppose proportionnelle à l'intégrale de la vitesse au carré. Il est alors possible de montrer que le problème possède deux propriétés intéressantes :

Le centre de gravité des n avions a un mouvement rectiligne et uniforme.
Dans le reférentiel barycentrique :

" t Î [t₀,t_f],

n

S

i=1
u_ig(t) Ù x_ig(t)
= Cte
où u_ig représente le vecteur vitesse et x_ig le vecteur position de l'avion i dans le référentiel barycentrique.

Dans le cas général de n avions, l'utilisation de ces deux invariants ne permet pas de résoudre le problème. En revanche, si l'on restreint le problème à deux avions, on peut déterminer analytiquement la solution optimale : les avions, pour s'éviter, tournent autour de leur isobarycentre à vitesse constante, isobarycentre qui se déplace lui-même à vitesse constante. On montre également que l'optimum dépend de l'éloignement en temps des avions par rapport au point de croisement mais pas de la vitesse de chacun des avions, et on peut construire une interprétation géométrique permettant de déterminer immédiatement le meilleur minimum.

Il faut cependant savoir que, dans la réalité, les avions sont fortement contraints en vitesse, ce qui rend caduc tout espoir de résolution ``optimale'' en terme de consommation.

Faisabilité de la résolution en vitesse

La régulation en vitesse, aujourd'hui pratiquée principalement dans les phases de descente et d'approche a l'avantage de ne pas changer le support de la trajectoire des avions. Néanmoins, elle nécessite des tenues de vitesses rigoureuses et des temps d'anticipation variables selon l'angle de conflit et sa gravité. Nous analysons ici de façon théorique quels sont les temps d'anticipations nécessaires pour une régulation en vitesse, en supposant que les tenues de trajectoires 4 D des avions sont parfaites.

La figure 3.7 représente le temps d'anticipation minimum pour résoudre un conflit entre deux avions ayant la même vitesse (rapport des vitesses, r=1). On représente en ordonnée la capacité e mesurée en % qu'un avion a de ralentir ou d'accélérer et en abscisse l'angle a de convergence des deux avions. Les courbes iso-temps parcourent les points pour lesquels le temps d'anticipation minimal est constant. La courbe intérieure correspond à un temps d'anticipation de 5 minutes. En allant de l'intérieur vers l'extérieur, le temps augmente par pas de 1 minute.

Figure 3.7: Temps d'anticipation en minutes en fonction de e et de a (r=1).

Figure 3.8: Temps d'anticipation en minutes en fonction de e et de a, à gauche : r=1.5 - à droite : r=0.5.

On observe ainsi que pour e³15% et des angles de trajectoires entre 10 et 120 degrés, le temps d'anticipation reste inférieur à 10 minutes dans le pire des cas (c'est à dire lorsque les avions sont prévus au même instant au point de croisement des trajectoires). La résolution en vitesse peut alors s'appliquer de façon relativement systématique. En revanche, si la marge d'accélération ou de ralentissement des deux avions est inférieure à 5%, on ne peut effectuer de résolution en vitesse si l'on ne prend pas une marge de plus de 20 minutes.

La figure 3.8 représente pour des rapports de vitesse r=1.5 et r=0.5 le temps d'anticipation nécessaire toujours en fonction de l'angle a des trajectoires et de e. On observe que pour r>1 (on intervient alors sur l'avion le plus lent) les résultats précédents restent bons. Si l'on intervient sur l'avion le plus rapide, il faut intervenir plus tôt.

L'observation des courbes précédentes montre qu'une régulation en vitesse est envisageable pour une majorité de conflits dans la mesure où la marge de régulation sur les avions est suffisamment importante. Ainsi, si l'on peut faire varier la vitesse des avions de plus de 15%, on peut espérer résoudre en vitesse bon nombre de conflits.

Nous n'avons pas jusqu'à maintenant évoqué les problèmes d'incertitude sur les tenues de vitesse des avions. Il est clair que si les avions ne peuvent tenir leur vitesse de façon précise, la régulation en vitesse devient difficile. Dans les hypothèses que nous avons choisies, nous avons toujours considéré les conflits dans le pire des cas, à savoir lorsque les deux avions sont supposés passer par le point d'intersection de leurs trajectoires au même instant. Il est clair que si deux avions sont déjà partiellement séparés, une régulation en vitesse peut permettre de les séparer complètement facilement. Néanmoins, plus on anticipe la régulation, plus l'incertitude joue un rôle important. Ainsi, à 400 noeuds, une incertitude de 1% pendant 20 minutes représente 1.33 nautiques. Aujourd'hui peu d'avions sont équipés de FMS-4D permettant de telles précisions. Ceci explique pourquoi les contrôleurs n'utilise la régulation en vitesse qu'en phase de descente, les marges de manoeuvres étant alors plus importantes.

3.2.2 Conflit entre deux avions contraints en vitesse

Résolution par une méthode de commande optimale

On va donc maintenant s'intéresser au cas de deux avions contraints en vitesse. Il s'agit du cas le plus proche de la réalité en matière de contrôle en route. On minimisera ici l'allongement de la trajectoire. La condition nécessaire de résolution permet de décrire les différentes phases de trajectoires. Lorsque la contrainte de séparation n'est pas saturée, les trajectoires des avions sont rectilignes uniformes, leurs caps sont modifiés uniquement lorsque la contrainte de séparation est saturée. Ce résultat reste valable pour le cas de n avions. La contrainte sur les vitesses ne permet pas d'aller plus loin dans la résolution analytique du conflit. De plus, lorsqu'un conflit à deux avions se présente, il n'est pas ``rentable'' en terme de coût pour le contrôleur aérien de dévier les deux avions. En conséquence, dans la suite, la trajectoire d'un des deux avions sera privilégiée (elle sera maintenue rectiligne et uniforme).

On peut, lorsque l'on privilégie un des deux avions en lui assurant une trajectoire rectiligne uniforme jusqu'à son objectif, s'intéresser à l'allongement de la deuxième trajectoire engendré par le conflit. On peut étudier le cas simple de 2 avions se croisant perpendiculairement et volant à la même vitesse. On notera d le rapport (norme de séparation) / (distance au point de conflit).

Dans le repère de l'avion non dévié, on peut (voir figure 3.9) représenter l'origine et la destination de l'avion dévié, ainsi que la zone interdite pour l'avion dévié, à savoir le cercle de centre l'origine et de rayon d.

On sait déjà qu'à l'optimum, l'avion dévié rejoint ce cercle en ligne droite en un point repéré par l'angle q₁, y reste jusqu'à q₂ et ensuite rejoint sa destination en ligne droite.

Figure 3.9: Trajectoires de l'avion dévié dans le repère lié à l'avion non dévié.

On va chercher alors à exprimer les valeurs de x₊ et x_- correspondant aux deux cas possibles : l'avion dévié passe devant l'avion fixe, ou derrière celui-ci. On obtient alors les équations implicites donnant les valeurs des optima :

2 +x₊ =

1 -

((2 - d²)⁽1/2)

2 + 2 x₊ + x₊²

æ
ç
ç
è

1 + x₊ +

((2 + 2 x₊ + x₊² - d²)⁽1/2)

ö
÷
÷
ø

log (

(

1 + d

)

(

((2 + 2 x₊ + x₊² - d²)⁽1/2)-1

)

(

1 + x₊ - d

)

(

((2 - d²)⁽1/2)-1

)

2 +x_- =

1 +

((2 - d²)⁽1/2)

2 + 2 x_- + x_-²

æ
ç
ç
è

1 + x_- -

((2 + 2 x_- + x_-² - d²)⁽1/2)

ö
÷
÷
ø

log (

(

1 + d

)

(

((2 + 2 x_- + x_-² - d²)⁽1/2)+1

)

(

1 + x_- - d

)

(

((2 - d²)⁽1/2)+1

)

Figure 3.10: Comparaison des allongements minimaux (en % ) pour t supérieur à 1.5.

Ceci nous définit des fonctions implicites x₊(d) et x_-(d). Si l'on pose d=1 / t, on peut représenter les pourcentages d'allongements de trajectoires en fonction de l'anticipation de la résolution du conflit (voir figure 3.10). L'unité de temps est alors le temps mis par un avion pour parcourir la valeur d'une norme de séparation. On observe que les pourcentages d'allongement de trajectoire restent très faible tant que t est supérieur à 2. Dans notre exemple, la trajectoire optimale est toujours celle qui passe derrière l'avion non dévié.

On peut assez facilement étendre l'étude précédente au cas de deux avions convergent non plus à angle droit mais sous un angle quelconque. Toujours en ne bougeant qu'un seul avion, on peut déterminer les deux équations implicites qui nous donnent l'allongement de trajectoire du deuxième avion dans le cas où celui-ci passe devant ou derrière.

Figure 3.11: Allongements minimaux en fonction de l'angle d'incidence et du rapport des vitesses pour une anticipation valant deux fois la norme de séparation.

Enfin, on peut représenter en fonction de l'angle d'incidence et du rapport des vitesses des deux avions, l'allongement minimal obtenu, pour une anticipation de, par exemple, cinq fois la norme de séparation (voir figure 3.11). On observe alors que les situations les plus pénalisantes dans le cas où les vitesses sont voisines et les angles d'incidence faibles, ce qui reste conforme aux résultats précédents ainsi qu'aux résultats décrits par AERA 3.

Approche numérique

Nous présentons ici les solutions optimales (fournies par à un algorithme d'optimisation locale ¹⁴ ) de certains conflits à deux avions.

La figure 3.12

Figure 3.12: De haut en bas et de gauche à droite, allongements moyens : 2.16, 2.21, 2.22, 2.20, 2.19 et 2.17 degrés.

donnent six façon de résoudre un conflit à cinq avions. 6 points de départ différents ont été donnés à LANCELOT pour la recherche de la solution optimale donnant 6 solutions localement optimales situées dans des composantes connexes différentes. Il existe probablement bien plus que six composantes connexes disjointes pour ce problème, mais le but de ce paragraphe n'est pas de les chercher toutes. On remarquera que les solutions, apparemment très différentes, génèrent des allongements moyens très voisins.

On notera que le temps de calcul nécessaire à la convergence de LANCELOT est très long : pour les exemples à 5 avions présentés ci-dessous, plusieurs heures sont nécessaires. Envisager une résolution en temps réel avec ce type d'algorithme ne parait pas raisonnable.

3.2.3 Complexité théorique

Nous venons de constater que le problème de résolution de conflits est difficile à résoudre, même numériquement, dès que le nombre d'avions augmente. Il est en fait possible d'établir un résultat général concernant la complexité du problème, dans le cas où un des avions a un cap et une vitesse maintenus fixes, et où la norme et la direction du vecteur vitesse de l'avion mobile ne peuvent changer qu'en un nombre fini d'instants ¹⁵ .

On peut alors montrer que l'espace des trajectoires admissibles pour l'avion mobile se compose de deux composantes connexes indépendantes, qui correspondent l'une aux trajectoires obtenues quand l'avion mobile passe devant l'avion dit ``fixe'', et l'autre au cas ou l'avion mobile passe derrière l'avion fixe au point de conflit.

Dans le cas où l'on s'intéresse à un conflit comprenant n avions on se retrouve face à

n (n-1)

conflits potentiels. L'espace des solutions admissibles contient donc 2

^n (n-1)

composantes connexes. Il est clair que dans la pratique, compte-tenu des performances des avions, toutes les composantes connexes n'ont pas besoin d'être explorées. Néanmoins, la présence théorique d'autant d'espaces disjoints et l'impossibilité de connaître à priori lequel contient la solution optimale nous a orienté vers des méthode d'optimisation globale plutôt que vers des méthodes locales.

3.2.4 Conclusion

La modélisation par Contrôle Optimal que nous avons abordée dans cette première partie permet de dégager certaines propriétés sur les trajectoires optimales et sur la structure de l'espace des solutions admissibles.

Nous retiendrons tout d'abord que les trajectoires non contraintes sont rectilignes et uniformes à l'optimum. Dans la pratique, la durée de saturation des contraintes, compte-tenu de la vitesse élevée des avions et de la faible densité de trafic, est très faible comparée à la durée de vol sans saturation de contrainte (dans la mesure où les conflits ne sont pas à angle trop faible). En conséquence, la plupart des trajectoires optimales peuvent être approchées par des trajectoires rectilignes par morceaux (c'est l'objet du prochain chapitre). Dans le cas où les avions ne sont pas contraints en vitesse, on a montré que l'on peut déterminer géométriquement la solution optimale.

Le second point important résulte de la structure de l'espace des solutions admissibles pouvant contenir pour n avions 2

^n (n-1)

composantes connexes disjointes. Le problème est de ce fait fortement combinatoire et nous avons pu observer numériquement qu'un algorithme d'optimisation locale tel que LANCELOT ne permet pas de trouver l'optimum global pour des valeurs de n faibles (par exemple n=5).

3.3 Approximation par point tournant et par offset

Les trajectoires optimales étudiées dans la section 3.2.2 étant formées de deux segments rectilignes relativement longs et d'une portion courbe réduite, il apparaît naturel de vouloir les approcher par des trajectoires composées de segments de droite. La modélisation par point tournant ramène la trajectoire à deux segments, alors que la modélisation par offset conserve trois segments.

3.3.1 Point tournant

La trajectoire des avions se ramène donc à deux droites se coupant en un point tournant (figure 3.13).

Figure 3.13: Modélisation point tournant.

On peut représenter l'augmentation en pourcentage de l'allongement lorsque l'on remplace la trajectoire d'évitement réelle par un point tournant (voir figure 3.14). On observe que pour la solution optimale, l'augmentation d'allongement due à notre approximation reste inférieure à 0.25 % tant que le temps d'anticipation t est supérieur à 2 et que pour l'autre solution, cet écart ne dépasse pas 3 %.

Figure 3.14: Allongements en %, l'avion mobile passant derrière (à gauche) ou devant (à droite) l'avion fixe.

L'angle d'incidence a une forte influence sur l'efficacité de ce mode de résolution .

Figure 3.15: Augmentation de l'allongement x_t+-x₊ en fonction de t et f.

On a représenté sur la figure 3.15 l'allongement de la trajectoire en fonction de la distance au point de conflit (t représente le rapport des distances (distance au point de conflit/(norme de séparation)) et de l'angle de convergence. On constate que pour des valeurs faibles de l'angle de convergence et pour une faible anticipation, la méthode du point tournant est peu efficace.

3.3.2 Approximation par offset

On appellera résolution par offset, la solution de notre programme de minimisation lorsque l'on met en parallèle l'un des deux avions impliqués dans le conflit. C'est la solution adoptée par Niedringhaus [NFC⁺83, Nie89b, Nie89a], pour le projet d'automatisation complète AERA 3 dans la fonction ``Gentle-Strict''.

Figure 3.16: Allongements optimaux en %, l'avion mobile passant derrière (à gauche) ou devant (à droite) l'avion fixe, f=p/ 8.

Nous avons représenté : les pourcentages d'allongement des trajectoires en fonction du temps d'anticipation tx=ty pour des angles d'incidences de trajectoires valant p/ 2 (figure ), 7 p/8 (figure ) et p / 8 (figure 3.18), et des angles de mise en offset valant p/ 3, p/ 4, p/ 6, p/ 8. Pour une incidence de trajectoires valant p/ 8, l'avion dévié ne peut pas passer devant l'avion fixe avec ce type d'offset.

Le principal intérêt de cette modélisation est que la fonction à minimiser devient linéaire, de même que les contraintes de séparation des avions une fois l'offset réalisé (à condition que l'angle de déviation soit fixé à priori). C'est ce que nous allons montrer. On s'intéresse donc ici à deux avions, a_i et a_j. On note f_i,j l'angle formé par les trajectoires non déviées de a_i et a_j, t_ijⁱ (resp. t_ij^j) l'instant auquel la trajectoire non déviée de l'avion a_i (resp. a_j) coupe celle de l'avion a_j (resp. a_i), et v_i et v_j les normes des vecteurs vitesse des avions (par hypothèse constantes sur [t_o,t_f]).

On considère le repère orthonormé (C_ij,E_j,E_i), où C_ij est le point d'intersection des trajectoires des deux avions a_i et a_j, et dont l'axe des abscisses (E_j) est dirigé par le vecteur vitesse de a_j (voir figure 3.19).

Figure 3.17: Conflit à deux avions, un seul avion étant dévié

On obtient les paramétrisations suivantes pour les coordonnées au temps t Î [t_o,t_f] des avions a_i et a_j, dans ce repère :

x_i'(t)	=	v_i (t - t_ijⁱ) cos (f_ij)
y_i'(t)	=	v_i (t - t_ijⁱ) cos (f_ij)

x_j'(t)	=	v_j (t - t_ij^j)
y_j'(t)	=	0

Dans ce repère la contrainte de séparation donne donc pour le couple (a_i,a_j) :

" t Î [t_o,t_f], (x_i'(t)-x_j'(t))² + (y_i'(t)-y_j'(t))² ³ d² (3.1)

En résolvant, il vient :

v_i² v_j² sin (f_ij)² (t_ijⁱ-t_ij^j)² ³ d² (v_i²+v_j² - 2 v_i v_j cos (f_ij)) (3.2)

Cette condition donne les deux conditions suivantes, selon l'ordre de passage des avions a_i et a_j au point C_ij, point d'intersection de leurs deux trajectoires :

Si l'avion a_i passe derrière l'avion a_j, on obtient :
(t_ijⁱ-t_ij^j) v_i v_j sin(f_ij) ³ d ((v_i² + v_j² - 2 v_i v_j cos (f_ij))⁽1/2) (3.3)
Si l'avion a_i passe devant l'avion a_j, on obtient :
(t_ij^j-t_ijⁱ) v_i v_j sin(f_ij) ³ d ((v_i² + v_j² - 2 v_i v_j cos (f_ij))⁽1/2) (3.4)

La mise en offset d'un avion (ou des deux avions a_i et a_j) a pour effet d'introduire un décalage d'une trajectoire par rapport à l'autre et d'influer ainsi sur l'instant auquel la trajectoire de chacun des deux avions coupe celle de l'autre. Nous nous intéressons à un couple d'avions, a_i et a_j, tous deux impliqués dans un conflit à n avions. La trajectoire de chacun de ces deux avions peut être déviée.

Pour chacun des deux avions a_i et a_j, l'évitement par offset a trois effets sur les temps t_i,jⁱ et t_i,j^j. Ces effets dépendent de l'angle de mise en offset, noté b, du sens de l'offset, et de sa valeur. Ainsi un offset de l'avion a_i d'une valeur d_i aura les effets suivants :

t_ijⁱ est augmenté, quelque soit le sens de l'offset, du retard dû à la mise en offset, c'est à dire de

d_itan(

b

2
)

v_i
;
si la trajectoire de l'avion a_i est déviée vers l'extérieur de l'angle formé par les trajectoires des deux avions (a_i et a_j), t_ijⁱ est augmenté du retard dû au déplacement de l'avion a_i, c'est à dire de

d_icot(f_ij)

v_i
. Si la trajectoire de a_i est déviée vers l'intérieur de cet angle, t_ijⁱ est diminué de cette valeur ;
de même, si la trajectoire de l'avion a_i est déviée vers l'extérieur de l'angle formé par les trajectoires des deux avions (a_i et a_j), t_ij^j est aussi augmenté du retard dû au déplacement de la trajectoire de l'avion a_j, c'est à dire de

d_i

v_jsin(f_ij)
.

Ainsi, quand l'avion a_i passe derrière l'avion a_j, selon le sens de l'offset de chacun des deux avions a_i et a_j on obtient les quatre conditions de séparations suivantes, qui sont linéaires en d_i et en d_j :

Figure 3.18: Conflit à deux avions, les deux offsets étant à l'extérieur

Les offsets des deux avions sont à l'extérieur (c'est le cas qui est représenté sur la figure 3.20) :

(t_ijⁱ +

d_itan(

)

v_i

d_icot(f_ij)

v_i

d_j

v_isin(f_ij)

- t_ij^j -

d_jtan(

)

v_j

d_jcot(f_ij)

v_j

d_i

v_jsin(f_ij)

) v_i v_j

sin

(f_ij)

- d ((v_i² + v_j² - 2 v_i v_j cos f_ij)⁽1/2)

(3.5)

L'offset de l'avion a_i est à l'extérieur, celui de l'avion a_j est à l'intérieur :

(t_i,jⁱ +

d_itan(

)

v_i

d_icot(f_ij)

v_i

d_j

v_isin(f_ij)

- t_i,j^j -

d_jtan(

)

v_j

d_jcot(f_ij)

v_j

d_i

v_jsin(f_ij)

) v_i v_j

sin

(f_ij)

- d ((v_i² + v_j² - 2 v_i v_j cos f_ij)⁽1/2)

(3.6)

L'offset de l'avion a_i est à l'intérieur, celui de l'avion a_j est à l'extérieur :

(t_ijⁱ +

d_itan(

)

v_i

d_icot(f_ij)

v_i

d_j

v_isin(f_ij)

- t_ij^j -

d_jtan(

)

v_j

d_jcot(f_ij)

v_j

d_i

v_jsin(f_ij)

) v_i v_j

sin

(f_ij)

- d ((v_i² + v_j² - 2 v_i v_j cos f_ij)⁽1/2)

(3.7)

Les offsets des deux avions sont à l'intérieur :

(t_ijⁱ +

d_itan(

)

v_i

d_icot(f_ij)

v_i

d_j

v_isin(f_ij)

- t_ij^j -

d_jtan(

)

v_j

d_jcot(f_ij)

v_j

d_i

v_jsin(f_ij)

) v_i v_j

sin

(f_ij)

- d ((v_i² + v_j² - 2 v_i v_j cos f_ij)⁽1/2)

(3.8)

Et on obtient quatre équations similaires dans le cas où l'avion a_i passe devant l'avion a_j (en intervertissant dans les équations ci-dessus les indices i et j).

On a considéré jusqu'ici que les droites portant les trajectoires non déviées des avions a_i et a_j étaient sécantes (et, comme on l'a vu, que les trajectoires des avions se coupaient pour tÎ[t_o,t_f]). Dans le cas où les trajectoires sont parallèles, on obtient aussi des conditions linéaires, avec la même combinatoire, la discussion sur l'ordre de passage des deux avions est alors remplacée par le choix entre ``a_i passe à gauche de a_j'' et ``a_j passe à gauche de a_i''.

Cette modélisation étendue au cas de n avions nécessite la résolution de 2^{n (n+1)/ 2} programmes linéaires comprenant chacun n (n+1)/ 2 contraintes linéaires. Pour un conflit à 5 avions, cela représente 32768 programmes d'optimisation à résoudre comprenant 15 contraintes linéaires chacun. Pour n=7, plus de 2 million de programmes linéaires doivent être résolus, comprenant 21 contraintes chacun. On se retrouve face à une très forte combinatoire. Il est intéressant de noter que l'on retrouve les composantes connexes observées dans le paragraphe 3.2.3. En effet, chaque programme linéaire détermine un ordre de passage entre une paire d'avions et résout le problème à l'intérieur d'une composante connexe de l'espace des solutions admissibles. Il faut néanmoins choisir le sens de la déviation pour chaque avion pour que le programme devienne linéaire ; c'est pourquoi la complexité passe de 2^{n (n-1)/ 2} à 2^{n (n-1)/ 2} × 2ⁿ = 2^{n (n+1)/ 2}. F. Médioni [MDA94] s'est intéressé à combiner un algorithme génétique avec un programme d'optimisation linéaire pour résoudre le problème décrit ci-dessus. Nous présentons ces résultats dans la section 3.7.

Nous ne nous sommes intéressés jusqu'à présent qu'à satisfaire la contrainte de séparation lorsque l'avion est établi en offset. Durant la mise en offset, les deux avions doivent rester séparés. La vérification de cette contrainte est longue, ou impose de prendre des marges de manoeuvre qui pénalisent la résolution.

3.3.3 Avions en rattrapage

Nous n'avons pas étudié jusqu'à présent les cas de conflits causés par des rattrapages. Dans ce cas, lorsque deux avions sur la même route ont des vitesses proches, l'offset devient plus avantageux que le point tournant. En effet, que l'avion le plus rapide dépasse le plus lent ou que l'avion le plus lent évite le plus rapide (figure 3.21), l'offset permet d'éviter un éloignement de plus d'une séparation standard de la trajectoire initiale.

Figure 3.19: Rattrapages

Si l'on note r le rapport des vitesses des deux avions, et X l'allongement due à la technique du point tournant par rapport à l'offset, on peut

Figure 3.20: A gauche : X en fonction de r pour r<1 - A droite : X en fonction de r pour r>1.

apprécier sur la figure 3.22 la supériorité de la technique de l'offset par rapport à la technique du point tournant simple.

Les calculs présentés ci-dessus nous conduisent finalement à la conclusion suivante : la modélisation point tournant, très efficace pour résoudre les problèmes de conflits à angle non nuls, s'avère insuffisante dans le cas des rattrapages. Il faut donc conserver les deux modélisations, qui ont des champs d'application différents.

3.4 Modélisation de l'incertitude

3.4.1 Nécessité de modéliser l'incertitude

Si un avion de ligne est capable de suivre précisément une route et une altitude, maîtriser précisément sa vitesse sol n'est pas possible en raison notamment des vents. Il est d'autre part impossible de corriger en permanence la vitesse car les réacteurs ont un régime de consommation idéal dont il ne faut pas trop s'écarter. Enfin, ils ne doivent pas, pour des raisons mécaniques, être soumis à des changements de régime permanents. Il est donc indispensable de modéliser les avions non par des points matériels mais par des segments de droites.

Figure 3.21: Modélisation de l'incertitude.

Il suffira alors de vérifier, pour que la contrainte horizontale soit respectée, que les segments de droite qui modélisent les avions soient séparés par la séparation standard (voir figure 3.23). Dans le plan vertical, l'incertitude est beaucoup plus forte. On maîtrise en effet très mal le taux de montée d'un avion qui dépend de paramètres aussi variés que la masse, où la mise en route de la climatisation. En conséquence, le même principe que dans le plan horizontal est repris mais les pourcentage d'incertitude seront beaucoup plus forts.

3.4.2 Évaluation de la probabilité de conflit.

Compte-tenu de l'incertitude sur la vitesse des avions que nous observons, il est évident qu'un conflit ne peut être prévu à l'avance avec certitude. Il se peut en effet que les erreurs sur la vitesse de chacun des avions suffisent à éviter le conflit. Dans ce cas, une manoeuvre d'évitement s'avère inopportune. Le but de ce paragraphe est de mesurer la valeur de la probabilité de conflit en fonction de la configuration du conflit et de l'incertitude sur les vitesses.

On ne peut bien évidemment pas étudier toutes les configurations de conflits. Aussi, nous nous limiterons au cas où les deux ont la même vitesse V, convergent sous un angle f vers un point de conflit. Les avions sont distants du point de conflit de V T. On suppose que chaque avion se déplace à vitesse constante, avec une incertitude en pourcentage sur cette vitesse notée Er. Pour simplifier, on supposera donc que chacun des deux avions a une probabilité uniforme d'avoir sa vitesse comprise entre (1-Er) V et (1+Er) V. On notera d la norme de séparation choisie. On veut mesurer la probabilité de conflit en fonction de l'anticipation T, de l'angle d'incidence f et de l'incertitude Er choisie.

On numérotera 1 et 2 les indices des deux avions. A un instant t ³ -T, les avions sont repérés par leur position dans le plan :

-T V₁ + t (1+Er₁) V₁

-T V₂ + t (1+Er₂) V₂

avec Er₁ et Er₂ compris entre -Er et Er. A partir des positions des deux avions à tout instant t, on cherche à quelle condition sur Er₁ et Er₂ il y a conflit. Pour cela, on est amené à déterminer le signe du discriminant d'une équation du second degré. La condition, une fois simplifiée s'écrit de la façon suivante.

Il y a conflit si et seulement si :

V² T²

d²

(

sin

f)²-1

2 (1-cosf)

(1+Er₁) (1+Er₂)

(Er₁-Er₂)²

Il est clair que si l'angle f vaut 0 ou p, le conflit est certain. On remarquera que la condition précédente ne dépend que du rapport x=

V T

qui mesure l'anticipation par rapport au point de conflit. On peut représenter la condition par une fonction f(x_,f,Er₁,Er₂) qui vaut 0 lorsque la condition n'est pas satisfaite et 1 lorsque la condition est satisfaite. On intègre ensuite cette fonction sur le pavé des erreurs possibles et on obtient la probabilité p(x,f,Er) pour que les deux avions entrent en conflit avec une anticipation x, un angle d'incidence f et une erreur sur les vitesses Er.

A titre d'illustration, nous allons observer l'évolution de la probabilité de conflit lorsque :

l'anticipation x=

V T

d
augmente (voir figure 3.24), on fixera f=

p

2
, Er=5 %, V=400 kts, d=10 nm et on fera varier T de 0 à 120 minutes. On constate que la probabilité de conflit vaut 1 jusqu'à 20 minutes, après quoi elle décroît. On remarquera qu'elle décroît alors de moins en moins vite avec le temps.
l'angle f varie de 0 à p (voir figure 3.24), on fixera V=400 kts, d=10 nm, T=30 minutes, et Er=5 %. On observe que l'angle f a une très forte influence sur la probabilité de conflit. En effet, dans cet exemple, celle-ci varie de 0.75 à 1 selon que les avions convergent à 20 degrés ou 120 degrés. On observe donc que le risque de conflit est d'autant plus faible que l'angle d'incidence est faible. Or on sait que le conflit est d'autant plus difficile à résoudre que cet angle est faible. On en déduit que les conflits d'avions convergents sont à la fois moins certains et plus difficiles à résoudre. La prise de risque est donc plus grande dans le choix de l'instant de résolution de conflit.
le pourcentage d'erreur Er varie de 0 à 20 % (voir figure 3.25), on fixera V=400 kts, d=10 nm, T=30 minutes, et f=

p

2
. La sensibilité de la probabilité de conflit au pourcentage d'erreur est semblable à sa sensibilité au temps d'anticipation.
l'angle f varie de 0 à p et le temps d'anticipation varie de 0 à 120 minutes (voir figure 3.25), on fixera V=400 kts, d=10 nm et Er=5 %. On visualise a lors bien le fait que la probabilité de conflit est fortement liée à l'angle d'incidence. Le choix du moment de résolution est donc fortement dépendant de la géométrie du conflit.

Figure 3.22: Probabilité de conflit en fonction du temps d'anticipation en minutes (à gauche), de l'angle d'incidence en degrés (à droite).

Figure 3.23: Probabilité de conflit en fonction du pourcentage d'erreur sur les vitesses (à gauche), en fonction de l'angle d'incidence et du temps d'anticipation (à droite).

Il apparaît donc au travers de ces résultats qu'une fois de plus, les conflits à faible incidence sont ceux qui posent le plus de problèmes. Moins ``certains'', ils sont plus difficiles à résoudre.

3.4.3 Espérance de coût de résolution de conflit.

Si l'on veut résoudre un conflit de façon certaine avec un temps d'anticipation T, il faut intégrer l'incertitude sur les vitesses dans la résolution. Ainsi au lieu de séparer des points par séparation standard, il faut séparer de cette séparation standard des segments de droite dont la longueur augmente avec le temps. Pour cela, on peut mesurer l'allongement de la trajectoire en nautiques lorsque l'on bouge un des deux avions en fonction du temps d'anticipation engendré par la résolution d'un conflit. Pour ce calcul, nous garderons les mêmes caractéristiques que précédemment pour les deux avions et choisirons un angle d'incidence de

et une erreur sur la vitesse de 5 %. Le calcul est fait dans les deux modélisations offset et point tournant (voir figure 3.26). On observe qu'avec la modélisation par offset, l'évitement le plus tardif est le plus économique. La courbe est en fait une droite. L'allongement est donc une fonction linéaire du temps d'anticipation. Pour la modélisation point tournant, au phénomène d'accroissement de l'allongement provoqué par l'incertitude s'ajoute un phénomène inverse. Plus l'on anticipe le conflit, plus la déviation de l'avion mobile sera faible, et si l'on s'y prend tard, l'allongement sera fort.

Figure 3.24: Allongement de la trajectoire en nautiques en fonction du temps d'anticipation, modélisation par offset (à gauche), modélisation point tournant (à droite)

On souhaiterait déterminer le moment optimal pour résoudre un conflit à deux avions en tenant compte de ce phénomène d'incertitude. Pour cela, il faut préciser quel est le critère d'optimalité retenu. N'ayant pas de certitude sur l'existence ou non d'un conflit lorsque le temps d'anticipation augmente, on ne pas parler de coût de résolution. Par contre on peut définir l'espérance du coût de résolution de conflit. Pour tout temps d'anticipation T, on connaît la probabilité pour que le conflit se produise et le coût associé à ce temps. Il suffit de multiplier les deux pour obtenir l'espérance du coût de résolution du conflit sachant que s'il n'y a pas de conflit, le coût de résolution est nul. On observera la figure 3.27 pour les deux modélisation offset et point tournant. Si pour l'offset, l'espérance de coût de résolution est minimale pour un temps d'anticipation le plus faible possible, pour la modélisation point tournant, dans cet exemple, le coût de résolution est minimal pour une anticipation de 20 minutes ou 130 nautiques.

Les calculs que nous venons de présenter permettent de conclure qu'une résolution par offset doit être la plus tardive possible. Pour une résolution par point tournant, il existe un compromis qui minimise l'espérance de coût de résolution du conflit. Ce compromis dépend de l'incertitude sur les vitesses et de la configuration du conflit. Cette étude n'était pas exhaustive mais propose un critère d'évaluation de l'instant optimal de début de résolution de conflit.

Figure 3.25: Espérance du coût de résolution en fonction du temps d'anticipation, modélisation par offset (à gauche), modélisation point tournant (à droite).

3.5 Modélisation pour la résolution de conflits complexes

Les études précédentes ont conduit aux conclusions suivantes :

On peut modéliser une manoeuvre d'évitement horizontale entre deux avions par un point tournant.
La modélisation par offset reste indispensable pour des cas de rattrapages.
L'incertitude sur les vitesses des avions et sur leurs taux de montée doit être prise en compte et fait apparaître dans le cas de la modélisation point tournant un temps ``idéal'' de début de manoeuvre.

D'autres contraintes pratiques sont maintenant introduites dans le modèle afin de pouvoir résoudre des conflits complexes mettent en jeu plusieurs avions :

Les angles de déviation pour le point tournant et l'offset seront discrétisés et pourront donc prendre pour valeur : -30, -20, -10, 0, 10, 20 et 30 degrés.
Un manoeuvre commencée ne pourra pas être remise en cause, on pourra néanmoins modifier son ampleur sans en modifier la structure.
Le système ne proposera pas de régulation de vitesse (le lecteur trouvera partie 3.2.1 des arguments justifiant ce choix.
Les manoeuvres d'évitement proposées sont horizontales. Le système ne pourra donc pas modifier la trajectoire verticale d'un avion même s'il peut faire tourner des avions évolutifs ( en montée ou en descente). Une telle hypothèse est relativement restrictive : un certain nombre de résolutions ne seront plus optimales, en particulier, lorsqu'un des avions impliqué dans un conflit est évolutif. Les contrôleurs le savent bien et essayent d'employer ce genre de résolution le plus fréquemment possible pour les avions qui ne sont pas en palier. Ces manoeuvres sont souvent optimales par rapport à une déviation horizontale lorsque les avions sont sur une route identique ou opposée. Se restreindre au plan horizontal n'est pas un objectif et la dimension verticale devra nécessairement être intégrée dans les évolutions futures. Néanmoins l'ajout de telles manoeuvre ne complexifie pas de façon significative le modèle.

Nous obtenons donc le modèle suivant (figure 3.28) où une manoeuvre est déterminée par les 4 paramètres suivants :

la date de début du virage d'éloignement t₀ ;
la date de fin du virage d'éloignement t₁ ;
la date de début du virage de retour sur la trajectoire initiale t₂.
l'angle de déviation de la manoeuvre : a ;

Figure 3.26: Modèles de manoeuvre.

Les différents t_i représentent des dates relatives. L'instant t=0 correspond au début de la prévision. A cette date, la position de l'avion est connue sans incertitude. On la considère comme la position initiale de l'avion.

Le virage de retour a évidemment le même angle a mais dans le sens opposé. La durée de la phase de retour est donc égale à la durée de la phase d'éloignement. La date de fin de manoeuvre, notée t₃ n'est donc pas un paramètre de la manoeuvre et on a : t₃ = t₂ + t₁ - t₀

Si on est en présence d'un point tournant, on aura t₂ = t₁.

Un tel modèle réduit donc la taille du problème de façon significative. Pour un conflit impliquant n avions, la dimension de l'espace de recherche sera de 4n. Ceci nous permettra de résoudre des gros conflits sans avoir à explorer un domaine de solutions admissibles trop vaste.

3.5.1 Modèle de cluster

Nous nous proposons donc de résoudre non pas uniquement des conflits élémentaires mais des situations plus complexes. Nous introduisons ici la notion de clusters. Un cluster est le résultat d'une fermeture transitive dans l'ensemble des conflits sur un horizon temporel fixé H. Si un avion A est en conflit avec B à l'instant t et B est en conflit avec C à l'instant t+Dt avec Dt < H alors A, B et C appartiennent au même cluster. Ainsi dans la figure 3.29, les avions A et B ne sont jamais en conflit mais ils appartiennent au même cluster. Une déviation de C pour éviter B peut lui permettre d'éviter A. L'optimisation doit donc se faire de façon globale.

Figure 3.27: Exemple de cluster.

3.5.2 Déroulement en temps réel

Un des objectifs retenus est de pouvoir détecter et résoudre les conflits en temps réel. Fixons nous un délai D. La situation doit être revue toutes les D secondes à partir de nouvelles données. Le système dispose donc d'un temps inférieur à D pour analyser la nouvelle situation et trouver les trajectoires optimales sans conflit pour l'ensemble des avions impliqués dans la fenêtre d'anticipation F_a. Le reste de l'intervalle D est consacré à la transmission des manoeuvres du sol vers le bord. Durant l'intervalle D, les avions volent toujours. Le système ne peut donc changer la trajectoire prévue de chacun des avions pendant les D premières secondes de F_a. Ces trajectoires correspondent donc à la prévision effectuée au tour précédent. Par contre le système reste libre de modifier toutes les trajectoires entre D et F_a à l'exception des branches de retour en point tournant ou en offset. En effet, cette partie de la manoeuvre est complètement déterminée par le début de la manoeuvre.

Appelons t le temps relatif utilisé par le système de résolution, T l'échelle de temps absolu et T₀ la date de début de la première itération de notre processus de résolution. A chaque itération i, le processus analyse une nouvelle situation entre t=0 et t=F_a. La situation prévue à l'instant t=0 correspond à la situation réelle existant à T=T₀ + iD en considérant que i=0 pour la première itération. La figure 3.30 peut alors se commenter de la façon suivante :

Figure 3.28: Séquencement en temps réel

itération 1 (T=T₀) :: Le système prévoit un offset pour t > 2D.
itération 2 (T=T₀+D ) :: Le système a réduit l'offset en un point tournant prévu pour t > D.
itération 3 (T=T₀+2D ) :: Le système a réduit le point tournant prévu. La date de début de manoeuvre est prévue pour t < D. Ce début de manoeuvre sera donc communiqué au pilote. Par rapport au modèle présenté, on a fixé les variables t₀ et sens.
itération 4 (T=T₀+3D ) :: L'avion a effectué son début de manoeuvre et le système prévoit toujours le même point tournant. Le reste de la manoeuvre est donc à son tour figées : t₁ et t₂ (en l'occurrence t₁=t₂ car il s'agit d'un point tournant).
itération 5 (t=T₀+4D ) :: L'avion est sur sa branche de retour.

3.6 Résolution par algorithmes génétiques

La modélisation simplifiée par point tournant ou offset permet dans le cas de conflits à deux avions d'approcher avec une perte acceptable les trajectoires optimales. Dans la mesure où il parait peu envisageable de donner à un avion plus d'un ordre de manoeuvre à la fois, cette modélisation pourra être conservée pour la résolution de conflits à n avions avec n>2. L'intérêt principal d'une telle modélisation est qu'elle permet de réduire fortement la taille de l'espace de recherche. On peut désormais définir une trajectoire d'évitement par la donnée d'au plus trois temps et d'un angle de déviation.

On a pu également observer que résoudre un conflit en modifiant seulement la vitesse des avions requiert une prise de décision fortement anticipée compte tenu des faibles marges de manoeuvre des avions (en route) et des incertitudes sur leurs tenues de vitesses. Une modification de vitesse pourrait donc être efficace à condition de pouvoir la combiner avec des manoeuvres de type point tournant ou offset, hypothèse que nous avons pour l'instant écartée.

Enfin, afin de pouvoir rendre le modèle réaliste, il est essentiel de tenir compte de l'incertitude sur les vitesses, taux de montée et de descente dans le modèle. La notion de séparation standard est ainsi remplacée par des volumes d'occupation de l'espace, se déformant avec le temps, représentant les positions potentielles futures des avions.

Tous ces éléments, associés à la forte complexité du problème, nous ont amenés à utiliser les algorithmes génétiques pour résoudre les conflits à plusieurs avions.

3.6.1 Codage

Pour le problème de résolution de conflits, les variables t₀, t₁, t₂ et a de chaque avion sont disposées dans une matrice (voir figure 3.31) qui constitue un individu de la population. On appellera gènes les variables t₀, t₁, t₂ et a de chaque avion. Un élément de population contient donc 4 n gènes.

Figure 3.29: Codage d'un individu à n avions.

3.6.2 Génération de la population initiale

Dans le modèle que nous avons défini partie 3.28, l'algorithme de résolution de conflits est ré-initialisé pour chaque cluster toutes les D minutes. Il se peut donc que l'algorithme ait à prendre en compte des avions déjà engagés dans certaines manoeuvres de résolution. Ces avions sont alors soumis à certaines contraintes gérées à priori par une procédure chargée de vérifier leur respect à toute étape de l'algorithme. Ces contraintes sont les suivantes :

Lorsqu'un conflit à n avions est fourni à l'algorithme génétique, il se peut que certains gènes correspondant à des manoeuvres déjà entamées ou qui doivent être entamées avant D soient imposés à l'algorithme génétique. Ainsi, tous les gènes t₀, t₁, t₂ dont la valeur est inférieure à D sont imposés dans l'algorithme et ne pourront plus être modifiés par la suite. De même si t₀<D alors l'angle a correspondant est fixé et ne pourra plus être modifié. Toutes ces variables ne seront donc pas initialisées de façon aléatoire.
On doit vérifier que t₀£ t₁£ t₂. Pour des avions arrivant à destination, il certaines manoeuvres doivent être terminées avant une certaine échéance t_3max de sorte qu'il faut vérifier que t₃=t₂+t₁-t₀£ t_3max.

Enfin, pour que l'algorithme génétique puisse détecter rapidement les solutions sans conflit, il sera fait en sorte que chaque avion de chaque chromosome de la population ait initialement une chance sur 3 de ne pas être dévié.

Les contraintes liées à la séparation des avions sont par contre directement introduites dans la fitness et ne sont pas gérées à priori mais à posteriori.

3.6.3 Fitness

La fonction fitness doit prendre en compte à la fois les contraintes de séparation des avions et la qualité de la résolution lorsque celle-ci est réalisée. Réduire à une seule valeur fitness toutes les calculs effectués pour l'évaluation d'un individu est très réducteur et une grande partie de l'information utile est perdue dans des opérations d'additions (voir [DAN94]). Aussi, la fonction fitness unique sera remplacée par une matrice triangulaire inférieure F. Si le cluster à résoudre comprend n avions alors n sera la taille de la matrice F. Si i ¹ j, alors F_i,j mesure la gravité du conflit entre l'avion i et l'avion j. S'il n'y a pas de conflit, F_i,j=0, F_i,j croit avec la gravité du conflit. F_i,i mesure la pénalisation de la trajectoire de l'avion i provoqué par ses manoeuvres. Cette matrice fitness d'où on pourra extraire une fitness scalaire contient beaucoup plus d'information qu'une fitness scalaire et permettra de définir les opérateurs de croisement et de mutation adaptés au problème de résolution de conflits.

Nous sommes en face d'un problème d'optimisation multi-critère. Nous avons retenu les critères suivants :

Le retard induit pour chaque avion doit être aussi faible que possible.
Le nombre d'avions déviés et le nombre total de manoeuvres doit être aussi faible que possible, il se peut donc que les retards ne soient pas partagés par tous les avions.
La durée d'une manoeuvre doit être aussi faible que possible pour pouvoir rendre le plus tôt possible un avion disponible pour une autre manoeuvre.
Les trajectoires doivent respecter les normes de séparation.

Détaillons le calcul des éléments de la matrice F.

Calcul des éléments de la diagonale

Pour prendre en compte à la fois le retard dû à la manoeuvre et la durée de la manoeuvre elle-même, on peut mesurer la surface S occupée par la résolution (figure 3.32). Cette surface augmente à la fois avec le retard induit et la durée de la manoeuvre. Il est intéressant de rappeler que cette notion de surface occupée est un des critères utilisés par le contrôleur pour décider d'une manoeuvre. Pour minimiser le nombre de manoeuvres, on ajoute à S le nombre de manoeuvres multiplié par un certain coefficient k. Pour un point tournant, il faut donc rajouter 2 k à S, pour un offset, il faut rajouter 3 k.

Figure 3.30: Surface occupé par la manoeuvre

F_i,i

S_i + k N_i

Évaluation des termes non diagonaux

A chaque pas de temps t, on évalue la différence (si elle est positive) C_t,i,j entre la séparation standard et la distance entre les segments i et j représentant les positions des avions i et j à t. Ces valeurs sont additionnées pour tous les temps t pour donner F_i,j, mesure du conflit entre i et j.

F_i,j

total time

t=0

(C_t,i,j)

A partir de la matrice F, et pour les besoins de l'opérateur de sélection, on est en mesure de calculer une fitness f scalaire de la façon suivante :

$ (i,j), F_i,j ¹ 0 Þ f

i ¹ j

F_i,j

" (i,j), F_i,j = 0 Þ f

F_i,i

On remarquera que cette fitness permet de distinguer les individus pour lesquels il reste des conflits (leurs fitness sont inférieures à 0.5) des individus où il n'y a plus de conflit (leurs fitness sont supérieures à 0.5).

3.6.4 Opérateurs de croisement et de mutation adaptés

Pour les clusters de grande taille, il est intéressant d'utiliser la séparabilité partielle du problème et d'introduire l' opérateur de croisement adaptés. Pour cela, à partir de la matrice fitness F, on peut définir pour l'avion ou le chromosome i sa fitness locale :

F_i=

j=1

(F_i,j)

L'opérateur de croisement est décrit par la figure 3.33. Après avoir choisi deux parents A et B, on compare les fitness locales de leurs avions (ces fitness sont notées A_i et B_i sur la figure 3.33). Pour l'avion i, si A_i £ B_i - d (d est une valeur permettant de moduler le déterminisme de l'opérateur) les deux enfants héritent de l'avion i du père A. Si B_i £ A_i - d, les deux enfants héritent de l'avion i du père B. Si aucune de ces deux conditions n'est respectée, les avions i des fils 1 et 2 sont deux combinaisons aléatoires des avions i des deux parents.

Figure 3.31: Opérateur de croisement adapté

De même, on pourra définir un opérateur de mutation adapté décrit par la figure 3.34. Après avoir choisi un individu à muter, un avion est choisi (sur la figure 3.34 l'avion 4 est choisi). Un avion i ayant une fitness F_i faible (c'est à dire inférieure à e où e module le déterminisme de l'opérateur) ne sera choisi que si toutes les fitness locales sont faibles.

Figure 3.32: Opérateur de mutation adapté

Ces opérateurs ont l'avantage d'être assez déterministes en début de convergence de sorte qu'une solution sans conflit (dont la fitness est supérieure à 0.5) peut être rapidement dégagée. Quand les solutions sans conflit deviennent suffisamment nombreuses, ces opérateurs deviennent moins déterministes et la recherche dans l'espace d'état devient plus large. L'association de ces opérateurs avec une méthode de sharing devient indispensable pour atténuer l'effet du déterminisme introduit.

3.6.5 Sharing simplifié

On se propose d'utiliser la méthode de sharing simplifiée suivante qui a l'avantage de distinguer de façon discrète deux solutions qui n'ont pas les mêmes caractéristiques. Ainsi, définissons la distance discrète suivante (a_i(A) est l'angle de déviation de l'avion i du chromosome A) :

deux individus A et B sont séparés par une distance nulle si :

" i Î [1,n] , a_i(A)=a_i(B)
deux individus A et B sont séparés d'une distance 1 si :

$ i Î [1,n] , a_i(A)¹ a_i(B)

Deux individus séparés par une distance nulle seront dits appartenir à la même classe. Si l'on applique la méthode de sharing clusterisé présentée précédemment, on remarque que cela revient à diviser la fitness de chaque individus par le nombre de représentants de sa classe.

3.6.6 Méthode locale en fin de convergence

Les algorithmes génétiques sont très efficaces pour résoudre des problèmes d'optimisation combinatoire de grande taille mais leur efficacité est moindre pour une recherche locale d'une bonne précision. En conséquence, il est très utile, après la dernière génération de l'algorithme génétique d'appliquer une méthode d'optimisation locale (de type gradient) sur la meilleure solution de chaque classe d'individus définie précédemment. La méthode locale utilisée est très simple : tous les gènes de tous les chromosomes de l'individu qu'on optimise sont successivement modifiés de façon à améliorer la fitness globale sans générer de nouveau conflits.

3.6.7 Applications numériques

Justification du modèle

Dans ce premier exemple, on considère un conflit très simple entre 2 avions (voir figure 3.35).

Le temps d'anticipation D est fixé à 2 minutes et la vitesse des avions à 400 noeuds avec une incertitude de 5 pour cent. Dans ce cas, si l'avion 0 a une vitesse sol de 380 noeuds et l'avion 1 une vitesse réelle de 420 noeuds, il n'y aura finalement pas de conflit (la séparation standard est de 4 nm). Au cas où les avions ne respecteraient pas leur trajectoire, l'algorithme calcule des solutions dans le cas le plus défavorable. La figure 3.36 donne le résultat de l'algorithme génétique à t=3 minutes, 5 minutes, 7 minutes, 9 minutes, 11 minutes and 13 minutes. Les traits épais représentent les deux minutes à venir qui ne peuvent être modifiées. Les traits fins décrivent les trajectoires optimales provisoires calculées par l'algorithme génétique.

Figure 3.33: Conflit à deux avions

Figure 3.34: t=3, 5, 7, 9, 11, 13 minutes

En raison de l'incertitude, la première optimisation donne des trajectoires robustes mais très pénalisantes. Au fur et à mesure que le temps passe, les trajectoires s'affinent car l'incertitude décroît. Finalement, à t=12 le conflit disparaît.

Un problème combinatoire

Dans cet exemple, 5 avions convergent vers le même point à une vitesse de 400 noeuds avec 3 pour cent d'erreur. D vaut ici 5 minutes. Les autres paramètres de l'algorithme génétique n'ont pas changé. La figure 3.37 donne les résultats. La distance minimale d'espacement des avions est de 6.01 malgré une forte incertitude sur les vitesses (3 %).

Figure 3.35: t=2, 6, 10, 14, 18, 22 minutes

Le tableau 3.5 donne la distance minimale observée entre les avions pour différents pourcentages d'erreur et différents temps d'anticipation. Il est clair à la vue de ce tableau que lorsque l'on a simultanément une forte incertitude et une grande anticipation la qualité de la résolution décroît fortement.

incertitude 0% 1% 2% 3% 4% 5%

1 mn 4.00 4.24 4.30 4.55 4.65 4.70

2 mn 4.03 4.35 4.52 5.00 5.30 5.77

3 mn 4.01 4.44 4.89 5.16 5.61 5.97

4 mn 4.02 4.50 5.02 5.63 6.10 6.68

5 mn 4.03 4.57 4.89 6.01 6.61 7.32

Table 3.5: Distance minimale entre les avions pour différents temps d'anticipation.

Les résultats représentés ne donnent que la meilleure solution de ce problème à 5 avions. L'algorithme génétique propose grâce au sharing d'autres solutions proches de la solution optimale (notamment la solution symétrique dans le cas ci-dessus).

Plusieurs solutions quasi-optimales

Le but de cet exemple est de montrer que l'algorithme génétique est capable de générer plusieurs solutions proches de l'optimum lorsqu'elles existent. On a, après la première optimisation conservé toutes les solutions admissibles ayant une fitness au moins égale à 95 % de la meilleur fitness.

On peut voir figure 3.38 les solutions quasi-optimales proposées pour un conflit à trois avions.

Figure 3.36: Conflit à 3 avions, plusieurs solutions quasi-optimales

Efficacité des opérateurs adaptés

Pour tester l'efficacité des opérateurs de croisement et de mutation adaptés introduit en 3.33, nous proposons de résoudre un conflit impliquant chacun 20 avions. Ce conflit implique 20 avions convergeant simultanément sur un même point. Ce conflit a très peu de solutions car tous les avions sont en conflit deux à deux. En fait, deux solutions existent : dans la première, tous les avions tournent à droite, dans la seconde, tous les avions tournent à gauche. La figure 3.39 donne le résultat de l'optimisation.

Figure 3.37: 20 avions sans conflit

Pour étudier l'effet des opérateurs de croisement adaptés combinés à l'utilisation du sharing, 4 différents tests ont été effectués sur les deux conflits précédents en utilisant : les opérateurs adaptés sans sharing, les opérateurs adaptés avec sharing, les opérateurs classiques sans sharing, les opérateurs classiques avec sharing.

Figure 3.38: Meilleure fitness (avions en cercle

Pour ces quatre tests, nous avons mesuré pour chaque exemple la valeur du meilleur élément de population (figure 3.40) pour les 20 générations de l'algorithme génétique. On peut d'abord constater que les opérateurs adaptés sont très efficaces pour trouver des solutions admissibles . En effet, avec les opérateurs classiques, aucun des deux conflits n'est résolu avant la génération 20 (en fait, des tests montrent que la première solution admissible est obtenue après la génération 200). Avec les opérateurs adaptés, une solution admissible est toujours trouvée avant la génération 10 (Une solution est admissible si sa fitness est supérieure à 0.5). La figure 3.40 montre que le sharing a tendance a freiner la croissance de la fitness du meilleur élément. Cependant la fitness finale est aussi bonne lorsque l'on utilise le sharing que lorsque l'on ne l'utilise pas. Elle est même meilleure en utilisant le sharing lorsque le conflit est difficile à résoudre. Le sharing permet d'ailleurs d'obtenir dans ce dernier cas les deux solutions symétriques (tous les avions tournant à droite et tous les avions tournant à gauche).

Un conflit de rattrapage.

Le but de cet exemple est de montrer l'intérêt de la modélisation par offset dans le cadre d'un conflit en rattrapage. Dans l'exemple présenté 5 avions se suivent sur la même route. L'avion de tête est le plus lent (350 noeuds), l'avion de queue est le plus rapide (550 noeuds).

Figure 3.39: 5 avions sans conflit

Les résultats sont représentés figure 3.41. On observe que l'offset est utilisé pour les 4 avions les plus rapides, le plus lent n'étant pas dévié. La déviation est est d'autant plus importante que l'avion est rapide, ce qui reste en accord avec les conclusions de la partie 3.3.3.

Une résolution globale des clusters

Dans cet exemple, deux conflits indépendants à deux avions face à face sont regroupés dans le même cluster par l'intermédiaire d'un avion coupant leurs axes. La figure 3.42 donne le résultat de l'optimisation. On observe qu' une seule déviation de l'avion coupant les axes résout 4 conflits.

Figure 3.40: 5 avions sans conflit

3.6.8 Architecture générale du simulateur de trafic

Les tests effectués précédemment montrent que l'algorithme génétique utilisé est très performant sur des cas d'école. Il convenait donc de tester l'algorithme dans un environnement réel.

L'architecture du simulateur de trafic (figure 3.43) est la suivante :

Figure 3.41: Architecture générale

Le processus P1 est le simulateur de trafic proprement dit décrit dans la section 3.1.1.
Le processus P2 est chargé de détecter les paires d'avions en conflit, de fabriquer les clusters d'avions par fermeture transitive des paires d'avions en conflits. Il vérifie également les trajectoires nouvelles proposées par P3.
Le processus P3 est l'algorithme de résolution de conflits décrit dans le chapitre précédent.

L'architecture du simulateur de trafic est détaillée figure 3.44.

Figure 3.42: Architecture détaillée du simulateur de trafic

Le processus P1 envoie les positions courantes des avions et les plans de vols au processus P2. P2 construit alors les trajectoires prévues pour les 20 minutes à venir et détecte les paires de conflits. P2 prend en compte les incertitudes sur les vitesses (voir la partie 3.4). Après avoir détecté les paires d'avions, P2 construit les clusters d'avions par fermeture transitive des paires d'avions sur les 20 minutes à venir. Les clusters sont en fait les classes d'équivalence de la relation ``est en conflit avec''. Tous les clusters sont ensuite résolus par le résolveur de conflits de façon indépendante. Le résolveur de conflits retourne à P2 les trajectoires modifiées. P2 vérifie alors que les trajectoires modifiées d'un cluster ne génèrent pas de nouveaux conflits avec les avions d'un autre cluster. Si tel est le cas, les ordres de résolutions pour les 5 minutes à venir sont envoyés à P1. Si le résolveur a généré de nouveaux conflits entre des avions de deux clusters différents, ces deux clusters sont regroupés, formant un nouveau cluster sur lequel on applique le résolveur de conflits. Ce processus est répété jusqu'à ce que tous les conflits disparaissent. Ce processus converge nécessairement. Dans le pire des cas, tous les avions en conflits dans les 20 prochaines minutes se retrouvent dans le même cluster. Cependant, le processus est d'autant plus efficace qu'il est en présence de nombreux clusters que l'on résoudra en parallèle ¹⁶ .

3.6.9 Résultats sur une journée de trafic réelle

Les expérimentations pratiques sur le simulateur de trafic sont toujours en cours mais certains résultats sont déjà disponibles [Cha95].

Nous décrivons ici un test effectué avec les plans de vols du 12 novembre 1992. 4835 vols ont été enregistrés ce jour-là. Le pourcentage d'incertitude sur les taux de montée et sur la vitesse ont été fixés à 1% et les séparations standards fixées à 6 nm et 1000 pieds. Les routes directes ont été utilisées (les avions ne transitant pas par des balises, mais rejoignant directement leur destination). Seuls les conflits ``en route'' ( au dessus de 6000 pieds) ont été considérés.

Lorsque cette journée est simulée avec un algorithme de détection ne prenant pas en compte l'incertitude, 665 conflits au dessus de 6000 pieds sont détectés.

Lorsque une simulation complète est exécutée, le processus P2 détecte 4408 paires d'avions en conflits ne représentant en fait que 908 conflits différents (un certain nombre de conflits durent plus de 5 minutes et sont donc détectés plusieurs fois). 1888 clusters ont étés proposés au résolveur de conflits. Il en a résolu 1541. 260 ont été presque résolus (le conflit prévu n'a finalement pas eu lieu en raison de l'incertitude adoptée). Le résolveur a échoué sur 80 conflits représentant en fait 23 différents conflits (répétés dans le temps). En observant ces conflits, on a pu remarquer qu'ils étaient tous dus à des décollages, atterrissages ou entrées dans l'espace aérien français simultanés (ces conflits apparaissent car des données plan de vol non régulées ont été utilisées). Dans ce cas, le résolveur de conflit ne peut bien évidemment pas séparer les avions. Ne considérer que les conflits au dessus de 6000 pieds ne suffit pas à s'affranchir de ce problème. Un algorithme de pré-régulation des plans de vol est en cours d'élaboration pour résoudre ce problème.

3.6.10 Conclusion

Les Algorithmes Génétiques se sont avérés très efficaces pour résoudre des conflits pouvant impliquer jusqu'à une vingtaine d'avions. L'introduction d'un opérateur de croisement adapté aux fonctions partiellement séparables combiné avec une méthode de sharing s'est toutefois révélée très utile. On notera que l'efficacité de cet opérateur peut également se constater sur des fonctions tests classiques partiellement séparables. La fonction d'évaluation utilisée est très simple mais pourrait être affinée autant qu'on le souhaite. Les résultats que nous avons obtenus sont très encourageants. Ils le sont d'autant plus que le résolveur de conflit ne donne pour l'instant que des résolutions dans le plan vertical.

3.7 Programmation linéaire et AG

3.7.1 Introduction

Nous avons présenté dans la section précédente la modélisation par offset qui linéarise les contraintes de séparation. Rappelons que, si l'on a fixé le sens de l'offset et l'ordre de passage des n avions, on a à résoudre, pour obtenir les valeurs des offsets, un problème d'optimisation linéaire à n inconnues (les valeurs des offsets des n avions), et à

n(n+1)

contraintes (ou à

n(n+2)

contraintes, si on borne les valeurs des offsets).

Notons que l'on a tout de même 2

ⁿ⁽ⁿ⁺¹⁾

façons possibles de fixer les sens des offsets et les ordres de passage. En effet, pour chaque avion, il y a deux sens de déviation possibles : à gauche, ou à droite. Et pour chaque couple d'avions (a_i,a_j) (il y en a

n(n-1)

), il y a deux ordres de passage possibles au point d'intersection C_ij de leurs trajectoires : soit a_i passe après a_j, soit a_i passe avant a_j. Dès que le nombre d'avions impliqués dans le conflit augmente, il devient beaucoup trop long d'utiliser une technique d'énumération exhaustive de toutes les combinaisons possibles : pour 5 avions, il y en a 32768, et pour 6 avions, il y en a 2097152.

Un problème linéaire peut en revanche se résoudre facilement, à l'aide par exemple d'un simplex, mais on n'obtient alors qu'un optimum local, et l'on voit bien que la forte combinatoire du problème empêche de tester l'ensemble des configurations possibles dès que le nombre d'avions devient un peu important.

Notre idée est donc d'utiliser un algorithme génétique qui générera des ``configurations'' : une configuration représente la donnée des sens de déviation et des ordres de passage, nécessaire pour établir les conditions linéaires de séparation des avions. Une fois la configuration choisie, la résolution du problème linéaire donnera la valeur de l'offset à faire subir à chaque avion de manière à minimiser la somme des retards.

3.7.2 Codage des données du problème

Le sens de déviation de chaque avion ne peut prendre que deux valeurs différentes (offset à droite ou offset à gauche). De même, si l'on considère le couple d'avions (a_i,a_j), et que l'on considère que les trajectoires des deux avions sont portées par des droites sécantes, il n'y a que deux ordres de passage des avions au point C_ij, point d'intersection de leurs trajectoires qui soient possibles sans conflit : soit a_i passe en C_ij après a_j, soit a_i passe avant. Ces données peuvent, de même que les sens des offset, se coder de manière binaire On utilise donc le mode de codage le plus classique pour les chromosomes dans le cadre des algorithmes génétiques : une séquence de bits, dans laquelle chaque bit traduit la valeur, ou l'état d'une donnée du problème.

Pour un problème à n avions, les n premiers bits (à partir de la droite), codent les sens des offset de chaque avion : si le i^eme bit est un 1, l'avion a_i sera dévié vers la gauche ; il sera dévié vers la droite si ce bit est un 0. Les

n(n-1)

bits suivants codent le sens de passage des avions pour chaque couple d'avions. On numérote les couples d'avions selon l'ordre suivant : (a₁,a₂), (a₁,a₃),...(a₁, a_n), (a₂, a₃),...(a_n-1,a_n). Si pour le couple d'avions (a_i,a_j), où i < j, a_i passe derrière a_j, le bit correspondant est un 1; ce bit est un 0 si a_i passe devant a_j.

Figure 3.43: Codage d'une configuration par un entier

La figure 3.45 montre un exemple du codage d'une configuration pour un problème d'évitement impliquant 4 avions. Le chromosome correspondant est codé par l'entier 691; l'avion a₁ est dévié vers la gauche, l'avion a₃ est dévié vers la droite, l'avion a₁ passe derrière l'avion a₂ (5^eme bit de 691), et l'avion a₂ passe devant l'avion a₄ (9^eme bit de 691).

3.7.3 Croisement et mutation

Le principe de la technique de croisement que nous avons utilisé est de choisir aléatoirement les bits dont l'enfant E₁ hérite du parent P₁. Ses autres bits lui viendront du parent P₂, et l'héritage de l'enfant E₂ sera déterminé comme étant le complémentaire de celui de E₁.

Pour la mutation, on choisit aléatoirement un des bits de la séquence utilisée pour le codage d'une configuration, et on le modifie.

3.7.4 Évaluation de la fitness

Nous nous sommes proposé de prendre comme fitness le retard minimal associé à une configuration, retard obtenu au moyen du programme d'optimisation linéaire, comme critère d'adaptation de l'élément de la population correspondant à cette configuration.

Cette méthode présente un inconvénient majeur : certaines configurations mènent à des problèmes d'optimisation infaisables, c'est à dire pour lesquels les contraintes ne peuvent pas être toutes satisfaites simultanément. Prendre une fitness nulle pour les éléments de la population correspondant à de telles configurations ne serait pas une solution satisfaisante : une configuration menant à un problème infaisable peut être mieux adaptée qu'une autre, en ce sens qu'elle peut être plus proche qu'elle d'une configuration menant à un problème faisable. Si une configuration mène à un problème d'optimisation infaisable, on essaiera de supprimer une contrainte, si les contraintes restantes ne peuvent toujours pas être satisfaites simultanément, on en supprimera une seconde, et ainsi de suite, jusqu'à ce que les contraintes restantes soient simultanément satisfiables. Cette méthode se base sur l'idée intuitive selon laquelle un problème d'optimisation infaisable est d'autant plus ``proche'' d'un problème faisable qu'il y a peu de contraintes à supprimer pour que les contraintes restantes puissent être toutes simultanément satisfiables. La fitness d'une configuration ``infaisable'' sera pénalisée en fonction du nombre de contraintes qu'il a fallu supprimer pour trouver une configuration satisfiable, mais ne sera donc pas nulle.

3.7.5 Résultats

L'évaluation des résultats obtenus pose le problème suivant : il est difficile d'obtenir par une autre méthode une solution dont on sache qu'elle est optimale, pour la comparer à la solution obtenue grâce à l'algorithme ci-dessus. De plus l'algorithme génétique est un algorithme stochastique : pour évaluer son efficacité, il faut pouvoir le faire tourner un grand nombre de fois, et considérer la moyenne et la distribution des résultats obtenus.

Conflit à cinq avions

Dans le cas d'un conflit mettant en jeu 5 avions, il est encore possible de traiter par un programme d'optimisation linéaire de manière systématique et déterministe toutes les combinaisons possibles de sens de déviation et d'ordre de passage (il y en a 32 768), et de comparer tous les résultats obtenus, afin de déterminer la meilleure solution.

Nous considérons pour cela l'exemple suivant : les avions vont à la même vitesse (400 kts), ils sont au temps t_o régulièrement répartis sur un demi cercle de centre C (et de rayon 100 Nm), et leurs trajectoires se coupent en C (voir figure 3.46). La norme de séparation est de 7 Nm. On obtient alors deux solutions optimales équivalentes : soit les quatre premiers avions sont déviés vers la droite, tandis que le cinquième n'est pas dévié, et si i<j, a_i passe derrière a_j, soit le premier avion n'est pas dévié, et les quatre suivants sont déviés vers la gauche, et si i<j, a_i passe devant a_j. C'est cette dernière solution qui est représentée sur la figure 3.46.

Pour un conflit à 5 avions, le programme a été lancé 50 fois sur l'exemple présenté ci-dessus, avec 150 éléments de population et pendant 100 générations.

La figure 3.46 montre la répartition du nombre d'appels au programme d'optimisation linéaire nécessaire à l'obtention d'une solution optimale.

Figure 3.44: Cas à 5 avions

Ces résultats sont à comparer au fait que pour parcourir toutes les configurations, il faut effectuer 32 768 appels au programme linéaire (ce qui correspond à un temps de calcul de 108 secondes). Le gain en nombre d'appels au programme linéaire est beaucoup plus sensible dans le cas d'un conflit à 6 avions, dont la combinatoire est beaucoup plus importante. Nous allons étudier plus en détail les résultats obtenus dans ce cas.

Conflit à six avions

Les solutions obtenues dans le cas d'un conflit à 6 avions sont plus délicates à vérifier. Nous avons appliqué la méthode décrite ci-dessus à un conflit à 6 avions comparable au conflit à 5 avions présenté dans la section précédente : les avions vont à la même vitesse (400 kts), ils sont au temps t_o régulièrement répartis sur un demi cercle de centre C (et de rayon 100 Nm), et leurs trajectoires se coupent en C (voir figure 3.47). La norme de séparation est toujours de 7 Nm.

Le programme a été utilisé avec les mêmes paramètres que dans le cas à 5 avions. Sur les 50 fois essais, nous avons obtenu une des deux meilleures solutions 39 fois. Il a fallu en moyenne 23000 appels au programme d'optimisation linéaire pour obtenir une de ces solutions. La figure 3.47 montre la répartition de ce nombre d'appels.

Figure 3.45: Cas à 6 avions

Nous rappelons qu'un parcours exhaustif de tous les cas de figure en nécessite 2097152.

3.7.6 Conclusion

Beaucoup de paramètres ayant permis d'atteindre ces résultats pourraient encore être ajustés de manière à améliorer l'efficacité de la méthode présentée ici (notamment les formes exactes des fonctions utilisées pour le calcul de la fitness des éléments). Cependant les résultats obtenus, surtout avec l'exemple à 6 avions, montrent que cette méthode peut s'avérer intéressante sur le plan théorique. Pourtant, sur le plan pratique, cette méthode présente un inconvénient majeur : la trajectoire des avions doit nécessairement être rectiligne uniforme. Or, la vitesse d'un avion varie ne serait-ce qu'en raison d'un changement d'altitude. D'autre part, cette méthode ne permet pas de modéliser simplement l'incertitude sur les vitesses. En conclusion, la résolution par techniques linéaires ne nous semble pas utilisable pour résoudre des conflits ``réels''.

3.8 Techniques de parcours de graphe

Les essais faits avec les techniques classiques de parcours de graphe sont restés à un stade préliminaire et mériteraient d'être repris en profondeur. Les travaux avaient été effectués par Hervé Gruber [Gru92].

3.8.1 Algorithme de type A^*

Les algorithmes de type A, dont l'algorithme A^* ([Pea90, Pea84, FG87, Far96], sont classiquement utilisés en Intelligence Artificielle et en Robotique depuis de nombreuses années. Le coût à minimiser est la somme des distances parcourues par les avions pour rejoindre leur destination, et l'heuristique est simplement la somme des distances restant à parcourir, en supposant que les avions peuvent rejoindre directement leur destination. Cette heuristique est clairement minorante, garantissant ainsi l'optimalité de la solution.

La modélisation choisie par Hervé Gruber ne permettait pas de résoudre des conflits à plus de deux avions, que ce soit de façon optimale ou même sous-optimale. Nous avons modifié légèrement cette modélisation : ici, un avion est dévié à partir d'un instant t₀ de 30 degrés à gauche ou à droite pendant un temps t₁, puis regagne directement sa destination.

Figure 3.46: Résolution d'un conflit à deux avions de façon optimale et d'un conflit à cinq avions de façon sous optimale

Il est alors possible de résoudre de façon optimale des conflits à deux avions en un temps très court (de l'ordre de quelques secondes). Cependant, il reste impossible de résoudre des conflits ne serait-ce qu'à trois avions. La raison en est simple. En utilisant l'heuristique présentée ci-dessus, et notre modélisation, l'algorithme A^* tend à reprendre la génération des états après un conflit dès le début de la trajectoire. C'est une mauvaise stratégie de résolution. En effet, les avions ont alors de fortes chances de se retrouver à nouveau en conflit au même point. Il vaut en fait mieux essayer de reprendre la génération des états le plus près possible du point de conflit, car une déviation à ce moment là à de plus fortes chances de résoudre. On peut favoriser ce comportement en multipliant la valeur de la fonction heuristique par un facteur de l'ordre de 1.2 (cela se comprend aisément). On obtient alors des résolutions sous-optimales, mais en un temps beaucoup plus réduit. Par exemple, la résolution d'un conflit à deux avions ne prend plus que quelques centièmes de seconde, et l'on parvient même à résoudre des conflits à cinq avions (en un temps important cependant, de l'ordre de plusieurs minutes). Cependant, le conflit présenté figure 3.48 est simple dans sa structure (avions en face à face). Dans le cas de conflits plus complexes, nous ne sommes pas parvenus à obtenir des résultats dans des temps raisonnables (moins d'une heure).

3.8.2 Méthode de plus forte pente

Elle consiste à développer le fils de plus faible coût parmi ceux qui ont été créés à la dernière génération. Au lieu de trier tous les états, on ne trie en fait que les états créés à chaque génération. On s'attend donc à trouver très vite une solution qui n'est pas nécessairement optimale. Les résultats sont en fait très surprenants. Ce comportement s'explique par le fait que la recherche ``s'égare'' dans des trajectoires inattendues : les deux avions volant parallèlement tout en maintenant la distance de séparation et réduisant la distance au but.

Le résultat obtenu lorsque l'on fixe la durée des pas de calcul sans limiter leur nombre, montre de façon comique, ce à quoi peut aboutir cette méthode trop simpliste (figure 3.49).

Figure 3.47: Trajectoires fantaisistes obtenues par la méthode du gradient (n=11)

3.8.3 Conclusion

Les deux méthodes précédemment évoquées montrent les deux écueils duaux, presque caricaturaux, auxquels on se trouve confronté lorsque l'on travaille sur des algorithmes de parcours de graphe. D'un côté un algorithme garantissant l'optimalité pour la résolution, mais lent et coûteux en mémoire, de l'autre un algorithme extrêmement rapide mais fournissant des solutions inutilisables.

Il est clair qu'un algorithme aussi primitif que la méthode de plus forte pente est inapplicable. En revanche, les résultats connus sur la complexité A^* ne permettent guère d'espérer résoudre des conflits impliquant trop d'avions avec cet algorithme. En effet, le nombre de noeuds de A^* peut-être considéré comme proportionnel au nombre de noeuds du graphe au carré. Or, dans le cas qui nous intéresse, le nombre de noeuds du graphe croît de façon exponentielle avec le nombre d'avions (on peut en fait montrer que dans le cas où notre heuristique est minorante, la complexité du problème croît comme s⁴ⁿ où s est le nombre de pas de temps et n le nombre d'avions).

Nous pensons cependant fermement que cette direction de recherche doit être reprise sérieusement. Il faut en particulier s'intéresser à des algorithmes de ``moyen terme'' (A_e, développement partiel, etc) qui nous permettraient de mieux tirer partir de notre connaissance du problème dans le développement des états. Il s'agit là d'une direction de recherche à reprendre.

3.9 Résolution réactive et autonome

3.9.1 Méthodes réactives à modèle physique

Présentation

Les méthodes de résolution décrites dans ce paragraphe sont radicalement différentes de celles évoquées précédemment. Le projet ATLAS est le premier projet à avoir envisagé l'hypothèse d'avions autonomes [DA93] au plan européen. Cette hypothèse a été également étudiée en détail par Karim Zeghal [Zeg93, Zeg94] dans sa thèse. Il introduit la notion de coordination d'actions grâce à différentes forces qui s'exercent sur les agents, dans notre cas, les avions. Il définit ainsi trois types de forces qui devront agir suivant l'urgence :

Les forces attractives qui permettent aux avions d'atteindre leur objectif (une balise ou leur destination finale par exemple).
Les forces répulsives qui permettent aux avions d'éviter un obstacle proche donc dangereux. Cet obstacle peut être un avion ou une zone interdite.
Les forces de glissement qui permettent de contourner les obstacles. Les avions ont alors une action coordonnée (voir figure 3.50). Un force de glissement est définie de la manière suivante : si l'on observe l'équipotentielle de danger passant par l'avion, une force de glissement est tangente à cette équipotentielle alors que la force répulsive est normale à cette équipotentielle. Il y a donc plusieurs forces de glissement possibles. Si l'on reste dans le plan horizontal, la figure 3.50 montre que l'on peut définir deux sens de glissement (à droite ou à gauche). Le sens optimal (il s'agit ici d'optimalité locale, pour l'avion concerné) est celui qui favorise le rapprochement vers l'objectif. Dans le cas d'un obstacle mobile, Karim Zeghal définit une action coordonnée d'évitement. Si deux avions arrivant au même point suivent des forces de glissement complémentaires, alors l'évitement peut se faire de façon très efficace. Dans le cas simple de deux avions (voir figure 3.50), on projette par exemple la vitesse relative sur l'équipotentielle de danger pour chaque avion et on obtient ainsi deux forces de glissements coordonnées.

Figure 3.48: Force répulsive et force glissante, forces de glissements coordonnées.

Il s'agit ensuite, pour limiter les changements brutaux de direction, de gérer l'intensité des différentes forces entre elles. En effet, les avions étant limités par leurs taux de virage, de montée et de descente, ils ne peuvent pas effectuer de manoeuvre trop rapide. Les différentes forces s'exerçant sur les avions s'additionnent donc avec des coefficients variables suivant l'imminence du danger.

Pour gérer les conflits à plus de deux avions, Karim Zeghal propose d'additionner les forces relatives à chaque avion. ``Intuitivement, excepté quelques cas exotiques, cela devrait permettre d'obtenir des directions de forces cohérentes entre elles et par rapport aux obstacles''. Les fondements de cette hypothèse ne reposent que sur l'étude de cas pratique.

La coordination d'actions grâce aux forces de glissement n'a pas pour objectif la recherche d'optimalité, mais vise avant tout une bonne efficacité ainsi qu'une bonne robustesse des solutions.

L'étude des possibilités d'utilisation d'une théorie de la coordination d'actions pour les besoins de la navigation aérienne a commencé au CENA en 1994. Trois systèmes sont envisagés :

Dans la mesure où le processus individuel ne nécessite que des informations locales à l'appareil, il peut fonctionner de façon autonome à partir d'une perception de son environnement. Karim Zeghal propose donc un système d'avion autonome ``hybride''¹⁷ . L'intérêt premier de ce système est sa robustesse. La panne d'un avion ne remet pas en cause la sécurité du système. Il apparaît une forme de redondance dans le système qui renforce sa robustesse. Ce système devrait gérer des conflits entre 4 et 10 minutes à l'avenir, ce qui suppose qu'un système supérieur continue à gérer la densité locale de trafic afin d'éviter une saturation.
Karim Zeghal propose également un système d'aide au contrôleur. Il suffit pour cela d'utiliser le processus individuel sous forme de processus centralisé et de simuler les trajectoires futures. Le résultat d'une simulation est alors un ensemble de trajectoires assurant l'évitement sur l'intervalle de temps considéré pour l'ensemble des appareils. Ceci pourrait selon lui avoir un grand intérêt pour planifier les trajectoires et faire des propositions au contrôleur.

Les résolutions proposées par ces techniques étant des commandes continues, il semble peu probables que celle-ci puissent être mises en pratique dans un cadre où le pilote et les contrôleurs sont maintenus dans le système.
Enfin on peut imaginer un système double ``intermédiaire''. Dans ce cas, certains avions sont autonomes et d'autres pas. Le contrôleur a alors une disponibilité supplémentaire et la capacité de son secteur augmente.

La robustesse des solutions est un des atouts des travaux de Karim Zeghal. Il reste néanmoins de nombreux problèmes à résoudre. Dans la mesure où l'on souhaite continuer à confier à l'homme son rôle de pilote dans l'avion, il est indispensable de pouvoir lui transmettre des manoeuvres exécutables et donc simples. Par exemple, on peut demander à un pilote de changer de cap pendant un certain temps ou de prolonger une montée ou de modifier une heure de début de descente. On ne peut pas lui demander de modifier en permanence son cap sa vitesse et son taux de montée ou descente. Il serait donc nécessaire de revoir la modélisation des trajectoires pour les simplifier et les rendre accessibles au pilote. De plus, si l'on doit pouvoir prouver que pour deux avions ces techniques peuvent résoudre tous les conflits, la généralisation à n avions (qui consiste à additionner les forces générées par chaque avion) n'a été vérifiée que sur des exemples. Enfin, aucune recherche d'optimalité globale n'est envisagée.

Évaluation

Jean-François Bosc a implanté la méthode précédente en y apportant quelques amélioration. Il a d'autre part imposé un certain nombre de contraintes :

tous les avions ont le même comportement
on utilise seulement des routes directes
on ne modifie pas la vitesse des avions, car on suppose que les marges de maoeuvre sur la vitesse sont trop faibles
on limite le taux de virage a 3 degrés par seconde

Les résultats obtenus sont intéressants à plus d'un titre (voir figure 3.51).

Figure 3.49: Pourcentages de conflits non résolus

Pour des valeurs élevées du volume de trafic et de la séparation horizontale (trafic multiplié par 2,5 et 10 NM de séparation), la résolution finit par générer plus de conflits qu'il n'y en avait initialement. Ceci est dû à la fois à l'accroissement des temps de vol qui devient très important et aux ''oscillations'' des avions soumis aux force issues d'intrus multiples. Une des limitations des méthodes réactives est qu'on est incapable de tenir compte du fait qu'un intrus en rapprochement pourra passer à distance suffisante sans modification de trajectoire. Une manoeuvre est effectuée, ce qui perturbe inutilement la trajectoire et les autres évitements en cours. On a également remarqué qu'en général les variantes de la méthode de résolution qui étaient moins performantes sur un trafic modéré se dégradaient moins nettement lorsque la complexité augmente.

Il est donc probable que la saturation observée est une saturation de la méthode de résolution plutôt qu'une saturation de l'espace aérien. Au niveau de complexité d'ARC2000 (trafic multiplié par 2.5, et des séparations horizontales allant de 5 à 10 NM selon la géométrie du conflit), la méthode Zeghal implantée sous cette forme fournit des résultats (en termes de pourcentage de résolution et de délais) nettement moins bons (25% de conflits non résolus et 6.7% de délai moyen avec une séparation (constante) de 6 NM).

3.9.2 Résolution par réseaux de neurones

Principe de résolution

La technique développée ici consiste à utiliser un réseau de neurones pour piloter chaque avion ¹⁸ . A chaque instant, le réseau de neurones donne une commande cap à l'avion en fonction des données recueillies. On peut voir sur la figure 3.52 quelle est la structure du réseau, ainsi que ses entrées :

Le cap a pour rejoindre la destination, et sa valeur absolue |a| (in degrés).
La distance l à l'autre avion et son gradient

dl

dt
.
Le cap g de l'autre avion
L'angle b de convergence des trajectoires
Une classique entrée de biais dont la valeur est 1.

Figure 3.50: Les entrées du réseau de neurones et sa structure

Le réseau quant à lui est simplement un classique réseau à 3 couches. La fonction d'activation est la classique fonction logistique act(s)=

1+e ^-s

Le problème est qu'il est impossible d'utiliser des techniques d'apprentissage supervisé pour réaliser l'apprentissage du réseau. En effet, il est long et coûteux de construire une résolution optimale de conflits à deux avions, et impossible de le faire pour un nombre d'avions supérieur à deux. Pour construire le réseau de neurones, nous utilisons donc un algorithme génétique (cette technique a déjà été employé, en particulier pour traiter le problème du parcage d'une voiture [SRD93]).

Chaque élément de population de l'algorithme génétique est un réseau de neurones, représenté par la matrice des poids de ses connexions. On utilise un croisement barycentrique et la mutation ajoute un bruit gaussien à un certain nombre de poids du réseau, pris au hasard.

La fitness de chaque réseau est calculée de la façon suivante : on fait voler les deux avions sur un ensemble de configurations considérées comme représentatives. On dit alors que la fitness vaut :

e ^-V

D est la moyenne des délais induits par les déviations de l'avion et V est le nombre moyen de conflits résiduels ¹⁹ .

La base d'apprentissage

On a utilisé 12 configurations différentes. Dans chacune de ces configurations, les avions sont distants de 20 miles à t=0.

dans 4 configurations, les avions ont la même vitesse et convergent avec des angles différents (20, 60, 120, 150 degrés, voir figure 3.53).

Figure 3.51: 4 configurations à vitesse égale et 4 configurations à vitesse différentes
dans 4 configurations, les avions ont des vitesses différentes et leurs caps sont calculés de façon à générer des conflits. (les vitesses sont de 500, 300, 350, 400, et 450 noeuds, voir figure 3.53).
dans 2 configurations, les avions sont face à face, avec la même vitesse (voir figure 3.54).

Figure 3.52: 2 configurations en face à face et 2 configurations en rattrapage
dans 2 configurations, les avions sont en rattrapage (voir figure 3.54).

En raison des symétries, ces 12 configurations sont représentatives de tous les cas possibles. Nous appelons ``configuration positive'' une configuration dans laquelle l'angle entre l'avion le plus lent et l'avion le plus rapide est positif. Quand on rencontre une configuration négative, on utilise la configuration positive symétrique, en donnant des valeurs négatives aux entrées du réseau.

Résultats numériques

Pour valider les résultats, nous avons testé notre réseau sur des configurations non apprises, afin de vérifier sa capacité à généraliser. Les solutions optimales ont été calculées avec LANCELOT [CGT92] et comparées avec les résolutions fournies par le réseau de neurone. Sur chacune des figures, la résolution du réseau de neurones est à gauche, et la solution optimale trouvée par Lancelot à droite.

Figure 3.53: Face à face et rattrapage.

La figure montre un exemple de conflit à 90 degrés, les deux avions ayant la même vitesse. Les deux solutions sont identiques.
La figure donne un exemple de conflit à 15 degrés (les avions ont la même vitesse). Il s'agit d'un conflit très difficile à résoudre. Les solutions sont différentes, mais les coûts sont proches et la solution donnée par le réseau de neurones est robuste.
La figure 3.56 donne un exemple de résolution de face à face. Les solutions sont identiques.
La figure 3.56 présente un exemple de résolution de rattrapage. Les solutions sont identiques.

Conclusion

La résolution réactive de conflits à deux avions par réseaux de neurones donne d'excellents résultats. Mais le problème de cette méthode est l'extension à un nombre plus élevé d'avions. Nous sommes parvenus à la faire fonctionner avec trois avions, mais le nombre d'entrées du réseau augmente et le nombre de configurations d'apprentissage augmente également. L'extension à des cas de quatre ou cinq avions paraît difficile, du moins dans ce cadre.

3.10 Conclusion

Nous nous sommes efforcés de présenter dans ces quelques pages un panorama assez complet des techniques qui peuvent s'appliquer pour résoudre des conflits aériens. Le travail qui reste à effectuer est encore trés important :

Il faut examiner à nouveau les techniques classiques de recherche de type A. Ces algorithmes devraient se révéler extrèmement utiles lorsque le nombre d'avions n'est pas trop important.
Il faut reprendre les expérimentations et réaliser une validation sur plusieurs journées de trafic.
Il faut que nous disposions d'un algorithme susceptible d'affecter des créneaux d'arrivée aux avions dans l'espace que nous contrôlons, de façon à éliminer les conflits aux frontières.
Enfin, il nous faudrait connecter l'ensemble des filtres dont nous disposons (affectation de créneaux, résolution à 20 minutes et évitement court terme), de façon à faire des estimations de sensibilité de chacun de ces filtres à ceux qui le suivent ou le précèdent dans la chaîne de contrôle.

Nous poursuivons activement ces quatre directions, dans le cadre de DEA ou de thèses.

1: Le niveau de vol ou altitude-pression est l'altitude de l'avion exprimée en centaines de pieds. Par exemple le FL290 (FL pour Flight Level) correspond à une altitude de 29000 pieds soit environ 9000 m.
2: 1 mille nautique vaut 1852 m (1 minute d'angle sur un méridien).
3: 1 pied vaut 30,48 cm.
4: Un créneau de décollage est une fenêtre temporelle pendant laquelle l'avion est autorisé à décoller.
5: Central Flow Management Unit
6: Flow Management Position
7: La charge de travail prend en compte des tâches de surveillance, communication, détection et résolution des conflits.
8: Traffic alert and Collision Avoidance System : système embarqué à bord de certains avions que les Etats-Unis ont rendu obligatoire pour tous les avions de plus de 30 passagers.
9: Flight Management System
10: Global Positionning System
11: Fort peu modestement, nous suggérons au lecteur intéressé mais pressé de se reporter à [AS92] pages 25--39, 358--361 et 463--484 pour un résumé des divers arguments.
12: Il s'agit en fait du modèle CAUTRA
13: Au sens de la théorie de la complexité bien entendu...
14: L'algorithme d'optimisation local utilisé est (LANCELOT)[CGT92]. Pour pouvoir l'appliquer, les trajectoires d'avions ont été discrétisées en 20 points. Les contraintes de séparation des avions sont appliquées en chaque point de discrétisation. Dans les exemples présentés, les avions sont toujours contraints en vitesse. La norme de séparation est de 8 nautiques et les avions parcourent en moyenne 120 nautiques à une vitesse de 400 noeuds.
15: On pose également comme hypothèse que l'avion mobile ne ``tournera'' pas autour de l'autre avion, ce qui effectivement ne se produit pas souvent dans la réalité.
16: Dans la pratique, on utilise un réseau de stations de travail reliées par Ethernet et PVM [GBD⁺94] pour passer des messages entre les différentes applications
17: L'équivalent du TCAS américain (Traffic alert and Collision Avoidance System) mais à plus longue échéance
18: On pourra se reporter à [DAN96a] pour plus de précisions.
19: On retrouve ici la classique méthode consistant à pénaliser la fitness d'un élément violant les contraintes, sans toutefois l'annuler

Routes	ind		dir		écart (%)
Séparation verticale	STD	RVSM	STD	RVSM	STD	RVSM
Nb de vols dans la fenêtre	225	221	210	207	-6.7	-6
Nb de clusters	49	42	33	21	-33	-50
Nb de conflits	69	56	40	30	-42	-46
stable-stable	22	9	11	4	-50	-56
stable-évolutif	35	35	20	14	-43	-60
évolutif-évolutif	12	12	9	12	-25	0
Moy du nb de conflits par cluster	1.41	1.33	1.21	1.43	-14	+7.5
Ecart-type du nb de conflits par cluster	0.70	0.64	0.54	0.73	-23	+14
Max du nb de conflits par cluster	3	3	3	3	--	--
Moy du nb d'avions par cluster	2.35	2.31	2.18	2.24	-7	-3
Ecart-type du nb d'avions par cluster	0.62	0.60	0.46	0.43	-26	-28
Max du nb d'avions par cluster	4	4	4	3	--	-25
Moy écart-type nb conflits par avion	0.12	0.11	0.06	0.11	-50	--
Max écart-type nb conflits par avion	0.87	0.87	0.50	0.82	-43	-6

	Conflits				Clusters
	total	stab-stab	stab-évol	évol-évol
c	1.95	2.24	1.81	1.91	1.61
h	0.99	0.68	1.30	0.87	0.68
v	0.75	0.92	0.71	0.69	0.52
i	0.90	0.91	1.08	0.67	0.80
r²	0.98	0.94	0.96	0.95	0.95

incertitude	0%	1%	2%	3%	4%	5%
1 mn	4.00	4.24	4.30	4.55	4.65	4.70
2 mn	4.03	4.35	4.52	5.00	5.30	5.77
3 mn	4.01	4.44	4.89	5.16	5.61	5.97
4 mn	4.02	4.50	5.02	5.63	6.10	6.68
5 mn	4.03	4.57	4.89	6.01	6.61	7.32

Chapter 3 Optimisation de la résolution de conflits

Introduction

3.1 Etude du trafic

3.1.1 Simulation du trafic

3.1.2 Résultats

Volume de trafic

Conflits et clusters

Routes indirectes :

Routes directes

3.1.3 Conclusion

3.2 Approche mathématique

3.2.1 Conflit entre des avions non contraints en vitesse

Résolution par une méthode de commande optimale

Faisabilité de la résolution en vitesse

3.2.2 Conflit entre deux avions contraints en vitesse

Résolution par une méthode de commande optimale

Approche numérique

3.2.3 Complexité théorique

3.2.4 Conclusion

3.3 Approximation par point tournant et par offset

3.3.1 Point tournant

3.3.2 Approximation par offset

3.3.3 Avions en rattrapage

3.4 Modélisation de l'incertitude

3.4.1 Nécessité de modéliser l'incertitude

3.4.2 Évaluation de la probabilité de conflit.

3.4.3 Espérance de coût de résolution de conflit.

3.5 Modélisation pour la résolution de conflits complexes

3.5.1 Modèle de cluster

3.5.2 Déroulement en temps réel

3.6 Résolution par algorithmes génétiques

3.6.1 Codage

3.6.2 Génération de la population initiale

3.6.3 Fitness

Calcul des éléments de la diagonale

Évaluation des termes non diagonaux

3.6.4 Opérateurs de croisement et de mutation adaptés

3.6.5 Sharing simplifié

3.6.6 Méthode locale en fin de convergence

3.6.7 Applications numériques

Justification du modèle

Un problème combinatoire

Plusieurs solutions quasi-optimales

Efficacité des opérateurs adaptés

Un conflit de rattrapage.

Une résolution globale des clusters

3.6.8 Architecture générale du simulateur de trafic

3.6.9 Résultats sur une journée de trafic réelle

3.6.10 Conclusion

3.7 Programmation linéaire et AG

3.7.1 Introduction

3.7.2 Codage des données du problème

3.7.3 Croisement et mutation

3.7.4 Évaluation de la fitness

3.7.5 Résultats

Conflit à cinq avions

Conflit à six avions

3.7.6 Conclusion

3.8 Techniques de parcours de graphe

3.8.1 Algorithme de type A*

3.8.2 Méthode de plus forte pente

3.8.3 Conclusion

3.9 Résolution réactive et autonome

3.9.1 Méthodes réactives à modèle physique

Présentation

Évaluation

3.9.2 Résolution par réseaux de neurones

Principe de résolution

La base d'apprentissage

Résultats numériques

Conclusion

3.10 Conclusion

3.8.1 Algorithme de type A^*