Comment une machine joue-t-elle au Cluedo ? Un modèle d’Intelligence Artificielle pour la recherche d’information (Curiosité)

Écriture : Jennifer Renoux
Relecture de contenu : Cédric Buron et Vincent Thomas
Relecture de forme : Aurélien Didier, Alexandre Fauquette et Christine Duthoit

Temps de lecture : environ 10 minutes.
Thématiques : Intelligence artificielle (Informatique, Sciences cognitives)

Publication originale : Spaan M., et al., Decision-theoretic planning under uncertainty with information rewards for active cooperative perception. Autonomous Agents and Multi-Agent Systems, 2014. DOI : 10.1007/s10458-014-9279-8

Version approfondissement

Les bons joueurs de Cluedo sont efficaces dans leur recherche d’information : ils planifient leurs actions afin d’obtenir le plus d’information possible en un minimum de temps. On appelle ce processus « perception active », et c’est une capacité que les humains maîtrisent très bien. Pour les machines, en revanche, c’est plus compliqué. Dans un article de 2015, Matthijs Spaan, Tiago Veiga et Pedro U. Lima ont proposé un modèle dotant les machines de capacités de perception active, avec des applications dans le domaine de la robotique autonome pour la surveillance ou le sauvetage de personnes.

Perception active et planification sous incertitude. Kesako ?

En tant qu’humain, lorsque que l’on marche dans la rue, on absorbe de l’information sur ce qui se passe autour de nous : le feu piéton au vert, le tram qui arrive en station ou le fait que le bâtiment où l’on va se trouve droit devant nous. Ces informations sont intégrées par notre cerveau presque inconsciemment pendant qu’il est occupé à planifier la prochaine action pour nous amener à notre but final : notre rendez-vous chez le docteur. Quand on souhaite remplacer l’humain par un robot, un ordinateur ou n’importe quelle entité artificielle (appelée agent artificiel, souvent abrégé en agent), et lui permettre de planifier une séquence d’actions, on tombe dans un sous-domaine de l’Intelligence Artificielle, qui s’appelle la Planification Automatique. Dans le monde de la planification automatique, la plupart des problèmes considérés suivent ce schéma : l’agent calcule un plan lui permettant d’accomplir sa mission, et l’information qu’il obtient lors de l’exécution de ce plan est au service de la mission. La recherche d’information est alors un moyen pour atteindre un but et non le but en lui-même. Cependant, il existe certains cas d’applications où la recherche d’information n’est pas seulement un moyen pour l’agent d’atteindre un but mais constitue le but en lui-même. C’est par exemple le cas dans des applications de surveillance et de patrouille, mais aussi de recherche et de sauvetage, où la vie de personnes dépend de la capacité des sauveteurs et sauveteuses (humain·e·s ou artificiel·le·s) à collecter de l’information vite et bien.

Ce processus s’appelle la Recherche active d’information ou Perception Active. Le but ici est de collecter le plus d’information possible à propos de certains points d’intérêts. Pensez notamment à une partie de Cluedo, où il vous faut trouver le coupable, l’arme et le lieu du crime. Vous devez donc vous déplacer dans l’environnement et récolter de l’information afin d’éliminer, les uns après les autres, suspect·e·s, armes, et lieux potentiels. 

Pour un humain, la perception active est simple. On la pratique depuis qu’on est gamin·e, quand on joue à cache-cache ou quand on cherche nos clefs. Notre cerveau y est entraîné. Mais comme souvent dans le domaine de l’Intelligence Artificielle, ce qui est facile pour un humain peut être très compliqué pour un agent artificiel. La perception active se fonde sur un modèle de connaissances de l’agent : il faut que l’on soit capable de modéliser ce que l’agent va considérer comme une certitude, mais également ce qu’il doit vérifier. 

Dans cet article, les auteurs se placent dans le cadre de la planification séquentielle sous incertitude : on souhaite trouver la meilleure séquence d’actions possible afin d’atteindre un but donné, tout en sachant que l’on ne connaît pas tout de l’environnement. Dans le cas de votre rendez-vous chez le docteur, vous allez tenter de trouver la meilleure suite d’actions (quel tram prendre, tourner à droite à la seconde rue, etc.) pour arriver chez le docteur le plus rapidement possible. Pour ce faire, une solution possible est d’attribuer une valeur à certains états et certaines actions que l’on juge désirables. Par exemple, l’état « je suis chez mon docteur » aura une forte valeur positive car c’est l’état que l’on souhaite obtenir. En revanche, l’état « je suis immobile sur la ligne de tram » aura une très forte valeur négative car c’est particulièrement dangereux. On va donc récompenser notre agent lorsqu’il est dans état désirable ou effectue une action désirable, et le pénaliser s’il est dans un état ou effectue une action non désirable. Dans ce cas, ce qu’on appelle récompense ou pénalité correspond à cette valeur mathématique que l’on attribue aux différents états et actions et qu’on l’on donne à l’agent lorsqu’il se trouve dans cet état ou effectue cette action. Le but de l’agent (= la façon dont il est programmé) va être de maximiser sa récompense, immédiate et potentielle. 

Le problème, c’est que dans la vraie vie, on n’a pas accès à toute l’information tout le temps. Par exemple, peut-être que le tram est au prochain croisement ou peut-être qu’il est à l’autre bout de la ligne. Selon la situation, la valeur associée à l’action « se trouver sur la ligne de tram » peut donc changer. Ce qui est possible en revanche, c’est de collecter de l’information sur la position du tram, par exemple en regardant sur l’application dédiée sur mon téléphone. L’information que j’obtiendrai ainsi ne sera pas absolument exacte (l’application peut avoir un léger décalage ou seulement donner le prochain arrêt par exemple) mais elle me permettra d’effectuer un raisonnement complexe, comme  « le tram est 3 arrêts plus loin, je peux rester un peu sur la ligne sans danger, mais plus j’attends plus c’est dangereux ». 

Il existe un modèle mathématique, basé sur la théorie des probabilités, qui permet de modéliser ce genre de problème, et qui s’appelle le Processus de Markov Partiellement Observable (POMDP de son petit nom, prononcez pom-dé-pé). Les POMDP permettent de modéliser tout ce qui peut se passer dans notre monde : les états possibles, les effets possibles des actions de l’agent ainsi que leur probabilité d’occurrence, et ce que l’agent reçoit comme information lorsqu’il effectue une action.

À partir de là, il existe de nombreux algorithmes qui permettent à un agent de raisonner sur l’ensemble des situations, de considérer les différentes actions possibles et de choisir la meilleure suite d’actions à effectuer en fonction de ce qu’il sait, de ce qu’il a vu du monde et afin d’atteindre son but. Par exemple, pour mon Cluedo, si je sais que j’ai la carte Salon dans la main, je ne vais généralement pas me déplacer dans le salon car je sais que ça ne fait pas partie de la solution. Néanmoins, l’une des limitations de ce modèle est que les valeurs ne peuvent être attribuées qu’à des états et des actions (par exemple : arriver chez le docteur). Or dans le cas de la recherche active d’information, le comportement désirable est celui qui permet à notre agent d’en apprendre le plus possible sur le monde. Il n’est donc pas lié à un état ou une action particulière mais à son état de connaissance : on aimerait récompenser l’agent s’il sait que le crime a eu lieu dans le salon. Peu importe si notre agent se trouve dans la cuisine ou la salle à manger et comment il le sait. L’important, c’est qu’il le sache. C’est cette limitation que les auteurs de l’article tentent de dépasser.

Actions d’Engagement : le Colonel Moutarde dans la cuisine avec le chandelier

Pour modéliser cette récompense basée sur l’état de connaissance d’un agent, les auteurs présentent un nouveau modèle basé sur les POMDP, qu’ils appellent « POMDP-IR » (pour POMDP with Information Reward ou POMDP avec récompense d’information en français). Dans ce nouveau modèle, les auteurs introduisent ce qu’ils appellent des actions d’engagement. Pour comprendre ce qu’est une action d’engagement, repensez au Cluedo. À la fin de la partie, lorsque vous avez obtenu assez d’information sur les différentes pièces, armes et suspect·e·s, vous êtes suffisamment sûr·e de vous pour émettre une accusation : « c’est le Colonel Moutarde dans la cuisine avec le chandelier ». Cette accusation est une action d’engagement : si vous avez raison, vous serez récompensé·e (vous gagnez la partie). Si vous avez tort, vous serez pénalisé·e (vous sortez du jeu). De ce fait, vous vous assurez d’avoir suffisamment d’information avant d’émettre votre accusation. Et bien dans cet article, les auteurs ont créé des agents capables de jouer de Cluedo ! Grâce aux actions d’engagement, l’agent se focalise sur les actions qui lui permettent de récolter de l’information afin d’obtenir un état de connaissance suffisant avant de s’engager, et donc soit de recevoir une récompense (s’il a raison), soit d’être pénalisé (s’il a tort).

Mais nos agents POMDP-IR ne sont pas que des joueurs de Cluedo et peuvent faire bien plus. En effet, un POMDP-IR permet de modéliser, en parallèle des actions d’engagement, n’importe quelle autre action qui serait modélisable dans un POMDP. À chaque action, l’agent peut alors décider simultanément d’une action « normale » et de s’engager ou non. De ce fait, le POMDP-IR permet de modéliser des problèmes multi-objectifs, où l’agent doit mettre en œuvre sa perception active tout en poursuivant une autre mission. On peut imaginer par exemple le cas de missions de sauvetage où l’agent doit retrouver des victimes et sécuriser l’environnement. Sécuriser l’environnement est la mission « classique » (au sens des POMDP, car il s’agit de modifier l’état de l’environnement par les actions de l’agent), alors que retrouver les victimes est une mission de perception active (modélisable par un POMDP-IR), car on attend de l’agent qu’il prenne des actions d’engagement du type  « je sais qu’il y a un blessé au troisième étage ».

Donc on peut maintenant récompenser un agent pour effectuer sa mission tout en ayant un état de connaissance suffisant. Mais, ça veut dire quoi suffisant ?

Les auteurs nous disent : suffisant, ça dépend du contexte ! Évidemment, ce que vous considérez comme étant un état de connaissance suffisant dépend énormément de votre application. S’il s’agit d’indiquer à l’utilisateur·rice que le café est prêt, les erreurs ne sont pas bien graves. Par contre s’il s’agit de secourir des victimes, une erreur pourrait vous coûter cher. Les auteurs démontrent également qu’à vouloir être trop sûr, l’agent risque de se focaliser sur sa recherche d’information, quitte à délaisser toute autre mission qui pourrait lui être confiée. Dans le cas de notre agent de sauvetage par exemple, si l’on demande à l’agent d’être trop sûr d’où se trouvent les victimes, notre agent va passer son temps à vérifier et re-vérifier chaque pièce en négligeant de sécuriser l’environnement, risquant ainsi la vie de ses coéquipiers.

Pourquoi ce modèle est-il intéressant ?

Dans le monde de la recherche en Intelligence Artificielle, produire un nouveau modèle ne suffit pas, encore faut-il qu’il soit intéressant. Alors comment détermine-t-on qu’un modèle est intéressant ? Souvent grâce à deux questions :

  1. Ce modèle permet-il de modéliser un type de problème qu’on ne savait pas traiter jusque là ? Si oui, il permet d’accroître le nombre de problèmes qu’un agent artificiel peut traiter et il est donc intéressant.    
       
  2. Si d’autres modèles permettent déjà de modéliser le même type de problème que ce nouveau modèle, ce nouveau modèle est-il meilleur que l’ensemble des autres modèles existant ?
       
    • Est-il plus simple à appliquer ?        
             
    • Donne-t-il de meilleurs résultats ?        
         

Dans notre cas, le POMDP-IR introduit par Matthijs Spaan et ses collègues ne permet pas de modéliser de nouveaux problèmes car il existe déjà un autre modèle permettant de traiter le problème de la recherche active d’information. Ce modèle, appelé \rho-POMDP, a été proposé cinq ans plus tôt (en 2010) par Mauricio Araya-Lopez et ses collègues [1]. D’après ses auteurs, le POMDP-IR permet de meilleurs résultats que le \rho-POMDP, au sens où un agent qui suivrait un POMDP-IR aura une meilleure récompense finale (et donc sera a priori plus efficace dans sa tâche) qu’un agent qui suivrait un \rho-POMDP.

Conclusion et Discussion

Le modèle développé par les auteurs dans cet article permet à un agent de raisonner sur ses connaissances afin d’agir au mieux pour acquérir de nouvelles connaissances tout en poursuivant d’autres buts. Ce modèle se base essentiellement sur la notion d’actions d’engagement, qui permettent de récompenser l’agent lorsque celui-ci obtient un bon niveau de connaissance sur le monde. 

L’une des difficultés majeures associées à ce modèle est de trouver le bon équilibre entre les différentes missions. C’est un aspect qui n’est pas du tout abordé dans l’article, mais qui est pourtant capital afin d’obtenir un comportement adéquat. En effet, dans le cas de notre agent de sauvetage, l’agent est récompensé s’il trouve les victimes correctement et s’engage sur leur position, mais également s’il sécurise au mieux l’environnement. La relation entre ces deux récompenses est tout aussi capitale que le degré de suffisant afin d’obtenir un agent qui effectue bien ses deux missions. Une récompense trop élevée pour la sécurisation de l’environnement par rapport à celle pour la recherche de victimes va inciter l’agent à prioriser la sécurisation et négliger la recherche des victimes, et inversement une récompense de sécurisation trop faible par rapport à la récompense de recherche de victime va inciter l’agent à négliger sa tâche de sécurisation. Ce problème n’est cependant pas propre au POMDP-IR, puisqu’il existe dans tout modèle la nécessité de trouver un compromis entre différents objectifs, ce qui implique malheureusement souvent une suite d’essais et d’erreurs afin de trouver la bonne configuration.

Le problème de raisonner et planifier sur l’état de connaissance d’un agent est un sujet qui suscite énormément d’intérêt dans la communauté de recherche sur la planification automatique. Ce (relativement) nouveau domaine de recherche est appelé Planification Épistémique et verra probablement émerger de nombreux modèles dans le futur, ouvrant ainsi la voie à beaucoup de nouvelles applications.

Note : l’autrice de ce papier-mâché est actuellement en collaboration avec les auteurs de la publication initiale. Cette collaboration a débuté après la publication dudit article, mais concerne un sujet similaire à celui abordé ici.

_________

[1] Araya-Lopez M., Buffet O., Thomas V., Charpillet F., A POMDP Extension with Belief-dependent Rewards.NIPS Proceedings, 2010. 

_________

Creative Commons License
Jennifer Renoux/Papier-Mâché/CC BY 4.0

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.