IA - Intelligence Artificielle

La résolution de conflits de trajectoires d’avions est un sujet de recherche depuis de nombreuses années pour plusieurs membres de l’axe. Différentes approches, métaheuristiques ou par programmation par contraintes, ont été testées. Les métaheuristiques (algorithmes évolutionnaires, évolution différentielle, optimisation par colonies de fourmis, essaims particulaires) ont permis une véritable percée pour traiter ce problème combinatoire de manière efficace et avec une modélisation réaliste des incertitudes et des manœuvres, notamment en introduisant des opérateurs (ex. croisement et mutation) adaptés à la nature partiellement séparable du problème. En programmation par contraintes, la formalisation du problème sous forme de CSP, avec un pré-calcul des manœuvres compatibles, a permis de proposer un benchmark de problèmes de résolution de conflits, avec des solutions optimales prouvées pour de nombreux scénarios. Les travaux en cours s’intéressent à la modélisation des incertitudes et aux aspects dynamiques de la résolution. En effet, il faut réévaluer régulièrement le problème en décalant l’horizon de prévision dans le temps, réduisant ainsi les incertitudes. On explore donc l’idée d’exploiter une métaheuristique en temps réel pour exploiter au mieux les aspects dynamiques du problème et la continuité des solutions.

Les contrôleurs sont des opérateurs humains qui réagissent différemment face à des situations similaires. La problématique générale consiste ici à analyser, à partir de données réelles enregistrées, l’incertitude liée aux actions de détection et de résolution de conflits, pour pouvoir proposer des outils d’assistance à la décision adaptés aux comportements des opérateurs. Une première étape de ce travail consistera à identifier et extraire des données radar les situations de conflits, par de l’apprentissage non supervisé ou semi-supervisé, pour pouvoir ensuite modéliser l’incertitude du contrôleur sur les manœuvres des avions, à partir de ces exemples réels.

Dans le contexte du développement de la circulation de drones dans des espaces aériens, on s’intéresse d’une part à l’adaptation d’algorithmes géométriques d’anti-collision issus de la robotique, pour une application à des avions commerciaux ou des UAV (à ailes fixes notamment) ayant des capacités de manoeuvre limitées et des vitesses de croisière dans des intervalles de faible amplitude. Dans ce contexte, des algorithmes classiques tels ORCA (Optimal Reciprocal Collision Avoidance) sont sujets à des effets indésirables peu abordés dans la littérature, dont notamment la mise en parallèle des trajectoires, repoussant ainsi indéfiniment leur croisement. Nos travaux en cours portent sur l’introduction d’un double horizon d’anticipation pour mieux croiser les trajectoires en amont tout en assurant l’anti-collision, et également sur un meilleur traitement des cas dégradés, lorsque le convexe des vitesses admissibles est vide. En collaboration avec la plateforme “Drones”, une implantation réelle pourrait être réalisée à des fins de démonstration et d’expérimentation.

On se propose de développer et mettre à disposition de la communauté scientifique un petit simulateur générique permettant de brancher facilement différents algorithmes de “detect & avoid” ou de résolution centralisée de conflits. L’objectif est de pouvoir enfin comparer objectivement différentes approches sur un même jeu de scénarios denses.

Prévoir précisément les trajectoires des avions est indispensable à tous les outils d’assistance au contrôleur. Les travaux passés menés dans l’axe ont permis d’apprendre les paramètres du modèle physique de l’avion afin d’améliorer la prévision de l’altitude de l’avion en montée par les systèmes au sol. Les modèles sont appris sur des données massives d’enregistrements ADS-B ou de radar Mode-S. Une future étude pourrait explorer l’inclusion des équations physiques du modèle dans un réseau de neurones.

Le calcul de trajectoires d’avions minimisant l’impact environnemental des traînées de condensation est un autre sujet actuel de l’axe. Plusieurs approches sont à l’étude. La gestion des flux aériens à l’échelle de tout un espace aérien est d’abord modélisé par la résolution dynamique de multiples problèmes de plus courts chemins sur un graphe dans lequel des contraintes de capacités sur des sous-graphes (secteurs aériens) sont considérés. Une seconde approche est en cours d’étude et consiste à optimiser des routes dans leur totalité pour un ensemble d’avions à l’aide de techniques basées sur la génération de colonnes. Cette seconde approche permettra une prise en compte plus naturelle de la dynamique ainsi que l’intégration de contraintes opérationnelles liées à l’altitude. Plusieurs façons d’estimer les zones de contrails persistantes sont envisagées et certaines déjà étudiées: estimation à l’aide de techniques d’extrapolation, de modèles physiques simples basés sur des données météorologiques ou bien de méthodes d’apprentissage sur des images satellites.

La gestion des avions au sol fait également apparaître des conflits entre avions, dans les zones de parking où les voies d’accès sont souvent limitées et les attentes après push-back contraignantes pour les autres mouvements, aux intersections les plus utilisées, ainsi que devant les pistes où les départs doivent être séquencés correctement pour permettre le respect de leurs créneaux de décollage lorsqu’ils sont régulés. Le problème consiste globalement à affecter des chemins et des positions d’attente aux avions pour permettre leur circulation. Ce problème peut être résolu par des métaheuristiques (algorithmes génétiques avec fonction d’adaptation partiellement séparable) ou simplifié par classement préemptif des avions pour être résolu par des méthodes exactes (type A* ou branch & bound), ou encore être résolu par des méthodes hybrides alliant métaheuristiques et optimisations locales.

L’optimisation des séquences d’avions sur les pistes doit être anticipée pour permettre la gestion coordonnée des départs, avec comme objectif de favoriser les attentes au parking, moteurs éteints, plutôt que sur les voies de circulation ou devant les pistes, moteurs allumés, tout en minimisant le retard cumulé et les écarts aux créneaux de décollage des départs régulés. Le problème se formalise comme un problème classique de séquencement de tâches, mais avec des contraintes particulières et de nombreuses symétries qui peuvent être utilisées pour le résoudre plus efficacement avec des méthodes exactes de type branch & bound. Ce problème peut être corrélé avec la résolution de conflits au roulage pour fournir une planification globale des mouvements avec cheminements optimisés (planning and routing function).

Prévoir la charge de travail des contrôleurs est essentiel pour anticiper les surcharges, ce qui permet de les éviter en retardant les avions au sol avant qu’ils ne décollent. Les modèles opérationnels actuels sont basés sur des métriques inadaptées, et les recherches sur le sujet nécessitent usuellement des protocoles expérimentaux lourds (ex. : mesures de paramètres physiologiques). Nous avons proposé dans des travaux passés d’apprendre des modèles de prévision à partir de données massives d’archives d’ouvertures de secteurs, et de mesures d’indicateurs de complexité ATC. Diverses approches ont été testées, dont notamment des réseaux de neurones classifieurs et des arbres de classification boostés, pour distinguer trois niveaux de charge (normale, sous-charge, ou surcharge). L’idée est que ces niveaux de charge sont facilement observables dans nos archives à partir de l’état des secteurs de contrôle (ouvert, regroupé avec un autre, ou séparés en secteurs plus petits). Des travaux futurs pourraient s’intéresser à l’utilisation de réseaux profonds récurrents, et à la robustesse des modèles obtenus face aux incertitudes sur leurs entrées.

Au-delà de la simple prévision de charge sur un secteur donné, il faut pouvoir anticiper comment ouvrir les secteurs de contrôle en minimisant les surcharges et en optimisant les ressources. Ce problème de partitionnement optimal de l’espace aérien est très combinatoire, en particulier si l’on tient compte des dépendances temporelles entre configurations successives de secteurs, dues aux contraintes de transition. Nous l’avons abordé dans le passé avec des méthodes de recherche arborescente à horizon limité, appliquées sur un horizon glissant, et avec une heuristique minorante basée le coût des configurations optimales sans contraintes de transition. Dans une autre approche, nous avons utilisé un algorithme de colonies de fourmis déposant des phéromones sur des chemins dans l’arbre des configurations successives. Il est envisagé par la suite de faire coopérer ces deux algorithmes en parallèle. Des recherches ultérieures pourrait là-aussi s’intéresser à la robustesse des prévisions de séquences de configurations face aux incertitudes de prévision du trafic.

Les signaux utilisés par les systèmes de positionnement par satellite (GNSS) sont sujets à des perturbations qui altèrent le calcul de la position. La principale perturbation est celle qui correspond à un multi-trajet (rebond) du signal dans son environnement (ex: hangar ou sol à l’approche d’un aéroport). Certains travaux de l’axe s’intéressent à détecter et estimer les paramètres de ces signaux parasites à partir de techniques d’apprentissage automatique. Le signal corrélé est vu comme une image et permet la construction d’un dataset utilisé pour entraîner des réseaux de neurones profonds. La construction de fonctions de perte dédiées permet l’estimation fine et robuste des paramètres et donc la correction de la position in fine. La dynamique temporelle du signal parasite a une signature particulière qui n’est pas exploitée dans les modèles actuels. Dans le futur, l’axe s’intéresse donc à profiter de cette structure pour entraîner des réseaux dit récurrents qui permettent d’exploiter cette dimension temporelle. Ces travaux sont le fruit d’une collaboration entre l’équipe OPTIM et TELECOM du laboratoire.

Des activités plus ponctuelles se focalisent aussi sur la construction de modèles statistiques paramétriques pour estimer la probabilité de défaillance d’un système critique. Ces travaux, en collaboration avec l’axe statistiques et graphes, font appel à des techniques d’estimation par maximum de vraisemblance et d’optimisation sur des variétés (groupe des matrices orthogonales ou variété de Stiefel pour être précis). Utilisés aujourd’hui pour les défaillances de moteurs d’hélicoptères (collaboration SAFRAN HSE), ces modèles sont transférables à bien d’autres applications.

Les infrastructures aéroportuaires constituent une limite à la quantité de trafic qu’il est possible d’écouler. Nous avons travaillé sur l’optimisation de l’allocation des portes d’embarquement sur des grands aéroports internationaux, avec des solutions optimales (prouvées) tenant compte de la robustesse, de la congestion, des temps de roulage ou d’autres critères opérationnels.

Les bouleversements écologiques présents et à venir vont transformer en profondeur le fonctionnement des économies des sociétés futures (transports, agro-alimentaire, énergie…). Des approches systémiques et trans-disciplinaires sont nécessaires pour mieux comprendre les trajectoires biophysiques et les alternatives sociotechniques de nos sociétés. Les outils de l’IA (modélisation, simulation, statistique, visualisation, optimisation MDO, aide à la décision) sont utiles pour construire et évaluer des scénarios de transformation soutenable. Une thèse sur cette problématique vient de débuter en collaboration avec Airbus et des économistes.

un enjeu crucial de la discipline afin d’assurer des garanties quant aux décisions proposées par les algorithmes. De nombreuses publications récentes dans le domaine du transport aérien ont montré l’intérêt d’utiliser des techniques à base d’IA dans les systèmes d’aide à la décision. Si les systèmes sont critiques et/ou embarqués, l’enjeu est de fait plus important. L’une des activités de l’axe consiste à analyser la sensibilité de certaines de ces techniques lorsque les données sont sujettes à des incertitudes. Notamment, plusieurs travaux autour de l’estimation de la constante de Lipschitz des réseaux de neurones profonds (marqueurs de l’amplification des incertitudes par le réseau) sont notamment en cours. D’autres travaux s’intéressent aussi à la compréhension de cette sensibilité à travers les propriétés géométriques des réseaux de neurones. Par la construction d’attaques utilisant cette géométrie, ces travaux permettent de comprendre les mécanismes qui engendrent cette forte sensibilité à de petites perturbations. A terme, cette compréhension de la topologie du réseau devrait aider à contraindre la phase d’apprentissage de manière à construire des modèles neuronaux plus robustes. ce travail de recherche met en oeuvre des outils de la théorie de l’information, de la géométrie différentielle et de la théorie de l’apprentissage.

En optimisation continue, des méthodes de Branch and Bound par intervalles peuvent être hybridées avec des métaheuristiques afin de profiter des avantages de chaque approche. Les métaheuristiques permettent d’atteindre rapidement une bonne solution qui peut accélérer l’élagage de l’arbre de recherche d’un algorithme de Branch and Bound par intervalles. Ce dernier peut éliminer rapidement des sous-domaines de l’espace de recherche, permettant aux métaheuristiques de se concentrer sur l’espace restant. Le Branch and Bound par intervalles garantit l’optimalité de la solution trouvée. En optimisation combinatoire, on peut exploiter la complémentarité des principales familles d’algorithmes : La programmation par contraintes qui permet une modélisation rapide et compacte avec un haut niveau d’abstraction grâce à l’expressivité des contraintes, ainsi que d’enrichir le solveur avec de nouvelles contraintes et stratégies de recherche spécifiques à l’application; La programmation linéaire mixte, dont le succès commercial et académique a permis des investissements massifs dans le développement de solveurs parallèles toujours plus performants; Les métaheuristiques grâce auxquelles il est possible d’obtenir efficacement des solutions de bonne qualité même pour des problèmes de grande taille ou non-linéaires. En exécutant ces algorithmes en parallèle sur les mêmes variables de décision, on peut en améliorer l’efficacité en échangeant des bornes de l’objectif, des solutions ou de nouvelles contraintes au fur et à mesure de leur découverte. L’une des limites de cette approche est la nécessité de développer un modèle spécifique pour chaque algorithme utilisé. Une direction de recherche intéressante serait la réalisation d’un compilateur pour un langage de modélisation abstrait qui permette de générer automatiquement des modèles pour les différents types de solveur.

Un travail est en cours sur la collaboration d’un algorithme mémétique et de méthodes d’intervalles pour trouver l’optimum de problèmes multimodaux complexes en échappant à une convergence prématurée vers un minimum local. La parallélisation des métaheuristiques permettra de conserver une efficacité importante pour de tels algorithmes.

Cette activité de recherche s’intéresse au domaine du traitement et de la visualisation de données, et aux classes d’ algorithmes d’intelligence artificielle capables d’expliquer leurs résultats. Concernant la visualisation de données, nous nous spécialisons sur les nouvelles techniques et technologies pour l’amplification de la cognition comme support à la décision. Ces thèmes de recherches, composants des sciences de l’informatique, sont à l’intersection entre l’intelligence artificielle, le traitement et la visualisation de données. Ces travaux de recherche s’inscrivent dans tous les domaines applicatifs critiques où la prise de décision a des conséquences sur l’Homme, avec le domaine aéronautique (pilotage, trafic aérien) mais aussi médical.

Les interfaces graphiques prennent de plus en plus de place dans les applications critiques de l’aéronautique (cockpits sur écran tactile, interfaces de contrôle aérien, etc.). En coopération avec l’équipe LII, certains membres de l’axe IA s’intéressent à la certification de ce type d’outils, via la preuve de propriétés de sécurité, ou la création d’interfaces correctes par construction. Nous nous appuyons sur des approches formelles (calcul des séquents, calcul des processus, bigraphes) pour exprimer la sémantique des langages associés ainsi que les propriétés graphiques. Verrous scientifiques Acceptabilité des solutions proposées par l’IA – L’axe développe des algorithmes intelligents d’aide à la décision pour le contrôleur aérien qui posent en général de nombreux problèmes d’acceptabilité, que l’on peut tenter de résoudre par la modélisation des incertitudes, l’extraction de préférences ou la transparence des algorithmes.

Un des objectifs à terme est d’obtenir des estimations fines de la constante de Lipschitz des réseaux de neurones, en des temps raisonnables dans le cas de grands réseaux. Les techniques en jeu composent à la fois des relaxations de problèmes d’optimisation combinatoire NP-difficiles à des techniques telles que la programmation semi-definie ou d’autres formulations mathématiques exploitant la structure particulière des réseaux.

Une partie des travaux de l’équipe repose sur l’utilisation d’outils d’optimisation (bibliothèques logicielles). Nous souhaitons pouvoir apporter des garanties, notamment de correction, sur les solutions fournies par ces outils. Un travail a débuté pour prouver des propriétés de correction sur la bibliothèque de programmation par contraintes FaCiLe, développée dans l’équipe. Une autre approche envisagée est la production, en parallèle de la solution, des lemmes à prouver (par exemple avec des assistants de preuve) pour garantir la correction de celle-ci.