Devoir 3 – Inférences probabilistes dans Pac-Man

Université de Sherbrooke
IFT615 – Intelligence artificielle, Hiver 2017

Professeur: Froduald Kabanza
Auxiliaire d'enseignement: Mariane Maynard

Date de remise: 2017-03-30

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 des agents pour Pac-Man utilisant des capteurs pour localiser et manger des fantômes invisibles.

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 bustersAgents.py et inference.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 bustersAgents.py et inference.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.

Inférence exacte I: 3 points

Implémentez la méthode observe de la classe ExactInference dans le fichier inference.py pour mettre à jour correctement les croyances de l'agent sur la position d'un fantôme étant donnée l'information des capteurs de Pac-Man. Une bonne implémentation devrait aussi gérer un cas spécial: lorsqu'un fantôme est mangé par Pac-Man, sa position devrait être celle de la cellule de prison, tel que décrit dans les commentaires de la méthode observe.

Vous pouvez visualiser le résultat en lançant le correcteur automatique avec cette commande: python autograder.py -q q1 En regardant les scénarios de test, essayez de comprendre comment les cases convergent vers leur couleur finale.

Vous devez implémenter la mise à jour des croyances de Pac-Man pour une nouvelle observation. Avant toute lecture de ses capteurs, Pac-Man croit que les fantômes pourraient se trouver n'importe où (probabilité a priori uniforme, voir la méthode initializeUniformly). Après la lecture des capteurs, la méthode observe est appelée et celle-ci doit mettre à jour les croyances de Pac-Man pour chaque case.

Commencez par écrire l'équation du problème d'inférence que vous tentez de résoudre avant de commencer à écrire du code.

Affichez la valeur des variables noisyDistance, emissionModel et PacmanPosition dans la méthode observe pour vous aider à démarrer.

Les croyances (self.beliefs) sont des objets de type util.Counter (dictionnaires), que vous devez mettre à jour.

Vous ne devez pas conserver en mémoire les observations. Les seules informations que vous avez besoin de garder en mémoire sont dans la variable membre self.beliefs.

Inférence exacte II: 4 points

Pac-Man possède d'autres connaissances que seules les observations de la position des fantômes. En particulier, il sait que ceux-ci ne se déplacent que d'une seule case à la fois et sans pouvoir traverser des murs.

Pour comprendre pourquoi cela est utile pour Pac-Man, considérez un scénario dans lequel il n'y a qu'un seul fantôme avec Pac-Man. Ce dernier reçoit plusieurs observations indiquant que le fantôme est très proche de lui, puis reçoit une observation indiquant que le fantôme est soudainement très loin. Cette observation est probablement due à une erreur dans les capteurs imparfaits; les connaissances a priori de Pac-Man sur le déplacement des fantômes réduira l'impact de cette observation, puisqu'il sait que le fantôme ne pourrait s'être déplacé si loin en un seul tour.

Implémentez la méthode elapseTime de la classe ExactInference. Votre agent a accès à la distribution des actions d'un fantôme GhostAgent. Afin de tester votre implémentation de cette méthode indépendamment de la question précédente, cette question n'utilisera pas votre implémentation de la méthode observe.

Puisque Pac-Man n'utilise aucune observation du fantôme, il commencera avec une distribution uniforme sur toutes les cases et mettra à jour ses croyances sachant comment un fantôme peut se déplacer. Au fil du temps, les croyances de Pac-Man finiront par refléter les cases du labyrinthe où il croit que des fantômes sont les plus susceptibles de se trouver étant donné la géométrie du labyrinthe et la connaissance de Pac-Man sur les déplacements valides des fantômes.

Pour évaluer cette question, plusieurs types de fantômes seront utilisés, par exemple des fantômes aléatoires et des fantômes se déplaçant vers le sud (GoSouthGhostAgent). Ceux-ci tendent à se déplacer vers le bas du labyrinthe avec le temps, et sans observation les croyances de Pac-Man devraient se focaliser vers cette région.

Vous pouvez lancer le correcteur automatique et visualiser le résultat avec cette commande: python autograder.py -q q2 Pour observer le comportement du fantôme GoSouthGhostAgent, vous pouvez exécuter: python autograder.py -t test_cases/q2/2-ExactElapse et observer que la distribution des croyances se concentre au bas du labyrinthe.

Les commentaires de la méthode elapseTime de la classe ExactInference indiquent comment obtenir une distribution sur les prochaines positions possibles d'un fantôme étant donnée sa position actuelle dans l'état du jeu (gameState).

Inférence exacte III: 3 points

Cette question utilisera vos implémentations des méthodes observe et elapseTime, avec une stratégie vorace simple pour chasser les fantômes. Dans cette stratégie, Pac-Man assume que chaque fantôme se trouve dans la case la plus probable étant données ses croyances, et se dirige ensuite vers le fantôme le plus proche.

Implémentez la méthode chooseAction dans la classe GreedyBustersAgent dans le fichier bustersAgents.py. Votre agent devra commencer par trouver la position la plus probable de chaque fantôme qui n'a pas encore été capturé pour ensuite choisir une action qui minimise sa distance avec le fantôme le plus proche. S'il est correctement implémenté, votre agent devrait gagner la partie dans le test q3/3-gameScoreTest avec un pointage > 700 au moins 8 fois sur 10.

Le correcteur automatique vérifie que les inférences sont correctes, mais le pointage obtenu dans les parties est aussi un bon indicateur.

Pour lancer le correcteur automatique et visualiser le résultat: python autograder.py -q q3

Pour exécuter les tests sans interface graphique, vous pouvez ajouter l'option --no-graphics: python autograder.py -q q3 --no-graphics

Les commentaires dans la méthode chooseAction donnent quelques méthodes utiles pour calculer les distances dans un labyrinthe et les états successeurs.

Assurez-vous de ne considérer que les fantômes vivants, tel que décrit dans les commentaires.

Filtre de particules I: 3 points

Implémentez les méthodes initializeUniformly, getBeliefDistribution et observe de la classe ParticleFilter dans le fichier inference.py.

Une implémentation correcte devrait aussi gérer deux cas particuliers: (1) lorsque toutes les particules ont un poids de zéro sachant les observations, les particules devraient être rééchantillonnées avec les probabilités a priori avant de recommencer; et (2) lorsqu'un fantôme se fait manger, toutes les particules devraient être mises à jour pour placer ce fantôme dans la cellule de prison, tel que décrit dans les commentaires de la méthode observe.

Vous pouvez lancer le correcteur automatique et visualiser les résultats avec cette commande: python autograder.py -q q4

Filtre de particules II: 4 points

Implémentez la méthode elapseTime de la classe ParticleFilter dans le fichier inference.py.

Cette question testera la méthode elapseTime individuellement ainsi que l'implémentation complète du filtre de particules avec les méthodes elapseTime et observe combinées.

Vous pouvez lancer le correcteur automatique et visualiser les résultats avec cette commande: python autograder.py -q q5

Filtre de particules joint I: 4 points

Jusqu'à présent, les fantômes ont été traqués indépendamment, ce qui fonctionne correctement avec des fantômes aléatoires ou des fantômes plus avancés comme DirectionalGhost. Par contre, l'agent DispersingGhost choisit des actions qui le font éviter les autres fantômes. Puisque les modèles de transition des fantômes ne sont plus indépendants, les fantômes doivent être traqués simultanément par un réseau bayésien dynamique.

Le réseau bayésien a la structure ci-dessous, avec les variables cachées G représentant les positions des fantômes et les variables observées E représentant les distances bruitées à chaque fantôme. Cette structure peut être étendue pour y avoir plusieurs fantômes, mais seulement 2 (a et b) sont montrés ci-dessous.

Vous allez maintenant devoir implémenter un filtre de particules qui traque plusieurs fantômes simultanément. Chaque particule représente un tuple de positions de fantômes, échantillonnées à partir de leur position courante. Le code s'occupe déjà d'extraire la distribution marginale pour chaque fantôme à partir de l'algorithme d'inférence que vous allez créer.

Complétez les méthodes initializeParticles, getBeliefDistribution et observeState dans la classe JointParticleFilter pour rééchantillonner toutes les particules étant données les nouvelles observations.

Votre agent devrait maintenant être capable de traquer efficacement les fantômes qui de dispersent. Vous pouvez lancer le correcteur automatique et visualiser les résultats avec cette commande: python autograder.py -q q6

Filtre de particules joint II: 4 points

Complétez la méthode elapseTime de la classe JointParticleFilter dans le fichier inference.py pour rééchantillonner chaque particule correctement pour le réseau bayésien. En particulier, la position d'un fantôme devrait être décidée en fonction de la position de tous les fantômes à l'étape précédente.

Les commentaires de la méthode elapseTime indiquent comment calculer les distributions sur les positions des fantômes et comment échantillonner correctement.

Les tests q7/1-JointParticleElapse et q7/2-JointParticleElapse valident l'implémentation de la méthode elapseTime seulement, alors que le test q7/3-JointParticleElapse valide les méthodes elapseTime et observe ensemble.

Vous pouvez lancer le correcteur automatique et visualiser les résultats avec cette commande: python autograder.py -q q7

Soumission

Le travail doit être remis par turnin sur le site opus.dinf.usherbrooke.ca au plus tard le 30 mars 2017 à 23:59:59. Remettez uniquement les fichiers : bustersAgents.py et inference.py.

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