L’équipe Synthèse du LaBRI s’attaque au problème ardu de la synthèse de programme. Il s’agit de développer des algorithmes qui eux-mêmes génèrent d’autres algorithmes, à partir de quelques exemples ou d’une spécification de ce qui est attendu. Concrètement, ces algorithmes très puissants sont utilisés dans une variété de contextes. Par exemple, la plupart des tableurs proposent aujourd’hui des fonctions de remplissage automatique : vous remplissez quelques cellules et, à partir de ces quelques exemples, un petit algorithme est synthétisé à la volée et se charge de finir le travail (https://deepsynth.labri.fr/). Un autre exemple est le contrôle robotique : un opérateur transmet à un robot une tâche à exécuter, par exemple reprendre le contrôle de la balle dans un match de Robocup, et charge au robot et à ses algorithmes de programmer la bonne suite de mouvements et d’actions à effectuer pour arriver au but escompté.
Quand les ingénieurs et chercheurs en Intelligence Artificielle (IA) ont besoin de résoudre des problèmes de synthèse, ils utilisent couramment un formalisme mathématique appelé processus de décision Markoviens, ou pour faire plus court, les MDP. La question centrale est la suivante : dans une situation où il faut prendre une suite de décisions, décrite par un MDP, comment faire pour prendre de bonnes décisions ? Ou, encore mieux, comment faire pour calculer automatiquement la meilleure suite de décisions possibles, ce qui s’appelle également une stratégie optimale ?
Les MDP pour décider
Mais qu’est-ce qu’un MDP exactement ? Dans le contexte de cette recherche, c’est un système à états finis dont l’évolution est déterminée à la fois par les décisions (choix d’action), mais également par le hasard. Voilà à quoi ressemble un tel animal :
Un exemple de MDP
Ce MDP illustre un exemple issu de l’article. C’est un jeu classique : il y a deux portes, et un tigre se cache derrière l’une des deux. On doit choisir quelle porte ouvrir, mais on ne sait pas où est le tigre. Grâce à l’action “écouter” (“listen” dans l’illustration) on peut révéler où se cache le tigre avec une probabilité positive.
Crédits : les auteurs.
Dans la vie courante, on peut se servir des MDP à de multiples occasions (nous les avions déjà rencontré dans le cas du Cluedo dans un autre article binaire), par exemple pour jouer au « Solitaire », également appelé « Patience » ou encore « Spider Solitaire » dans sa célèbre variante. La situation ci-dessous illustre le dilemme de la prise de décision dans un MDP : faut-il placer un des deux rois noirs sur la pile vide à gauche ? Si oui, lequel des deux ? Le choix est épineux car certaines cartes sont masquées et ne seront révélées qu’ultérieurement.
Jeu de Solitaire
Le jeu de Solitaire. Même quand toutes les cartes sont révélées, le problème est difficile : cf https://web.stanford.edu/~bvr/pubs/solitaire.pdf.
Crédits : les auteurs.
Stratégies de résolution des MDP
Il y a deux grandes catégories d’algorithmes IA pour résoudre un MDP, qui peuvent paraître similaires à première vue mais qui pour les chercheurs en informatique sont bien distinctes. D’une part, il y a les algorithmes qui fonctionnent bien en pratique mais sans garantie de fournir la meilleure solution, ce qui est le cas de la plupart des méthodes d’apprentissage, notamment celles utilisant les réseaux de neurones (DeepRL). D’autre part, il y a les algorithmes qui fournissent à coup sûr une réponse exacte, qui relèvent de l’IA de confiance, basée sur la notion de calculabilité et de problème décidable développé par le génie Alan Turing, pionnier de l’informatique théorique. L’article des chercheurs bordelais appartient à la seconde catégorie : quand l’algorithme proposé produit une stratégie gagnante, on peut utiliser cette stratégie en toute confiance — elle garantit de gagner avec probabilité 1.
Soyons modestes et réalistes : les techniques d’apprentissage permettent de calculer des stratégies dans des problèmes très complexes alors que les techniques exactes au sens de la théorie de la calculabilité sont pour l’instant circonscrites à des problèmes plus simples, car elles sont en général beaucoup plus gourmandes en ressources de calcul. Par exemple, Google DeepMind a exploité les techniques de DeepRL afin de synthétiser d’excellentes stratégies à StarCraft, un jeu vidéo populaire dans lequel il faut prendre des dizaines de décisions par seconde en fonction de millions de paramètres. L’IA de DeepMind a initialement battu les meilleurs joueurs mondiaux, mais sa stratégie n’était pas parfaite : des contre-stratégies difficilement prévisibles ont ensuite été découvertes. Les méthodes exactes sont aujourd’hui inexploitables pour résoudre un problème aussi complexe que StarCraft, mais cela ne les empêche pas d’être efficaces en pratique. Par exemple, autre succès bordelais, l’équipe Rhoban du LaBRI a remporté une médaille d’or à la Robocup 2023 en exploitant des méthodes exactes pour résoudre de petits MDP en se basant sur le partage d’informations entre plusieurs robots coopératifs (https://github.com/Rhoban/TeamPlay).
La difficulté de la résolution exacte de problèmes de décision est très variable en fonction de l’information disponible au moment de la décision. Le cas idéal est celui de l’information parfaite, c’est le cas où toute l’information est disponible. Un exemple classique est celui d’un robot qui doit sortir d’un labyrinthe dont on connaît le plan ainsi que la propre position et orientation exacte du robot. Dans ce cas, le calcul est relativement facile à effectuer : il faut calculer un chemin vers la sortie (par exemple avec l’algorithme de Dijkstra) puis suivre ce chemin avec la suite de commandes de déplacement adéquates. Mais dans les problèmes rencontrés en pratique, il est rare d’avoir toutes les cartes en main. C’est le cas au solitaire, où une partie des cartes est masquée, ce qui nécessite de faire des hypothèses. Dans ce cas, en toute généralité le problème ne peut être résolu de manière exacte, la réponse n’est pas calculable au sens de Turing : aucun algorithme, aussi puissant que soit l’ordinateur sur lequel il est programmé, ne peut résoudre avec exactitude tous les problèmes de contrôle de MDP. C’est assez démoralisant à première vue pour un informaticien mais cela n’arrête pas certains chercheurs en informatique qui s’attellent à trouver des classes de MDP pour lesquelles le problème est moins complexe. En informatique théorique, on appelle cela une classe décidable.
Le travail de recherche primé à AAAI fournit justement une classe décidable de MDP : c’est le cas des problèmes avec « révélation forte », pour lesquels à chaque instant il y a une probabilité non-nulle que l’état exact du monde soit révélé. L’article donne aussi des résultats de décidabilité pour le cas des « révélations faibles », qui garantit que l’état exact du monde ne peut rester inconnu infiniment longtemps.
Un article de recherche se doit d’être tourné vers le futur, d’ouvrir des pistes. Notre algorithme permet d’analyser les jeux avec des révélations (fortes). Une perspective intéressante est de retourner le problème : on peut se demander plus généralement ce que fait l’algorithme lorsqu’il est utilisé pour n’importe quel jeu, avec ou sans révélations. Cela permet d’envisager d’analyser tous les jeux, même les plus compliqués, mais en restreignant plutôt le type de stratégie que les joueurs utilisent, ou la quantité d’informations qu’ils sont capables de traiter.
Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn, Guillermo A. Pérez et Pierre Vandenhove
Répondre à cet article