Implémentation du jeu du Wumpus
mono-agent & mutli-agents
sous Jade
29 Mars 2010
Introduction
Le projet consiste à implémenter le jeu du Wumpus en deux versions, mono-agent et multi-agents
sous Jade. Ceci dans le but d’implémenter l’algorithme de Q-learning, de trouver les bons
paramètres qui permettent sa convergence dans le cas mono-agent et d’essayer de trouver une
méthode d’implémentation pour que l’algorithme converge dans le cas multi-agents.
Ce rapport est divisé en deux parties. Dans la première partie nous décrirons le contexte du jeu,
ensuite nous présenterons la méthode proposée pour résoudre le problème de convergence en multi-
agents. Dans la deuxième partie qui est consacrée à l’implémentation, nous détaillerons
l’architecture du programme et le protocole d’interaction entre les agents. Puis nous expliquerons
l’évolution de l’apprentissage en se basant sur notre méthode d’implémentation.
1. Contexte
Le jeu du Wumpus est composé d’une grille, de n lignes et n colonnes, qui représente une caverne
dans laquelle un chasseur (ou plusieurs) doit se déplacer pour trouver un trésor, tuer un monstre et
sortir vivant malgré tous les obstacles.
Dans le monde des agents, le jeu est modélisé par un agent chasseur, un agent environnement (la
caverne) et les objets qui se trouvent dans l’environnement tels que le monstre, les trous et le trésor.
L’agent chasseur se trouve dans l’obscurité, et est guidé uniquement par ses perceptions. Celles-ci
sont fournies par l’agent environnement, sous forme de messages, à la demande de l’agent chasseur.
Dans ce contexte, notre objectif est d’apprendre au chasseur à trouver une politique optimale qui lui
mène au trésor. L’apprentissage se fait par l’algorithme de Q-learning qui attribut un poids à chaque
action a effectuée dans un état s parmi les actions possibles de cet état. La politique optimale qui
assure le gain de l’agent est alors déduit par le choix des actions possédants le plus gros poids dans
chaque état.
1.1 Méthode classique
Le problème de l’implémentation de l’algorithme de Q-learning est de fixer le point de convergence
qui permet à l’agent de passer d’un état d’exploration de l’environnement à un état d’exploitation de
ses connaissances.
Généralement les solutions proposées consistent à utiliser une table de hachage, par agent, indicée
par état et par action dans laquelle sont stockées les valeurs Q correspondantes à chaque couple
(état, action). L’algorithme converge alors après un très grand nombre d’itérations qui est
strictement liée au taux de remplissage de la table de hachage.
1.2 Méthode Proposée
Notre méthode se base sur le partage de connaissance. La base de connaissance est le résultat des
contributions de tous les agents. Chaque agent bénéficie de l’expérience des autres agents grâce à la
structure et la méthode utilisées pour le stockage des valeurs Q.
En pratique, nous utilisons un tableau simple par état indicé par les huit actions. En passant par un
état s, chaque agent ajoute au tableau sa contribution en mettant à jour la valeur Q. Ainsi, plus le
nombre d’agents est important, plus le remplissage de la structure est rapide et par la suite le point
de convergence sera rapidement atteint.
2. Implémentation
2.1 Architecture
Notre programme se compose de quatre packages:
Environnement: rassemble toute la fonctionnalité liée à l’environnement, telle que la structure, la
perception, la communication, et l’orchestration. Ce package regroupe (resp) les classes Cell et
Grid, Perception, WumpusACLMessage, et EnvironmentAgent.
-Gui: regroupe les deux classes qui se chargent de l’interface graphique, CellGui et GridGui.
-Hunter: contient la classe HunterAgent.
-Start: contient la classe Wumpus qui permet de lancer les agents.
Les classes du programme se divisent en quatre catégories: la structure, les agents, la
communication et l’interface graphique.
-La structure: les classes Cell et Grid forment la structure utilisée pour stocker les données. La
classe Cell détient toutes les informations. Tous les objets de l’environnement y sont définis, ainsi
que les huit actions possibles du jeu du Wumpus et leur table Q, tous encapsulés avec les deux
perceptions vent et odeur.
Un objet cell constitue la plus petite entité d’un objet grid qui à son tour n’est autre qu’un ensemble
de cellules. Plus précisément un objet grid est une matrice de cellules, elle s’occupe du placement
des objets dans les cellules correspondantes. Ainsi une cellule peut contenir de zéro à trois entités
(objets et/ou perceptions) avec un ou plusieurs chasseurs (version multi-agents).
-Les agents: la classe EnvironmentAgent est l’orchestrateur de toutes les actions. L’agent
environnement, ayant un comportement complètement réactif, répond aux demandes du chasseur.
Il exécute les actions et envoie les perceptions d’une manière cyclique.
La classe HunterAgent représente l’agent apprenant. Elle implémente l’algorithme de Q- learning.
L’agent chasseur calcule la valeur Q (après chaque action a dans un état s) mais il ne la stocke pas
car il ne possède pas le tableau. Ce dernier est stocké dans la cellule et c’est l’agent environnement qui s’en charge.
L’agent chasseur calcule la valeur Q (après chaque action a dans un état s) mais il ne la stocke pas
car il ne possède pas le tableau. Ce dernier est stocké dans la cellule et c’est l’agent environnement qui s’en charge.
La communication: est assurée par la classe WumpusACLMessage, qui hérite de la classe
ACLMessage de Jade, et la classe Perception. Un message est composé de deux entités, l’enveloppe
ou le type du message qui est un objet WumpusACLMessage et son contenu qui est un objet
Perception. Un objet Perception est composé d’un objet Cell et du résultat de l’action effectuée
(gagné, mort, Wumpus tué, action non disponible, succée).
L’interface graphique: se crée à partir des deux classes CellGui et GridGui. La classe CellGui est
le miroir de la classe Cell, elle s’occupe de la représentation graphique des objets et de la mise à
jour après chaque changement des états de l’environnement. La classe GridGui est une matrice de
CellGui.
Après une action, le changement d’un état de la grille ne nécessite que le rafraîchissement de la
cellule correspondante.
2.2 Les interactions
L’interaction entre l’agent chasseur et l’agent environnement se fait par envoi de messages. L’agent
chasseur initie la conversation en demandant sa position à l’agent environnement. Ce dernier, ayant
un comportement réactif, lui envoie sa position sous forme de perception.
En se basant sur la perception reçue, il demande à l’environnement d’effectuer une action.
L’environnement exécute l’action demandée (tirer ou se déplacer) et à son tour lui envoie le résultat
de l’action. Selon le résultat de l’action, la récompense reçue, le chasseur calcule la valeur Q et
envoie une demande de mise à jour du tableau Q-learning.
2.3 Apprentissage
Mono-agent: Dans un environnement stable et en se basant sur notre méthode d’implémentation,
nous avons remarqué que l’apprentissage évolue d’une manière très rapide. Sur une grille de 25
cases contenant quatre trous, le chasseur termine la phase d’exploration de la grille en un nombre
minimal d’itérations (20). Ce qui lui permet de passer à l’exploitation de ses connaissances, tuer le
Wumpus et remporter le trésor à tous les coups, en suivant le même chemin résultant de la politique
optimale calculée pendant la phase d’exploration.
Multi-agents: en conservant les mêmes données que dans le cas mono-agent (notre méthode
appliquée dans un environnement stable) l’apprentissage ne pose pas les problèmes de convergence
connus avec l’algorithme de Q-learning, parce que les agents partagent la connaissance. Le tableau
de Q-learning d’un état s est rempli par tous les agents qui le visite. Etant donné que la convergence
de l’algorithme est fortement liée au taux de remplissage du tableau Q, l’augmentation du nombre
d’agents permettra d'accélérer le remplissage des tableaux et par conséquent de réduire le nombre
d’itérations.
Conclusion
Notre méthode d’implémentation a été conçue spécialement pour un système multi-agents. le choix
d’encapsuler toutes les structures dans un objet cellule était dans le but de rendre l’apprentissage
disponibles à tous les agents à tout moment. Nous nous sommes inspirées du système routier qui
nous permet de partager les mêmes informations, disponibles sous forme de panneaux, elles nous
indiquent les directions et nous permettent de calculer notre chemin. C’est ce que nous faisons dans
notre programme, nous mettons des balises dans chaque cellule pour guider les agents.
En plus notre solution utilise peu de ressources grâce à l’utilisation d’un seul tableau simple de Q-
learning partagé par tous les agents.
