Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

Dans le monde de l'intelligence artificielle, la prise de décision est souvent traitée comme un jeu de hasard pratiqué sur un plateau dont les règles sont parfaitement connues. Imaginez un robot naviguant dans un labyrinthe ; si les ingénieurs savent exactement à quel point le sol est glissant et comment les roues du robot vont tourner, ils peuvent calculer le chemin parfait pour atteindre la sortie. C'est le modèle standard de nombreux systèmes de prise de décision. Cependant, le monde réel est rarement aussi précis. Les capteurs tombent en panne, les matériaux s'usent et les données sont bruitées, ce qui signifie que les probabilités exactes qu'un robot glisse ou qu'une voiture dévie ne sont jamais vraiment connues, mais seulement estimées dans une plage de possibilités. Lorsque ces incertitudes s'ajoutent au mélange, le problème devient beaucoup plus difficile : comment planifier un chemin sûr quand on ne peut être certain du comportement du terrain ? De plus, dans les domaines critiques pour la sécurité comme la conduite autonome ou la robotique médicale, l'objectif n'est pas seulement d'atteindre une destination rapidement, mais de garantir que le système n'entre jamais dans un état dangereux ou ne suive jamais une séquence spécifique d'événements logiques indéfiniment.

Des chercheurs de l'Institut indien de technologie de Bombay et de l'Université technologique de Nanyang ont abordé cette intersection difficile entre l'incertitude et la sécurité logique stricte. Ils se sont concentrés sur une classe de problèmes où un agent doit prendre des décisions tout en ne voyant que partiellement le monde, et où les règles de mouvement ne sont pas des nombres fixes mais appartiennent à un ensemble de valeurs possibles. L'équipe a prouvé que la résolution de ces problèmes de décision complexes et incertains est mathématiquement identique à la résolution d'un autre type de jeu bien étudié impliquant deux joueurs opposés avec des informations cachées. En établissant cette connexion bidirectionnelle, ils ont pu emprunter des décennies de connaissances existantes sur la théorie des jeux pour déterminer instantanément la difficulté de calcul de la résolution de ces problèmes robotiques incertains. Leur travail révèle précisément la difficulté de garantir la sécurité dans ces scénarios, montrant que pour certains types d'objectifs logiques, le problème est soluble avec des méthodes connues, tandis que pour d'autres, il est si complexe qu'aucun algorithme ne pourrait jamais le résoudre en un temps raisonnable.

Le cœur de leur découverte réside dans le rapprochement de deux mondes mathématiques différents. D'un côté, le processus de décision markovien partiellement observable robuste, un modèle utilisé pour décrire une situation où un agent, comme une voiture autonome, doit choisir des actions sans connaître sa position exacte et sans connaître la probabilité exacte de passer à un nouvel état. Au lieu d'une probabilité unique, le système opère dans un « nuage » de probabilités possibles. De l'autre côté, le jeu stochastique partiellement observable, un modèle où deux joueurs, l'un essayant de réussir et l'autre de l'en empêcher, se relaient pour effectuer des mouvements tout en ne voyant qu'une partie des informations sur le plateau. Pendant des années, les chercheurs savaient que si l'objectif était simplement de maximiser une récompense, ces deux modèles pouvaient être traduits l'un dans l'autre. Cependant, lorsque l'objectif passe à des règles logiques strictes — telles que « ne jamais heurter un piéton » ou « éventuellement atteindre l'hôpital et y rester pour toujours » — la connexion est rompue. La nouvelle étude prouve que même avec ces règles logiques complexes, les deux modèles sont toujours parfaitement équivalents.

Pour démontrer cela, les chercheurs ont construit un mécanisme de traduction précis qui fonctionne dans les deux sens. D'abord, ils ont montré comment prendre un problème de décision robuste avec des probabilités incertaines et le convertir en un jeu à deux joueurs. Dans ce nouveau jeu, l'agent devient un joueur, et l'incertitude du monde devient un second joueur, adverse. Ce second joueur n'agit pas de manière aléatoire ; il choisit activement le pire scénario parmi les options disponibles pour tenter de vaincre l'agent. Les chercheurs ont prouvé que si l'agent peut gagner ce jeu contre un adversaire habile, il peut également réussir dans le monde incertain d'origine. Plus surprenant encore, ils ont réussi la traduction inverse. Ils ont montré que n'importe quel jeu à deux joueurs avec des informations cachées pouvait être converti en un problème de décision robuste. Cette étape inverse était techniquement difficile car, dans le jeu, l'adversaire voit le mouvement de l'agent avant d'agir, alors que dans le problème de décision, l'environnement s'engage dans son comportement immédiatement. L'équipe a résolu cela en insérant une brève pause invisible dans la structure du jeu, donnant ainsi à l'environnement la même information qu'il avait dans le problème d'origine. Cette passerelle bidirectionnelle signifie que tout résultat d'informatique concernant la difficulté de résolution d'un type de problème s'applique automatiquement à l'autre.

Les implications de cette équivalence sont immédiates et profondes pour la compréhension des limites du raisonnement automatisé. En utilisant ce pont, les chercheurs ont été capables de cartographier la complexité de calcul exacte de la résolution de ces problèmes pour divers types d'objectifs logiques. Ils ont trouvé que pour des objectifs simples, tels que atteindre une cible ou éviter une zone de danger, les problèmes sont solubles, bien qu'ils nécessitent une puissance de calcul importante qui croît de manière exponentielle avec la taille du système. Cependant, l'étude a également identifié une limite dure. Pour certains objectifs logiques complexes, spécifiquement ceux impliquant un mélange de conditions de type « toujours » et « éventuellement » dans un environnement incertain à deux côtés, le problème devient indécidable. Cela signifie qu'aucun programme informatique, quelle que soit sa puissance, ne pourra jamais garantir une réponse pour chaque scénario possible. Les chercheurs ont également clarifié la difficulté pour l'incertitude à un seul côté, où seul l'agent est aveugle mais l'environnement voit tout, montrant que ces cas sont généralement plus faciles à résoudre que les scénarios de cécité totale.

Ce travail fournit un paysage complet de ce qui est computationnellement possible lors de la conception de systèmes autonomes sûrs sous incertitude. Il confirme que, bien que nous puissions construire des algorithmes pour gérer de nombreuses tâches critiques pour la sécurité, il existe des frontières fondamentales où la combinaison d'informations cachées, d'incertitude adversaire et de règles logiques complexes rend une solution impossible à trouver. L'étude n'offre pas un nouvel algorithme pour résoudre tous les cas, mais plutôt une carte définitive du terrain, indiquant aux ingénieurs exactement quels problèmes ils peuvent résoudre et lesquels nécessitent une approche totalement différente. En prouvant que ces deux cadres mathématiques sont les mêmes, les chercheurs ont ouvert une vaste bibliothèque d'outils et de théories existants, permettant au domaine d'avancer avec une compréhension claire des défis à venir.