Airbus Defence & Space entre dans la galaxie de l’optimisation temps réel
Airbus a adopté un moteur de calcul pour résoudre des problèmes combinatoires complexes en temps réel. Initialement développé pour l’orchestration de réseaux militaires critiques, cet outil trouve désormais de multiples applications.
Dans la défense et les télécommunications, la prise de décision doit être quasi instantanée. Or identifier une meilleure option parmi des milliards de possibilités sous contrainte de temps extrême n’est pas simple. Ces défis d’optimisation combinatoire sont en effet un véritable « mur » computationnel. Autrement dit, ces problèmes deviennent extrêmement difficiles à résoudre de façon optimale dans un délai raisonnable lorsque la taille du problème augmente. Faciles à vérifier, une fois résolus, ils résistent aux tentatives de résolution qu’elles soient à la fois rapides et garanties.
Trouver la bonne combinaison parmi des milliards
Pour mémoire, l’optimisation combinatoire consiste à trouver la meilleure solution parmi un nombre fini, mais souvent astronomique, de configurations possibles (activer ou non un lien réseau, choisir telle route plutôt qu’une autre, allouer telle ressource à tel flux).
Or le nombre de combinaisons est exponentiel dans de nombreux cas, et les possibilités à évaluer peuvent se compter en milliards de milliards. Trouver une solution acceptable peut-être simple, mais identifier la meilleure solution, dans un temps contraint, est un travail titanesque.
Airbus Defence & Space a été confronté à ce défi. Le cas d’usage initial concernait la gestion d’un réseau de données aux ressources limitées.
Ce problème, un problème classique d’allocation de flux réseau (multi-commodity flow), mettait en compétition plusieurs flux (vidéo, voix, data) pour utiliser la bande passante. Le défi était de trouver « la bonne combinaison parmi des milliers », résume Jorge Eleazar Lopez Coronado, expert optimisation R&D chez l’industriel.
Les approches traditionnelles imposaient un compromis qui était difficilement acceptable pour des applications critiques. Elles contraignaient à accepter « une solution heuristiquequi ne va peut-être pas se comporter comme il faut, mais on l’acceptait parce que [faire autrement] était trop complexe. »
Solution heuristique et mur computationnel
Une solution heuristique repose sur des règles empiriques et des approximations, des sortes de raccourcis « intelligents ». Certaines prennent systématiquement la décision qui semble la meilleure sur le moment (algorithmes gloutons), d’autres testent des configurations en s’inspirant de processus naturels comme l’évolution des espèces ou le refroidissement des métaux.
« On acceptait une solution heuristique parce que faire autrement était trop complexe. »
Jorge Eleazar Lopez CoronadoExpert optimisation R&D chez Airbus Defence & Space
Dans le cas du réseau, plutôt que de tester des milliards de façons d’acheminer des flux, l’algorithme privilégie d’emblée les routes les moins encombrées et les priorités évidentes, quitte à passer à côté de la configuration parfaite
Ces « anciennes » méthodes sont un bon compromis. Elles donnent un résultat acceptable en quelques millisecondes. Mais cette rapidité a un prix. Dans un contexte militaire critique, « acceptable » peut signifier 95 % d’efficacité au lieu de 100 %. Cette différence de quelques pour cent peut s’avérer fatale.
En 2020, Airbus Defence & Space a donc décidé de prendre le problème à bras le corps. Le groupe évalue des solutions du marché. Après avoir testé plusieurs outils, propriétaires et open source, son choix se pose sur un « solveur » bien particulier, celui de l’éditeur Gurobi.
Les tests sur de « grosses instances » – qui simulent un réseau de cinquante sites gérant jusqu’à 7 000 flux – sont prometteurs. Le « solveur » identifiait la solution en « quelques millisecondes », bien en dessous de la marge de tolérance. L’outil va même plus loin. Il apporte la preuve mathématique formelle que le résultat proposé est optimal ; un processus distinct qui ne prend que trois minutes.
Un effet catalyseur interne
Le projet s’inscrivait dans un programme de « recherche technologique » pour développer un nouveau portefeuille de produits en capitalisant sur cette capacité d’optimisation. Par exemple, une solution d’orchestration intelligente de réseau.
Sur un théâtre d’opérations militaires, une communication du commandement ne peut être compromise par un flux vidéo de drone qui saturerait le réseau. Il ne s’agit donc pas de simple gestion de trafic, mais d’assurer la primauté des communications critiques. Une seule décision erronée, un seul message bloqué, pouvant entraîner des conséquences irréversibles.
« Plus on résout des problèmes avec le solveur, plus les gens veulent faire de choses avec. »
Jorge Eleazar Lopez CoronadoExpert optimisation R&D chez Airbus Defence & Space
Le projet a mis en lumière l’intérêt de l’optimisation mathématique pour l’allocation de ressources limitées sous contraintes et a mis à jour d’autres opportunités chez Airbus Defence & Space.
Le « solveur » est désormais exploré ou utilisé pour la planification de production, l’assignation de fréquences satellites, ou la préparation de missions critiques (militaires, sécurité publique, lutte contre les incendies).
Un potentiel existe aussi pour la gestion du Réseau Radio du Futur (RRF) en France, afin de garantir la résilience des communications des forces de sécurité en cas de crise majeure.
« Plus on résout des problèmes [avec le solveur], plus les gens se disent “Ah bah je vais faire autre chose avec, par exemple, la planification des trajectoires hélicos” », se félicite Jorge Eleazar Lopez Coronado.
L’art de l’optimisation : au-delà de l’outil, l’expertise
Reste que l’exploitation d’un « solveur » n’est pas triviale. Elle exige une expertise humaine pour obtenir la performance maximale et construire la couche d’intelligence et d’interaction avec l’utilisateur final.
Pour la performance brute, les experts d’Airbus Defence & Space travaillent en C/C++ pour « gratter chaque milliseconde », approche indispensable aux applications en temps réel. Ils ajustent finement le « solveur » par l’intermédiaire de « plus d’une centaine de paramètres ».
Ils fournissent également au moteur des « solutions initiales » de bonne qualité pour accélérer la convergence.
La piste de la programmation génétique
Simultanément, les experts d’Airbus Defence & Space explorent des pistes de recherche, comme la programmation génétique assistée par LLM, inspirée de l’approche « FunSearch » développée par DeepMind, une fusion entre programmation génétique et intelligence artificielle générative.
La programmation génétique s’inspire des mécanismes de l’évolution naturelle pour générer automatiquement des algorithmes et créer une population de « programmes candidats ». Les meilleurs survivent et se reproduisent. Génération après génération, le système fait émerger des solutions de plus en plus efficaces, parfois contre-intuitives.
Dans l’approche « FunSearch », des LLM sont utilisés pour générer du code source de fonctions mathématiques ou de règles de décision pratiques qui sont ensuite évaluées. Les meilleures sont réinjectées dans le processus pour guider le LLM vers des solutions encore plus performantes.
Airbus Defence & Space change d’univers
Cette boucle a permis de découvrir de nouvelles solutions et de découvrir des solutions à des problèmes mathématiques que les chercheurs tentaient de résoudre depuis des années.
Grâce à toutes ces optimisations, Airbus Defence & Space a en tout cas changé d’univers.
Il ne cherche plus des solutions « assez bonnes ». Il traque activement la configuration optimale, même dans des scénarios complexes soumis à de fortes contraintes de temps.
