Devoir 1 – Algorithmes de recherche dans Pac-Man

Université de Sherbrooke
IFT615 – Intelligence artificielle, Hiver 2017

Professeur: Froduald Kabanza
Auxiliaire d'enseignement: Mariane Maynard

Date de remise: 2017-02-02

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, votre agent Pac-Man devra trouver des chemins dans des labyrinthes, que ce soit pour atteindre un endroit précis ou pour manger des gommes de façon efficace. Vous devrez implémenter des algorithmes de recherche génériques et les appliquer à des scénarios dans le jeu de Pac-Man.

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 search.py et searchAgent.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 search.py et searchAgent.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.

Tous les algorithmes de recherche doivent retourner une liste d'actions qui mèneront l'agent de son état initial jusqu'à son but. Ces actions doivent être légales (e.g., direction valide, pas de déplacement au travers des murs).

Utilisez les structures de données Stack, Queue et PriorityQueue fournies dans le fichier utils.py pour implémenter vos algorithmes.

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

Après avoir téléchargé et extrait le code source, vous devriez pouvoir jouer à Pac-Man en lançant cette commande: python pacman.py

Le fichier searchAgents.py contient les agents intelligents utilisant des algorithmes de recherche, implémentés dans le fichier search.py. L'agent le plus simple est implémenté dans la classe GoWestAgent, qui se déplace toujours vers l'ouest: python pacman.py --layout testMaze --pacman GoWestAgent Bien entendu, cet agent trivial n'arrive pas à résoudre des labyrinthes plus complexes: python pacman.py --layout tinyMaze --pacman GoWestAgent

Dans le fichier searchAgents.py, vous trouverez un agent complètement implémenté dans la classe SearchAgent, qui planifie un chemin dans un labyrinthe de Pac-Man et qui exécute ce chemin étape par étape. Votre travail consiste à implémenter les algorithmes de recherche qui seront utilisés par cet agent.

Testez d'abord que le SearchAgent fonctionne correctement avant la commande: python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch La commande ci-dessus indique que le SearchAgent doit utiliser la fonction tinyMazeSearch comme algorithme de recherche, implémenté dans search.py. Pac-Man devrait réussir à atteindre son objectif dans le labyrinthe.

Recherche en profondeur (depth-first search): 3 points

Implémentez un algorithme de recherche en profondeur dans la fonction depthFirstSearch du fichier search.py. L'algorithme doit être implémenté comme une recherche dans un graphe qui évite d'explorer les états déjà visités. Le code devrait rapidement trouver une solution pour les exemples ci-dessous: python pacman.py -l tinyMaze -p SearchAgent
python pacman.py -l mediumMaze -p SearchAgent
python pacman.py -l bigMaze -z .5 -p SearchAgent

Si vous utilisez la Stack comme structure de données, la solution trouvée par l'algorithme de recherche en profondeur pour le labyrinthe mediumMaze devrait avoir une longueur de 245 si les états sont ajoutés à la frontière dans le même ordre que la liste retournée par la méthode getSuccessors, ou 146 si les états sont insérés dans l'ordre inverse.

Recherche en largeur (breadth-first search): 3 points

Implémentez une recherche en largeur dans la fonction breadthFirstSearch du fichier search.py. Encore une fois, l'algorithme de recherche dans un graphe doit éviter d'explorer les états déjà visités. Le code peut être testé de la même façon que l'algorithme de recherche en profondeur: python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

Si l'algorithme a été implémenté de façon générique, il devrait pouvoir résoudre le jeu de taquin à 8 cases sans modification: python eightpuzzle.py

Recherche à coût uniforme (uniform-cost search): 3 points

Même si l'algorithme de recherche en largeur réussi à trouver un chemin ayant un nombre minimal d'actions pour atteindre le but, il pourrait être intéressant de trouver de meilleurs chemins dans d'autres contextes; considérez par exemple les labyrinthes mediumDottedMaze et mediumScaryMaze.

En changeant la fonction de coût, il est possible d'encourager Pac-Man à trouver des chemins différents. Par exemple, les déplacements dans les zones où il y a des fantômes pourraient avoir un coût plus grand, les zones où il y a beaucoup de gommes à manger pourraient avoir un coût moindre, et un agent rationnel devrait ajuster son comportement en conséquence.

Implémentez l'algorithme de recherche à coût uniforme dans la fonction uniformCostSearch du fichier search.py.

Recherche heuristique A*: 3 points

Implémentez l'algorithme de recherche heuristique dans un graphe A* dans la fonction aStarSearch du fichier search.py. L'algorithme A* prend une fonction heuristique en paramètre. Une fonction heuristique requiert deux paramètres: un état dans le problème de recherche et le problème lui-même. La fonction nullHeuristic dans search.py montre un exemple trivial.

Vous pouvez tester votre implémentation de A* en l'utilisant pour trouver un chemin vers une position donnée dans un labyrinthe en utilisant la distance de Manhattan comme fonction heuristique (déjà implémentée dans la fonction manhattanHeuristic du fichier searchAgents.py): python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

Visiter tous les coins: 3 points

Certains labyrinthes ont des gommes dans chacun des quatre coins. Un nouveau problème de recherche consiste à trouver le chemin le plus court pour visiter les quatre coins, qu'il y ait des gommes ou non. Pour certains labyrinthes comme tinyCorners, le chemin le plus court ne passe pas par la gomme la plus près du point de départ en premier.

Dans tinyCorners, le chemin le plus court nécessite 28 déplacements.

L'algorithme de recherche en largeur doit avoir été implémenté avant de résoudre ce problème.

Implémentez la classe CornersProblem dans le fichier searchAgents.py. Vous devrez choisir une représentation de l'état qui encode l'information nécessaire pour détecter si les quatre coins ont été visités. Votre agent devrait être capable de résoudre ce problème: python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem
python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

Afin d'obtenir tous vos point pour cette question, votre représentation de l'état ne doit pas encoder de l'information qui n'est pas nécessaire pour résoudre le problème (par exemple la position des fantômes et la position des autres gommes).

Les seules informations de l'état du jeu à conserver en mémoire sont la position initiale de Pac-Man ainsi que la position des quatre coins.

Fonction heuristique pour visiter tous les coins: 3 points

L'algorithme de recherche heuristique A* doit avoir été implémenté avant de résoudre ce problème.

Implémentez une fonction heuristique non triviale, admissible et monotone pour visiter tous les coins dans la fonction cornersHeuristic du fichier searchAgents.py: python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

Une heuristique est une fonction qui estime le coût restant pour atteindre le but. Les fonctions heuristiques efficaces retournent une valeur qui s'approche du coût réel. Une fonction heuristique admissible est non négative et ne surestime pas le coût pour atteindre le but. Pour qu'une heuristique admissible soit aussi monotone, il faut que l'exécution d'une action ayant un coût x réduise la valeur de la fonction heuristique d'au plus x. Une fonction heuristique triviale retourne toujours 0 ou encore le coût réel, calculé par exemple par un planificateur.

Pour vous mériter des points dans cette question, la fonction heuristique doit être non négative, non triviale, admissible et monotone. Les points seront alloués en fonction du nombre d'états visités par l'algorithme:

Nombre d'états visités Note
> 2000 0/3
≤ 2000 1/3
≤ 1600 2/3
≤ 1200 3/3

Manger toutes les gommes: 4 points

Un problème plus difficile consiste à manger toutes les gommes en effectuant le moins de déplacements possible. La classe FoodSearchProblem dans searchAgents.py (déjà implémentée) formalise la définition de ce problème. Une solution à ce problème est un chemin qui passe par toutes les cases où il y a des gommes dans le labyrinthe. Les solutions n'ont pas à considérer les fantômes ni les grosses gommes, elles ne dépendent que de la position des murs, des gommes ainsi que de Pac-Man.

Si les algorithmes de recherche ont été implémentés correctement, l'algorithme A* avec une heuristique nulle (équivalent à la recherche à coût uniforme) devrait rapidement trouver une solution dans le labyrinthe testSearch sans changer le code. Le coût total du plan devrait être 7. python pacman.py -l testSearch -p AStarFoodSearchAgent

L'algorithme de recherche heuristique A* doit avoir été implémenté avant de résoudre ce problème.

Implémentez la fonction foodHeuristic dans le fichier searchAgents.py avec une heuristique admissible et monotone pour le problème FoodSearchProblem. Testez votre agent sur le labyrinthe trickySearch: python pacman.py -l trickySearch -p AStarFoodSearchAgent Toute fonction heuristique non négative, non triviale, admissible et monotone se méritera au moins 1 point. Les autres points seront alloués en fonction du nombre d'états visités par l'algorithme:

Nombre d'états visités Note
> 15 000 1/4
≤ 15 000 2/4
≤ 12 000 3/4
≤ 9000 4/4
≤ 7000 (difficile) 5/4

Recherche sous-optimale: 3 points

Trouver un chemin optimal passant par toutes les gommes peut s'avérer un problème difficile, même avec un algorithme A* équipé d'une bonne fonction heuristique. L'objectif dans cette section sera d'écrire un agent vorace qui mange la gomme la plus proche. La classe ClosestDotSearchAgent est déjà implémentée dans le fichier searchAgents.py, mais il manque une méthode clé qui trouve un chemin vers la gomme la plus proche.

Implémentez la méthode findPathToClosestDot dans le fichier searchAgents.py: python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

L'implémentation la plus simple de la méthode findPathToClosestDot utilise la classe AnyFoodSearchProblem, dont la méthode isGoalState est à compléter.

Bonus: 2 points

Malgré les 2 points boni, la note maximale pour ce travail sera 25/25, ramenée sur 10 points. Les points supplémentaires ne seront pas rapportés sur les travaux futurs.

Implémentez un agent dans la classe ApproximateSearchAgent du fichier searchAgents.py qui trouve le chemin le plus court dans le labyrinthe bigSearch. Les points seront alloués en fonction du coût de la solution trouvée par l'algorithme:

Coût de la solution Note
≤ 290 1/2
≤ 280 2/2

Évidemment, une solution préprogrammée (hardcoded) ne se méritera aucun point.

Votre implémentation sera testée avec cette commande: python pacman.py -l bigSearch -p ApproximateSearchAgent -z .5 -q L'algorithme doit retourner une solution en moins de 30 secondes.

Soumission

Le travail doit être remis par turnin sur le site opus.dinf.usherbrooke.ca au plus tard le 2 février 2017 à 23:59:59. Remettez uniquement les fichiers: search.py et searchAgent.py.

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