Abstract

The thesis deals with the design and mathematical analysis of reliable and accurate Monte Carlo methods in order to estimate the (very small) probability that a Markov process reaches a critical region of the state space before a deterministic final time. The underlying idea behind the multilevel splitting methods studied here is to design an embedded sequence of intermediate more and more critical regions, in such a way that reaching an intermediate region, given that the previous intermediate region has already been reached, is not so rare. In practice, trajectories are propagated, selected and replicated as soon as the next intermediate region is reached, and it is easy to accurately estimate the transition probability between two successive intermediate regions. The bias due to time discretization of the Markov process trajectories is corrected using perturbed intermediate regions as proposed by Gobet and Menozzi. An adaptive version would consist in the automatic design of the intermediate regions, using empirical quantiles. However, it is often difficult if not impossible to remember where (in which state) and when (at which time instant) did each successful trajectory reach the empirically defined intermediate region. The contribution of the thesis consists in using a first population of pilot trajectories to define the next threshold, in using a second population of trajectories to estimate the probability of exceeding this empirically defined threshold, and in iterating these two steps (definition of the next threshold, and evaluation of the transition probability) until the critical region is reached. The convergence of this adaptive two-step algorithm is studied in the asymptotic framework of a large number of trajectories. Ideally, the intermediate regions should be defined in terms of the spatial and temporal variables jointly (for example, as the set of states and times for which a scalar function of the state exceeds a time-dependent threshold). The alternate point of view proposed in the thesis is to keep intermediate regions as simple as possible, defined in terms of the spatial variable only, and to make sure that trajectories that manage to exceed a threshold at an early time instant are more replicated than trajectories that exceed the same threshold at a later time instant. The resulting algorithm combines importance sampling and multilevel splitting. Its preformance is evaluated in the asymptotic framework of a large number of trajectories, and in particular a central limit theorem is obtained for the relative approximation error.; La thèse porte sur la conception et l'analyse mathématique de méthodes de Monte Carlo fiables et précises pour l'estimation de la (très petite) probabilité qu'un processus de Markov atteigne une région critique de l'espace d'état avant un instant final déterministe. L'idée sous-jacente aux méthodes de branchement multi-niveaux étudiées ici est de mettre en place une suite emboitée de régions intermédiaires de plus en plus critiques, de telle sorte qu'atteindre une région intermédiaire donnée sachant que la région intermédiaire précédente a déjà été atteinte, n'est pas si rare. En pratique, les trajectoires sont propagées, sélectionnées et répliquées dès que la région intermédiaire suivante est atteinte, et il est facile d'estimer avec précision la probabilité de transition entre deux régions intermédiaires successives. Le biais dû à la discrétisation temporelle des trajectoires du processus de Markov est corrigé en utilisant des régions intermédiaires perturbées, comme proposé par Gobet et Menozzi. Une version adaptative consiste à définir automatiquement les régions intermédiaires, à l’aide de quantiles empiriques. Néanmoins, une fois que le seuil a été fixé, il est souvent difficile voire impossible de se rappeler où (dans quel état) et quand (à quel instant) les trajectoires ont dépassé ce seuil pour la première fois, le cas échéant. La contribution de la thèse consiste à utiliser une première population de trajectoires pilotes pour définir le prochain seuil, à utiliser une deuxième population de trajectoires pour estimer la probabilité de dépassement du seuil ainsi fixé, et à itérer ces deux étapes (définition du prochain seuil, et évaluation de la probabilité de transition) jusqu'à ce que la région critique soit finalement atteinte. La convergence de cet algorithme adaptatif à deux étapes est analysée dans le cadre asymptotique d'un grand nombre de trajectoires. Idéalement, les régions intermédiaires doivent êtres définies en terme des variables spatiale et temporelle conjointement (par exemple, comme l'ensemble des états et des temps pour lesquels une fonction scalaire de l’état dépasse un niveau intermédiaire dépendant du temps). Le point de vue alternatif proposé dans la thèse est de conserver des régions intermédiaires simples, définies en terme de la variable spatiale seulement, et de faire en sorte que les trajectoires qui dépassent un seuil précocement sont davantage répliquées que les trajectoires qui dépassent ce même seuil plus tardivement. L'algorithme résultant combine les points de vue de l'échantillonnage pondéré et du branchement multi-niveaux. Sa performance est évaluée dans le cadre asymptotique d'un grand nombre de trajectoires, et en particulier un théorème central limite est obtenu pour l'erreur d'approximation relative.

Abstract

Maîtres de thèse : Eric RIGAUD et Denis BESNARD; This thesis demonstrates the need to develop systemic safety assessment methods to account for the effect of performance variability on air traffic management safety. Like most modern socio-technical systems, air traffic management is so complex that it is impossible for it to be completely described. As consequence, performance cannot be completely specified because it must vary to meet performance demands. Performance variability is an inevitable asset to ensure the functioning of an organisation and at the same time can be harmful for system safety when it combines in an unexpected manner. This argument clearly indicates the need for safety assessment methods that can deal with performance variability. The Functional Resonance Analysis Method (FRAM) has the ability to model performance variability. However parts of the FRAM can be improved to expand its capabilities to evaluate performance variability. This thesis addresses this weakness and develops a methodology for the evaluation of performance variability. The methodology has been applied on a safety assessment case study for the German air traffic management domain. The results have been compared with the official results of a traditional safety assessment. The comparison shows the added valued of the proposed methodology. In particular it illustrates the possibility to identify emergent risks and human contribution to system safety.; Cette thèse montre la nécessité de développer des méthodes systémiques d'estimation de la sécurité permettant de tenir compte de l'effet de la variabilité de la performance sur la sécurité de la gestion du trafic aérien. Comme la plupart des systèmes socio-techniques modernes, la gestion du trafic aérien est tellement complexe que il lui est impossible d'être complètement décrite. Comme conséquence directe, sa performance ne peut être complètement explicitée, car elle doit varier afin de correspondre aux conditions réelles. La variabilité de la performance est un inévitable atout pour assurer le fonctionnement d'une organisation. Mais en même temps elle peut représenter une atteinte à la sécurité du système lorsqu'elle se déroule de manière indésirable ou inattendue. Cet argument indique la nécessité de méthodes d'estimation de la sécurité qui puissent traiter la variabilité de la performance. La Functional Resonance Analysis Method (FRAM) a la capacité de modéliser la variabilité de la performance. Cependant, certains points de la FRAM pourraient être améliorés dans le but de développer ses capacités a évaluer la variabilité de la performance. Cette thèse aborde ce point faible et développe une méthodologie pour l'évaluation de la variabilité de la performance. Cette méthodologie a été appliquée dans une étude de cas dans le domaine de la Gestion du Trafic Aérien Allemand. Ses résultats ont été comparés aux résultats officiels obtenus en utilisant l'estimation de la sécurité traditionnelle. La comparaison montre la valeur ajoutée de la méthodologie proposée. En particulier elle illustre la possibilité d'identifier des risques émergents et la contribution humaine a la sécurité d'un système.

Abstract

To sustain the continuously increasing air traffic demand, the future air traffic management system will rely on a so-called Trajectory Based Operations (TBO) concept that will increase air traffic capacity by reducing the controller's workload. This will be achieved by transferring tactical conflict detection and resolution tasks to the strategic planning phase. In this future air traffic management paradigm context, this thesis presents a methodology to address such strategic trajectory planning at nation-wide and continent scale. The proposed methodology aims at minimizing the global interaction between aircraft trajectories by allocating alternative departure times, alternative horizontal flight paths, and alternative flight levels to the trajectories involved in the interaction. To improve robustness of the strategic trajectory planning, uncertainty of aircraft position and aircraft arrival time to any given position on the trajectory are considered. This thesis proposes a mathematical formulation of this strategic trajectory planning problem leading to a discrete-optimization and a mixed-integer optimization problem whose objective function relies on the new concept of interaction between trajectories. A computationally efficient algorithm to compute interaction between trajectories for large-scale applications is introduced and implemented. Resolution methods based on metaheuristic and hybrid-metaheuristic algorithms have been developed to solve the above large-scale optimization problems. Finally, the overall methodology is implemented and tested with air traffic data taking into account uncertainty over the French and the European airspaces, involving more than 30,000 trajectories. Conflict-free and robust 4D trajectory planning are produced within computational time acceptable for the operation context, which shows the viability of the approach.; Afin de pouvoir satisfaire la demande sans cesse croissante du trafic aérien, le futur système de gestion du trafic aérien utilisera le concept d'opérations basées sur les trajectoires (Trajectory Based Operations), qui augmentera la capacité du trafic aérien, en réduisant la charge de travail du contrôleur. Pour ce faire, les tâches de détection et de résolution de conflits seront transférées depuis la phase tactique vers la phase stratégique de la planification. Dans le cadre de ce nouveau paradigme pour le système de gestion du trafic aérien, nous introduisons dans cette thèse une méthodologie qui permet d'aborder ce problème de planification stratégique de trajectoires d'avion à l'échelle d'un pays ou d'un continent. Le but de la méthodologie proposée est de minimiser l'interaction globale entre les trajectoires d'avion, en affectant de nouveaux créneaux de décollage, de nouvelles routes et de nouveaux niveaux de vols aux trajectoires impliquées dans l'interaction. De plus, afin d'améliorer la robustesse du plan stratégique de vols obtenu, nous prenons en compte l'incertitude de la position de l'avion et de son heure d'arrivée à un point donné de la trajectoire de l'avion. Nous proposons une formulation mathématique de ce problème de planification stratégique conduisant à un problème d'optimisation discrète et un problème d'optimisation en variables mixtes, dont la fonction objectif est basée sur le nouveau concept d'interaction. Un algorithme efficace en termes de temps de calcul pour évaluer l'interaction entre des trajectoires d'avion pour des applications de grande taille est introduit et mis en œuvre. Des méthodes de résolution basées sur des algorithmes de type métaheuristique et métaheuristique hybride ont été développées pour résoudre ces problèmes d'optimisation de grande taille. Enfin, la méthodologie globale de planification stratégique de trajectoires d'avion est mise en œuvre et testée sur des données de trafic, prenant en compte des incertitudes, pour l'espace aérien français et l'espace aérien européen, impliquant plus de 30000 vols. Des plans de vols 4D sans conflits et robustes ont pu être produits avec des temps de calcul acceptables dans un contexte opérationnel, ce qui démontre la viabilité de l'approche proposée.