Devoir 4 – Apprentissage par renforcement dans Pac-Man

Université de Sherbrooke
IFT615 – Intelligence artificielle, Hiver 2017

Professeur: Froduald Kabanza
Auxiliaire d'enseignement: Mariane Maynard

Date de remise: 2017-04-13

Source: The Pac-Man Projects, University of California, Berkeley

Fichiers à télécharger

Introduction

Pour toute question concernant ce travail, envoyez un courriel à Mariane Maynard.

Ce travail doit fonctionner avec la version 2.6 ou 2.7 du langage Python. Voici quelques ressources sur le langage Python qui pourraient vous aider dans votre travail:

Labyrinthe (Source: UC Berkeley)

Pour ce travail, vous devrez implémenter les algorithmes d'itération par valeurs (value iteration) et d'apprentissage par renforcement Q-learning.

Dans les fichiers fournis pour ce travail, un correcteur automatique est inclus pour évaluer votre implémentation. Celui-ci peut être lancé par la commande: python autograder.py Veuillez noter que votre note finale peut être différente de la note que vous obtenez avec le correcteur automatique.

Le code de ce projet consiste en plusieurs fichiers Python. Seuls les fichiers valueIterationAgents.py, qlearningAgents.py et analysis.py devront être modifiés et remis; les autres fichiers peuvent être consultés au besoin, mais ne doivent pas être modifiés. De plus, seules les sections indiquées dans les fichiers valueIterationAgents.py, qlearningAgents.py et analysis.py doivent être modifiées; les noms des classes et des variables globales ainsi que les signatures des méthodes et des fonctions ne doivent pas être modifiés.

Générateur de nombres aléatoires

Vous pouvez utiliser l'option --fixRandomSeed (ou -f) pour utiliser un seed fixe ('cs188', voir pacman.py à la ligne 534) avec le générateur de nombre aléatoires, de façon à ce que les fantômes aléatoires aient toujours le même comportement d'une exécution à l'autre.

Plagiat

Tout cas de plagiat sera sanctionné adéquatement. Voir le document informatif du Groupe de travail antiplagiat de l'Université de Sherbrooke à cet effet.

Premiers pas

Pour commencer, vous pouvez contrôler manuellement un agent dans une grille, en utilisant les flèches: python gridworld.py -m La grille comporte deux sorties en haut à droite ainsi qu'un obstacle au milieu de la pièce. L'agent est représenté par un point bleu. Un déplacement dans toute direction déplacera l'agent dans la direction voulue avec une probabilité de 80%.

Vous pouvez utiliser inspecter le texte affiché dans la ligne de commande pour voir les transitions empruntées par l'agent.

L'agent par défaut se déplace aléatoirement: python gridworld.py -g MazeGrid

Le processus de décision de Markov dans la grille est conçu de façon à ce que l'agent doive entrer dans un état pré-terminal (cases 1 et -1), dans lesquels une seule action est possible pour se rendre dans l'état terminal (non visible dans l'interface graphique).

Comme dans Pac-Man, les positions (x, y) sont des coordonnées cartésiennes, et tous les vecteurs sont indexés par [x][y], avec la direction north étant la direction qui augmente la valeur de y, etc. Par défaut, la plupart des transitions donnent une récompense de 0; cette valeur peut être changée avec l'option -r.

Itération par valeurs: 6 points

Implémentez un agent utilisant l'algorithme d'itération par valeurs dans la classe ValueIterationAgent, partiellement spécifiée dans le fichier valueIterationAgents.py. Votre agent sera un planificateur en différé (offline), pas un agent apprenant par renforcement; par conséquent, l'option -i spécifie le nombre d'itérations de l'algorithme d'itération par valeurs dans sa phase de planification. Le constructeur de la classe ValueIterationAgent prend un processus de décision de Markov en paramètre et exécute le nombre spécifié d'itérations avant de retourner.

En plus de l'algorithme d'itération par valeurs, vous devez aussi implémenter les méthodes suivantes de la classe ValueIterationAgent en utilisant l'estimation des valeurs optimales dans le vecteur Vk

Ces quantités sont affichées dans l'interface graphique: les valeurs dans self.values sont les nombres au milieu des cases, les valeurs Q sont les nombres dans les quartiers des cases, et la politique (action optimale pour chaque case) est indiquée par une flèche dans chaque case.

Vous devez implémenter la version de l'algorithme d'itération par valeurs qui calcule chaque vecteur Vk à partir du vecteur fixe de l'itération précédente Vk-1, pas la version en direct (online) qui met à jour les éléments d'un seul vecteur in situ. La différence entre les deux algorithmes est discutée dans le 6e paragraphe du chapitre 4.1 du livre de Sutton et Barto.

Utilisez la classe util.Counter du fichier util.py, un vecteur associatif donnant des valeurs par défaut de 0. Soyez cependant vigilants avec la méthode argMax: la véritable valeur argmax que vous voulez trouver pourrait ne pas être une clé dans l'objet Counter.

Assurez-vous de gérer le cas où un état n'a pas d'action possible dans le processus de décision de Markov; songez à ce que cela implique pour les récompenses futures.

Pour tester votre implémentation, vous pouvez lancer le correcteur automatique: python autograder.py -q q1

La commande suivante lance votre agent ValueIterationAgent, qui calculera une politique et l'exécutera 10 fois: python gridworld.py -a value -i 100 -k 10 Appuyez sur une touche pour alterner entre les valeurs V, les valeurs Q et la simulation. La valeur V de l'état initial et la récompense moyenne obtenue dans les 10 exécutions de la politique devraient être proches.

5 itérations de l'algorithme sur la grille par défaut devraient vous donner le résultat suivant: python gridworld.py -a value -i 5

Grille

Pont: 1 point

La grille BridgeGrid est une grille ayant un état terminal avec une faible valeur ainsi qu'un état terminal ayant une valeur élevée séparés par un pont, avec un gouffre de chaque côté d'états ayant des récompenses négatives. L'agent commence près de l'état terminal ayant une faible valeur.

Avec le facteur d'escompte par défaut de 0.9 et le bruit par défaut de 0.2, la politique optimale n'arrive pas à traverser le pont. Changez un seul de ces paramètres de façon à obtenir une politique capable de traverser le pont. Inscrivez votre réponse dans la fonction question2() du fichier analysis.py. (Le bruit indique la probabilité que l'agent se déplace dans une direction différente que la direction voulue en exécutant une action.)

Les valeurs par défaut (obtenues par la commande suivante) sont illustrées dans la figure ci-dessous: python gridworld.py -a value -i 100 -g BridgeGrid --discount 0.9 --noise 0.2

Grille

Pour tester votre réponse, vous pouvez lancer le correcteur automatique: python autograder.py -q q2

Politiques: 5 points

Observez la grille DiscountGrid ci-dessous. Cette grille possède deux états terminaux avec des récompenses positives (dans la rangée du milieu): un situé près de l'état initial (en jaune) avec une récompense de +1 et un autre plus loin avec une récompense de +10. Les états dans la rangée du bas de cette grille ont tous une récompense négative de -10. Il existe deux types de chemins dans cette grille: (1) les chemins qui prennent le risque de passer près des états négatifs; ces chemins (flèche rouge) sont plus cours, mais risquent d'obtenir une récompense fortement négative. (2) les chemins plus sûrs qui font le détour par le haut de la grille; ces chemins (flèche verte) sont plus longs, mais ont moins de chances d'obtenir une récompense fortement négative.

Grille

Vous devez choisir des valeurs pour le facteur d'escompte, le bruit et la récompense dans les autres états (cases noires sans nombres) afin que le processus de décision de Markov produise des politiques optimales de différents types. Un agent exécutant, sans bruit, la politique optimale obtenue avec vos valeurs de paramètres dans chaque partie devra avoir le comportement indiqué. Si le comportement est impossible peu importe la combinaison des paramètres, retournez la chaîne de caractères 'NOT POSSIBLE'.

Voici les types de politiques que vous devez tenter de produire:

  1. Préférer la sortie proche (+1) en risquant les états négatifs (-10)
  2. Préférer la sortie proche (+1) en évitant les états négatifs (-10)
  3. Préférer la sortie lointaine (+10) en risquant les états négatifs (-10)
  4. Préférer la sortie lointaine (+10) en évitant les états négatifs (-10)
  5. Éviter les deux sorties et les états négatifs (de façon à ce qu'un épisode ne se termine jamais)

Pour tester vos réponses, vous pouvez lancer le correcteur automatique: python autograder.py -q q3

Les fonctions question3a() à question3e() (fichier analysis.py) doivent retourner un triplet (escompte, bruit, récompense).

Q-learning: 5 points

Implémentez un agent Q-learning qui apprend par essai et erreur dans ses interactions avec l'environnement dans la méthode update(state, action, nextState, reward). Une esquisse d'un tel agent est spécifiée dans la classe QLearningAgent du fichier qlearningAgents.py, que vous pouvez sélectionner avec l'option -a q. Pour cette question, vous devez implémenter les méthodes update, computeValueFromQValues, getQValue et computeActionFromQValues.

Lorsque plusieurs actions ont des valeurs maximales égales dans la méthode computeActionFromQValues, choisissez le gagnant aléatoirement à l'aide de la fonction random.choice(). Dans un état donné, les actions que l'agent n'a pas encore vues ont tout de même une valeur Q (égale à 0); si toutes les actions que l'agent a vues jusqu'à présent ont une valeur Q négative, une action qu'il n'a pas encore vue pourrait être optimale.

Assurez-vous de toujours accéder aux valeurs Q dans les méthodes computeValueFromQValues et computeActionFromQValues en appelant la méthode getQValue.

Pour déboguer votre code, vous pouvez désactiver le bruit avec le paramètre --noise 0.0.

Pour tester votre implémentation, vous pouvez lancer le correcteur automatique: python autograder.py -q q4

Sélection epsilon-vorace des actions: 3 points

Complétez votre agent Q-learning en implémentant une sélection epsilon-vorace des actions dans la méthode getAction, c'est-à-dire que votre agent doit choisir une action aléatoire avec une probabilité epsilon et utiliser les valeurs Q sinon. Notez qu'une action aléatoire pourrait être une action optimale; vous devez choisir parmi toutes les actions valides, pas uniquement les actions sous-optimales. python gridworld.py -a q -k 100

Pour tester votre implémentation, vous pouvez lancer le correcteur automatique: python autograder.py -q q5

Vous pouvez simuler une variable binaire avec une probabilité de succès p en utilisant la fonction util.flipCoin(p), qui retourne True avec une probabilité p et False avec une probabilité 1-p.

Vous devriez être capable d'utiliser votre agent Q-learning dans un domaine différent, comme un bras robotisé devant déplacer un objet, sans code additionnel: python crawler.py Si cela ne fonctionne pas, votre code est probablement trop spécifique au domaine de la grille et vous devriez le rendre plus générique à tous les processus de décision de Markov.

Pont revisité: 1 point

Entraînez premièrement un agent Q-learning complètement aléatoire avec le taux d'apprentissage par défaut sur la grille BridgeGrid sans bruit pour 50 épisodes, et observez s'il trouve une politique optimale: python gridworld.py -a q -k 50 -n 0 -g BridgeGrid -e 1 Refaites la même expérimentation avec une valeur epsilon (paramètre -e) égale à 0.

Existe-t-il une combinaison d'un epsilon et d'un taux d'apprentissage (paramètre -l) avec lesquels la politique optimale sera trouvée après 50 itérations avec une probabilité > 99% ? La fonction question6() du fichier analysis.py devrait retourner soit une paire (epsilon, taux d'apprentissage) ou la chaîne de caractères 'NOT POSSIBLE' s'il n'existe aucune telle combinaison.

Pour tester votre réponse, vous pouvez lancer le correcteur automatique: python autograder.py -q q6

Q-learning approximatif dans Pac-Man I: 1 point

Pac-Man jouera des parties en 2 phases. Dans la première phase, l'apprentissage (sans interface graphique par défaut), Pac-Man apprendra les valeurs des cases et des actions. Ensuite, dans la phase de test, Pac-Man arrêtera d'apprendre (en mettant les variables self.epsilon et self.alpha à 0) et exploitera la politique qu'il a apprise. Vous devriez être capable d'utiliser votre agent Q-learning sans code supplémentaire: python pacman.py -p PacmanQAgent -x 2000 -n 2010 -l smallGrid

Si votre agent arrive à s'exécuter sans exception et à gagner au moins 80% du temps, vous aurez tous vos points pour cette question.

Si votre agent QLearningAgent fonctionne avec gridworld.py et crawler.py, mais ne semble pas apprendre une bonne politique pour Pac-Man dans la grille smallGrid, c'est peut-être parce que vos méthodes getAction et computeActionFromQValues ne considèrent pas correctement les actions non observées dans certains cas. En particulier, puisque les actions non vues ont par définition une valeur Q égale à 0, si toutes les actions vues ont une valeur Q négative, une action non vue pourrait être optimale. N'utilisez pas la méthode argMax de la classe util.Counter!

Pour tester votre implémentation, vous pouvez lancer le correcteur automatique: python autograder.py -q q7

Vous pouvez expérimenter avec différentes combinaisons des paramètres d'apprentissage avec l'option -a, par exemple -a epsilon=0.1,alpha=0.3,gamma=0.7.

Durant l'apprentissage, des statistiques seront affichées à chaque 100 parties jouées. La valeur epsilon est positive durant l'apprentissage, alors Pac-Man obtiendra de mauvais résultats même après avoir appris une bonne politique, parce qu'il exécutera occasionnellement des actions aléatoires qui pourraient l'envoyer sur un fantôme. Entre 1000 et 1400 parties devraient être nécessaires afin que Pac-Man obtienne des récompenses positives après un segment de 100 épisodes. Avant la fin de l'apprentissage, la récompense devrait rester positive et devrait être assez élevée (entre 100 et 350).

Assurez-vous de bien comprendre ce qui se passe ici: chaque état du processus de décision de Markov est une configuration exacte du labyrinthe, avec les transitions décrivant tous les changements apportés à cet état (déplacements de Pac-Man et de tous les fantômes). Les configurations intermédiaires du labyrinthe où Pac-Man a bougé, mais où les fantômes n'ont pas encore répondu ne sont pas des états du processus de décision de Markov, mais sont modélisés implicitement dans les transitions.

Q-learning approximatif dans Pac-Man II: 3 points

Implémentez un agent Q-learning approximatif qui apprend des poids pour des caractéristiques des états, où plusieurs états pourraient partager les mêmes caractéristiques. Écrivez votre implémentation dans la classe ApproximateQAgent du fichier qlearningAgents.py.

L'algorithme de Q-learning approximatif suppose l'existence d'une fonction f(s,a) qui associe des caractéristiques à des paires (état, action), et qui retourne donc un vecteur f1(s,a) … fi(s,a) … fn(s,a) de valeurs. De telles fonctions sont disponibles dans le fichier featureExtractors.py.

La valeur Q calculée par l'algorithme Q-learning approximatif prend la forme suivante: où chaque poids wi est associé à la caractéristique fi(s,a). Dans votre code, vous devriez implémenter le vecteur de poids comme un dictionnaire associant des caractéristiques à des poids. Vous devrez mettre à jour vos vecteurs de poids de façon semblable à la mise à jour des valeurs Q: Notez que le terme difference est le même que dans l'algorithme Q-learning normal, et que r est la récompense.

Par défaut, l'agent ApproximateQAgent utilise l'object IdentityExtractor, qui associe une seule caractéristique à toutes les paires (état, action). Avec cette fonction d'extraction des caractéristiques, votre agent Q-learning approximatif devrait se comporter exactement de la même façon que l'agent PacmanQAgent. Vous pouvez valider avec cette commande: python pacman.py -p ApproximateQAgent -x 2000 -n 2010 -l smallGrid

La classe ApproximateQAgent hérite de la classe QLearningAgent. Assurez-vous que vos méthodes dans QLearningAgent appellent la méthode getQValue au lieu d'accéder directement aux valeurs Q, de façon à ce que vous puissiez redéfinir cette méthode et calculer les actions en fonction de ces nouvelles valeurs Q approximatives.

Lorsque vous croyez que votre agent fonctionne correctement avec la caractéristique identité, vous pouvez lancer votre agent avec l'extracteur de caractéristiques simple, afin qu'il puisse facilement apprendre à gagner: python pacman.py -p ApproximateQAgent -a extractor=SimpleExtractor -x 50 -n 60 -l mediumGrid python pacman.py -p ApproximateQAgent -a extractor=SimpleExtractor -x 50 -n 60 -l mediumClassic (Attention, l'apprentissage peut prendre quelques minutes dans la grille mediumClassic.)

Pour tester votre implémentation, vous pouvez lancer le correcteur automatique: python autograder.py -q q8

Soumission

Le travail doit être remis par la commande par turnin sur le serveur opus.dinf.usherbrooke.ca au plus tard le 13 avril 2017 à 23:59:59. Remettez uniquement les fichiers : valueIterationAgents.py, qlearningAgents.py et analysis.py.

Écrivez votre nom, votre matricule et votre adresse courriel en commentaire dans l'entête de chaque fichier.