Projet: Agent Logique pour la chasse au Wumpus

Projet : Agent Logique pour la chasse au Wumpus

(Adapté de http://www.sista.arizona.edu/~clayton/courses/ai/projects/wumpus/)

Introduction

Dans ce projet, vous construirez un agent logique basé sur la Logique Propositionnelle (LP0) capable de résoudre une variante du jeu "La Chasse au Wumpus". Cela nécessitera la construction de la base de connaissances de l'agent et l'implémentation des routines de recherche utilisées par l'agent pour la planification de ses actions.

Le code du projet consistera en plusieurs fichiers Python. Il vous faudra lire et comprendre certains de ceux-ci afin de mener à bien le projet, mais vous pourrez en ignorer d'autres.

Vous pouvez télécharger des éléments du code et des fichiers complémentaires à partir de l'archive zip.

Remarque : L'abbréviation AIMA utilisée dans la suite réfère à l'ouvrage Artificial Intelligence: A Modern Approach, 3rd Edition de Stuart Russell et Peter Norvig ainsi qu'au code Python correspondant, disponible sur GitHub (Toutefois, tous les fichiers requis pour le projet sont inclus dans l'archive zip).

Fichiers à compléter et soumettre

`wumpus_kb.py`	Code permettant de générer la base de connaissances de l'agent. Il vous faudra compléter la plupart des fonctions.
`wumpus_planners.py`	Code pour effectuer `plan_route` et `plan_shot`. Il vous faudra compléter le code pour implémenter les problèmes `PlanRouteProblem` et `PlanShotProblem`. Voir `search.py` pour la classe parente `Problem` et des exemples.

Fichiers à consulter :

`wumpus.py`	Le fichier principal pour éxécuter la Chasse au Wumpus. Comprend du code pour générer un `WumpusWorldScenario` qui combine un code `WumpusEnvironment` avec un agent (soit `Explorer` soit `HybridWumpusAgent`). Inclut des programmes agents permettant de conduire la partie "à la main" (avec ou sans base de connaissances). Inclut également une interface en ligne de commande `__main__`.
`wumpus_environment.py`	Implémente les principales classes définissant l'environnement du Wumpus. L'agent `Explorer` est un agent chasseur de Wumpus qui ne dispose pas d'une base de connaissances. Le code `WumpusEnvironment` implémente les aspects physiques et de gameplay de la chasse au Wumpus.
`wumpus_agent.py`	Définit l'agent `HybridWumpusAgent` (qui étend l'agent `Explorer`). Cet agent dispose d'une base de connaissances. Le code `agent_program` implémente une hiérarchie de réflexes qui sont exécutés selon les perceptions et l'état de connaissance de l'agent. Cela inclut des appels à `plan_route` et `plan_shot` que vous implémenterez dans le programme `wumpus_planners.py`.
`logic.py`	Code issu d'AIMA implémentant des aspects de la Logique Propositionnelle (LP0) et de la Logique des Prédicats (LP1) et divers algorithmes d'inférence. Vous devrez vous intéresser à l'implémentation de la LP0. Remarque : fichier légèrement modifié par rapport à la version AIMA.
`search.py`	Code issu d'AIMA implémentant divers outils de recherche ; inclut la classe `Problem` que vous implémenterez dans `wumpus_planners.py` pour `plan_route` et `plan_shot`.

Fichiers pouvant être ignorés :

`minisat.py`	Code pour implémenter l'interface vers CryptoMiniSat, incluant la traduction des clauses LP0 de type AIMA en CNF DIMACS, une interface pour appeler CryptoMiniSat, ainsi que la récupération des résultats de CryptoMiniSat.
`agents.py`	Code issu d'AIMA pour les agents et environnements génériques.
`utils.py`	Code issu d'AIMA fournissant une boîte à outils pour d'autres modules issus de AIMA. Remarque : fichier légèrement modifié par rapport à la version originale.

Ce que vous avez à faire : Installer CryptoMiniSat, compléter les fichiers wumpus_kb.py et wumpus_planners.py. Rédiger un rapport sur le fonctionnement global du programme. Soumettre l'ensemble du code sous forme d'une archive Zip. Inclure dans le rapport un exemple d'exécution.

Obtenir de l'aide : Si vous bloquez sur quelque chose, n'hésitez pas à me contacter par mail.

Terminologie

Dans les commentaires de code et la documentation, j'utilise pour la base de connaissances les termes knowledge base, KB, kb et agent.kb. Il s'agit à chaque fois de la même chose : un outil global de stockage des formules propositionnelles.

J'uilise le terme axiomes pour me référer à des formules soumises à la KB pour permettre la mise à jour de l'état de connaissance de l'agent.

Lorsque des formules de la LP0 sont ajoutées à la KB, elles sont immédiatement converties en forme normale conjonctive FNC (ang. CNF). Cette représentation de type CNF est stockée dans la KB comme une liste des clauses disjonctives la composant (la liste est considérée implicitement comme la conjonction des clauses membres). Les clauses de la liste sont appelées collectivement clauses KB.

Intstallation : Installer CryptoMiniSat, télécharger le code du projet et lancer un test

Ce projet utilise le solveur SAT CryptoMiniSat (https://www.msoos.org/cryptominisat5/). C'est à vous de trouver comment l'installer sur le système que vous utilisez. N'oubliez pas de le mentionner dans votre rapport.

Après avoir installé CryptoMiniSat, téléchargez l'archive Zip du projet (wumpus.zip), décompressez-la et placez-vous dans le répertoire wumpus. Vous pouvez tester la connexion à CryptoMiniSat en exécutant les instructions suivantes en ligne de commande :

python wumpus.py -t

Les trois test devraient bien se passer. Si ce n'est pas le cas, contactez-moi pour obtenir de l'aide.

Bienvenue dans la grotte du Wumpus !

L'étape suivante est de vous familiariser avec le jeu de Chasse au Wumpus. Exécutez l'instruction suivante en ligne de commande pour jouer :

python wumpus.py

Cela lance une interface en ligne de commande interactive, en mode "Manuel" : vous avez le contrôle de l'agent chasseur de Wumpus. En saisissant 'env', vous obtenez une représentation de type ascii-art de l'état courant de l'environnement du Wumpus. Par exemple, lors du premier tick, vous verrez :

     Scores: < Explorer >=0
       0   1   2   3   4   5    time_step=0
     |---|---|---|---|---|---|
     | # | # | # | # | # | # | 5
     |---|---|---|---|---|---|
     | # |   |   |   |   | # | 4
     |---|---|---|---|---|---|
     | # | W | G | P |   | # | 3
     |---|---|---|---|---|---|
     | # |   |   |   |   | # | 2
     |---|---|---|---|---|---|
     | # | ^ |   | P |   | # | 1
     |---|---|---|---|---|---|
     | # | # | # | # | # | # | 0
     |---|---|---|---|---|---|

En haut, le score courant de l'agent chasseur de Wumpus (un < Explorer > dans le mode manuel par défaut). Les coordonnées x de l'environnement du Wumpus sont affichées sur la ligne au-dessus de la grille et les coordonnées y sont affichées à côté de la ligne à droite de la grille. Chaque cellule de la grille représente une salle. '#' représente un mur, et 'W', 'P', et 'G' représentent le Wumpus, un Puit et l'Or (ang. Gold), respectivement. La position de l'agent chasseur de Wumpus est représentée par '^', '>', 'v', et '<', chaque symbole pointant dans la direction vers laquelle l'agent est orienté. Au début, l'agent se trouve à la position (1,1).

Vous pouvez entrer '?' à n'importe quel moment pour voir une liste complète des commandes.

Le but du jeu est d'obtenir le score le plus élevé possible. Chaque mouvement coûte un point, tirer une flèche (indépendamment du fait qu'elle tue le Wumpus ou pas) coute 10 points et quitter la grotte (effectué en exécutant la commande' Climb' à l'endroit d'où l'agent était parti avec l'or (i.e., en ayant auparavant utilisé la commande 'Grab' pour récupérer l'or)), permet d'obtenir 1000 points. Mourir, ce qui a lieu en arrivant dans un carré ou se trouve le Wumpus ou un Puit, coute 1000 points.

A chaque étape de temps (tick), les perceptions courantes sont représentées par une liste de propositions ('~' représente le fait qu'une proposition est Fausse). Par exemple, à l'instant 0 (indiqué entre les crochets à gauche) les perceptions associées à l'environnement précédemment décrit sont :

[0] You perceive: ['~Stench', '~Breeze', '~Glitter', '~Bump','~Scream']

Jouez plusieurs parties afin de voir comment l'environnement du Wumpus détermine les perceptions. Essayez de mourir en vous déplaçant dans le carré du Wumpus ou un Puit. Tirez sur le Wumpus : vous devrez pour cela exécuter 'Shoot' tout en étant orienté face au Wumpus ; lorsque l'opération est couronnée de succès, le Wumpus meurt et à l'étape de temps suivante vous percevrez son cri ('Scream') ; de plus, le Wumpus n'est, après cela, plus représenté par un 'W', mais par un 'X'. Vous pouvez à présent vous déplacer en toute sécurité dans le carré du Wumpus. Résolvez la partie en vous déplaçant sur l'Or, en exécutant 'Grab', puis en revenant à l'entrée/sortie et en exécutant 'Climb'.

Vous pouvez charger différents environnements en spécifiant soit le nom d'un environnement existant dans le répertoire wumpus/layouts/ (deux sont fournis), soit en spécifiant le chemin vers un environnement, en utilisant l'option de ligne de commande :

python wumpus.py -l 'wumpus_4x4_book'

(Vous pouvez, de façon optionnelle, spécifier l'extension '.lay'.) Le format d'une spécification d'environnement est très simple; en voici un exemple :

.,.,.,.
W,G,P,.
.,.,.,.
A,.,P,.

Le format de fichier définit l'environnement du Wumpus comme une série de spécifications des salles, séparées par des virgules, chaque ligne représentant une ligne de salles dans l'environnement du Wumpus. '.' représente une salle vide, 'W' positionne un Wumpus (la base de connaissances que vous créerez ne pourra s'accommoder que de la présence d'un Wumpus exactement, ni plus, ni moins, mais dans le jeu manuel, il peut y avoir plusieurs Wumpi), 'P' positionne un Puit, 'G' positionne l'Or (la base de connaissances ne permettra de prélever qu'un et un seul Or) et 'A' marque la position de l'agent chasseur de Wumpus (l'orientation de l'agent est spécifiée séparément dans le code; Nord, ou '^', est l'orientation par défaut). Vous pouvez également ajouter des murs, representés par '#'. Par défaut, l'environnement spécifié sera automatiquement entouré de murs.

Jetez un coup d'oeil aux commentaires de code et aux exemples inclus dans wumpus.py afin de voir comment construire un WumpusWorldScenario à partir d'un fichier de spécification d'environnement ; vous pouvez également le spécifier directement dans le code en construisant des objets et en les affectant à des positions dans l'environnement du Wumpus.

Commentaires généraux à propos de la structure du code et des options de ligne de commande

Deux classes principales réalisent ensemble une version fonctionnelle du jeu : la classe WumpusEnvironment et une instance d'un agent sont combinées dans une classe WumpusWorldScenario, définie dans wumpus.py.

Le WumpusEnvironment, défini dans wumpus_environment.py, représente l'environnement de la grotte du Wumpus, la position et l'état de tous les objets et définit les règles du jeu (la 'physique' du jeu), comme les effets des actions de l'agent. La méthode step() fait avancer le jeu d'une étape de temps et inclut un appel au programme agent_program de l'agent chasseur de Wumpus.
Deux classes sont utilisées pour définir les agents chasseurs de Wumpus. La classe Explorer, également définie dans wumpus_environment.py, fournit un squelette d'agent minimal, alors que la classe HybridWumpusAgent, définie dans wumpus_agent.py, est une implémentation complète d'un agent et inclut une base de connaissances et un ensemble de réflexes suffisants pour résoudre n'importe quelle partie de Chasse au Wumpus (une fois que vous aurez complété le code).

La principale action d'un agent chasseur de Wumpus a lieu dans le programme agent_program. Trois différents programmes agent_program sont fournis :

La fonction with_manual_program (dans wumpus.py) prend un agent comme entrée et remplace son agent_program avec un agent_program "manuel" dans lequel l'agent attend des commandes de ligne de commande à chaque étape. C'est l'agent qui est exécuté lorsqu'on lance le jeu à partir de la ligne de commande (avec ou sans l'option '-l' de fichier de spécification d'environnement):
```
python wumpus.py
```
Cette version est très utile pour jouer au jeu et vérifier que vous comprenez la "physique" de l'environnement du Wumpus (i.e., les effets des actions sur les états du monde et les perceptions subséquentes).
La fonction- with_manual_kb_program (également dans wumpus.py) fonctionne de façon similaire à with_manual_program excepté que l'agent crée une base de connaissance et que le programme agent_program met à jour la base de connaissances avec les perceptions et les actions sélectionnées (par le joueur humain) à chaque étape. L'utilisateur peut également soumettre n'importe quelle requête pertinente à propos des propositions de la base de connaissances. Cette option est très utile pour développer et déboguer les axiomes que vous fournissez pour initialiser et mettre à jour la base de connaissances. Cette version du programme agent peut être lancée en exécutant la commande suivante à partir de la ligne de commande (dans le répertoire wumpus/) :
```
python wumpus.py -k
```
(Vous pouvez également combiner cela avec l'option '-l' pour charger une spécification d'environnement particulière.) Une fois le programme lancé, saisir '?' pour obtenir la liste des commandes et la liste complète des types de requêtes disponibles.
La classe HybridWumpusAgent (HWA) est définie dans wumpus_agent.py (c'est une sous-classe de la classe Explorer). La classe HWA définit un programme agent_program qui implémente l'agent chasseur de Wumpus comme décrit dans la figure ci-dessous, issue de AIMA, page 270.

Une fois que vous aurez correctement implémenté les générateurs d'axiomes de la base de connaissances (dans wumpus_kb.py) et les classes PlanRouteProblem et PlanShotProblem (dans wumpus_planners.py), le programme agent_program de la classe HWA pourra résoudre toute instance résolvable du jeu de la Chasse au Wumpus. La classe HWA et son programme agent_program peuvent être exécutés en ligne de commande (dans le répertoire wumpus/) en faisant :
```
python wumpus.py -y
```
(Ceci peut être combiné avec l'option '-l' ; toutefois, l'option '-y' écrasera l'option '-k' si elle est incluse). Lorsqu'il est exécuté, le programme agent agent_program de la classe HWA sélectionne toutes les actions ; l'utilisateur humain n'à rien à faire, juste à regarder. Comme pour les options précédentes, les sorties affichées sont très détaillées, de façon à pouvoir suivre l'exécution du programme étape par étape.

Afin d'avoir une idée du comportement "correct", les sorties de deux exécutions de la classe HWA complète sont fournies, pour deux spécifications d'environnement : HWA_lay_book_run.txt et HWA_lay_2_run.txt.

Notez que le nombre de clauses dans la KB augmente au fur et à mesure que l'agent agit dans l'environnement. On peut s'y attendre : à chaque étape de temps, de nouveaux axiomes sont ajoutés à la base de connaissances pour représenter les changements intervenus (en se basant sur les perceptions et les actions). C'est vous qui implémenterez les générateurs d'axiomes correspondants.
Remarque : Bien qu'il vous soit possible de construire des spécifications d'environnement (que ce soit dans un fichier ou dans du code) de n'importe quelles dimensions, il est recommandé de respecter les contraintes suivantes (essentiellement en raison de l'utilisation d'une base de connaissances ; pour une partie manuelle sans KB, il n'y pas de contraintes) :
- Ne pas créer d'environnement contenant moins de deux salles, car la base de connaissances suppose qu'il y a un et un seul Wumpus, donc une grotte à une seule salle mettrait nécessairement le Wumpus à l'entrée, ce qui conduirait à une contradiction.
- Ne pas créer d'environnement contenant plus de 16 salles, car alors la KB augmente de taille trop rapidement et cela bogue au niveau de l'inférence.
Logique Propositionnelle en Python

Les deux programmes agents avec lesquels vous travaillerez (se trouvant dans with_manual_kb_program, dans wumpus.py, ou dans la classe HybridWumpusAgent (HWA) définie dans wumpus_agent.py) utilisent la base de connaissances PropKB_SAT. Celle-ci est définie dans wumpus_agent.py et elle est une sous-classe de la classe PropKB définie dans logic.py. Ces classes sont en fait très simples, implémentant la méthode tell() pour ajouter de nouveaux énoncés à la base de connaissances, et la méthode ask() pour requêter la base de connaissances (ask() est une interface vers CryptoMiniSat). Les assertions introduites dans la base de connaissance (sous la forme de chaînes de caractères) sont stockées dans le champ clauses de la KB, et il s'agit juste d'une liste Python ! Les représentations des assertions elles-mêmes sont construites en se basant sur l'implémentation de la logique propositionnelle telle qu'elle est effectuée dans AIMA. Comme vous implémenterez des générateurs d'axiomes, il est important de comprendre comment des énoncés propositionnels, initialement exprimés sous la forme de chaînes de caractères, sont convertis en représentations dans la LP0. Vous pouvez jeter un coup d'oeil dans logic.py. En particulier, l'extrait suivant de l'invite Python illustre quelques fonctionnalités de base.
```
In [1]: import logic

In [2]: a = '(A & B) >> ( ~(C | D) <=> E )'

In [3]: e = logic.expr(a)

In [4]: e
Out[4]: ((A & B) >> (~(C | D) <=> E))

In [5]: c = logic.to_cnf(e)

In [6]: c
Out[6]: ((~C | ~E | ~A | ~B) & (~D | ~E | ~A | ~B) & (E | C | D | ~A | ~B))

In [7]: logic.conjuncts(c)
Out[7]: [(~C | ~E | ~A | ~B), (~D | ~E | ~A | ~B), (E | C | D | ~A | ~B)]
```
La ligne 2 exprime un énoncé propositionnel sous la forme d'une chaîne de caractères, avec la syntaxe issue de AIMA. Voir la classe Expr dans logic.py. La fonction expr() analyse cette chaîne de caractères et construit une Expr. L'objet Expr est conçu pour avoir une représentation Python "agréable", tel qu'illustré à la ligne 4 (ceci est réalisé par la définition de la méthode __repr__() dans Expr ; voir cette explication). Mais gardez présent à l'esprit qu'il s'agit d'un objet ! Il a deux champs principaux : l'opérateur, op, et la liste des arguments de l'opérateur, args. Comme la variable e référence l'Expr, nous pouvons examiner op et args de la façon suivante :
```
In [10]: e.op
Out[10]: '>>'

In [11]: e.args
Out[11]: [(A & B), (~(C | D) <=> E)]
```
Ceci montre que l'Expr à laquelle e réfère a pour opérateur le symbole conditionnel, et que ses args ont deux entrées, la première étant l'antécédent, dans ce cas A & B, et le deuxième le conséquent, ~(C | D) <=> E. Chacun d'eux est également une Expr, la première ayant l'opérateur de conjonction, '&', avec deux args A et B. Ainsi, notre Expr initiale, à laquelle réfère e, est en fait la racine d'un arbre d'Expr, ce qui permet de représenter des énoncés arbitrairement complexes.

Assurez-vous de consulter la documentation de Expr et expr() dans logic.py afin de comprendre comment la syntaxe en LP0 sera générée à partir d'une chaîne de caractères, en particulier la remarque dans la documentation d'expr() à propos de l'ordre de priorité des opérateurs : expr('P & Q ==> R & S') est analysée en ((P & (Q >> R)) & S), ce qui n'est peut-être pas ce qui était prévu ! Afin que l'ordre de priorité attendu soit respecté (i.e., & prioritaire sur ==>), vous devez utiliser expr('(P & Q) ==> (R & S)'). En général, il est conseillé d'utiliser des parenthèses pour faire respecter la priorité que vous attendez.

Revenons à l'exemple initial. La ligne 5 convertit l'énoncé complet dans la LP0 en forme normale conjonctive en utilisant la fonction to_cnf() ; La ligne 6 montre le résultat. Il s'agit encore d'un objet Expr ; de plus, il est logiquement équivalent à la forme apparaissant dans les lignes 2 et 4. Chaque fois qu'une Expr est ajoutée à la KB à l'aide d'un tell(), l'Expr est convertie en CNF. Ensuite, les conjoints de la CNF sont obtenus ; ce qui est stocké dans le store clauses de la KB est une liste des clauses individuelles composant la CNF. C'est illustré à la ligne 7.

Finalement, une remarque à propos de l'utilisation de CryptoMiniSat. CryptoMiniSat est un solveur SAT, ce qui signifie qu'il cherche un modèle pour un ensemble de clauses CNF, renvoie True si un tel modèle est trouvé ou False si aucun modèle n'est trouvé. C'est très utile mais insuffisant pour faire de l'inférence propositionnelle. Dans notre cas, nous ne ferons pas de l'inférence complète mais nous demanderons simplement au solveur si des propositions données sont des conséquences logiques (True) ou non (False) de la base de connaissances ou s'il est impossible de répondre. Afin de déterminer dans lequel de ces trois cas on se trouve, la méthode ask() de PropKB_SAT effectue deux appels à CryptoMiniSat, un dans lequel la variable de requête (la proposition dont on essaie de déterminer la véracité) est supposée True, et un dans lequel elle est supposée False, et dans chacun des cas, CryptoMiniSat détermine si l'assertion postulée est satisfaisable avec l'ensemble des clauses de la KB. Si l'ensemble clauses + requête est satisfaisable dans les deux cas, alors cela signifie que la KB ne permet pas de déterminer si la proposition est True ou False. D'autre part, si un appel à CryptoMiniSat est satisfaisable, mais l'autre non, alors la valeur de vérité de la proposition est celle pour laquelle l'appel est satisfaisable. Il est important de comprendre comment ça marche.

Construire la Base de Connaissances

OK, il est temps de se mettre au travail ! Les premières tâches à effectuer consistent à implémenter les générateurs d'axiomes pour la base de connaissances. Pour cette partie du projet, vous travaillerez dans wumpus_kb.py, en rajoutant votre code à tous les endroits indiqués par "*** YOUR CODE HERE ***". Vous remarquerez que les noms de toutes les méthodes que vous implémenterez commencent par "axiom_generator_...". Les chaînes doc de ces fonctions décrivent les connaissance à énoncer en LP0, avec une explication de ce que représentent les arguments de la fonction. Les valeurs retournées doivent être des chaînes de caractères représentant les assertions dans la LP0.

Les extraits suivant des sections 7.2, 7.4 et 7.7 de AIMA sont un bon guide pour certains axiomes que vous aurez à implémenter. Mais attention, il y en a d'autres !

En plus du générateur d'assertions de perceptions courantes (qui convertit les vecteurs de perceptions en énoncés propositionnels sur les perceptions), il y aura deux classes générales de générateurs d'axiomes à construire : un ensemble qui génère les axiomes décrivant l'état de connaissance initial et un ensemble qui génère des axiomes qui représentent les changements intervenant au fil du temps.

Les assertions faites par vos générateurs seront construites à partir de propositions. La première section de wumpus_kb.py définit toutes les propositions qui apparaitront dans la KB. Comme il est très facile d'ajouter un symbole propositionnel mal formé à la KB sans le savoir, des fonctions constructeurs de chaînes de caractères propositionnelles, une pour chaque type de proposition, sont fournies.

Vous travaillerez beaucoup avec les chaînes de caractères dans cette partie du projet. Voici quelques fonctions Python sur les chaînes qui pourront vous être utiles :
- Le signe plus est surchargé : 'a' + 'b' donne 'ab'
- Le méthode join est très pratique ; la chaîne sur laquelle est appelé le join sera insérée entre les chaînes listées dans celui-ci (utiliser une chaîne vide pour simplement concaténer la liste de chaînes) :
  - ''.join(['a','b','c']) donne 'abc'
  - '-'.join(['a','b','c']) donne 'a-b-c'
- La méthode format vous sera utile : 'string with {0}{1}'.format('stu', 'ff')
  donne 'string with stuff'
En termes de notation, les point seront alloués, pour une implémentation correcte, de la façon suivante (pour un total de 24 points):
- axiom_generator_percept_sentence = 1 pt
- axiom_generator_initial_location_assertions = 0.5 pt
- axiom_generator_pits_and_breezes = 1 pt
- axiom_generator_wumpus_and_stench = 1 pt
- axiom_generator_at_least_one_wumpus = 1 pt
- axiom_generator_at_most_one_wumpus = 1 pt
- axiom_generator_only_in_one_location = 1 pt
- axiom_generator_only_one_heading = 1 pt
- axiom_generator_have_arrow_and_wumpus_alive = 0.5 pt
- axiom_generator_location_OK = 1 pt
- axiom_generator_breeze_percept_and_location_property = 1 pt
- axiom_generator_stench_percept_and_location_property = 1 pt
- axiom_generator_at_location_ssa = 4 pts
- axiom_generator_have_arrow_ssa = 1 pt
- axiom_generator_wumpus_alive_ssa = 1 pt
- axiom_generator_heading_{north,east,south,west}_ssa = 3 pts (pour l'ensemble)
- axiom_generator_heading_only_{north,east,south,west} = 2 pts (pour l'ensemble)
- axiom_generator_only_one_action_axioms = 2 pts
Remarque : Pendant que vous construisez les générateurs d'axiomes de la base de connaissances, celle-ci doit rester satisfaisable. Si elle devient insat, cela signifie que quelque chose que vous avez ajouté conduit à une contradiction. Afin de vérifier la satisfaisabilité de la KB, appelez la fonction minisat() dans wumpus_agent.py sur les clauses KB, en faisant par exemple minisat(kb.clauses); lorsque vous exécutez wumpus.py avec une KB (option -k) à partir de la ligne de commande, vous pouvez saisir la commande 'kbsat' pour faire de même . Notez toutefois que le fait que la KB soit satisfaisable ne signifie pas qu'il n'y a pas d'autres problèmes.

Implémentation du plan de route et de tir

La deuxième tâche importante du projet est de compléter l'implémentation du plan de route et de tir pour l'agent chasseur de Wumpus hybride. Votre code prendra place dans wumpus_planners.py. La documentation pour plan_route et plan_shot décrivent le problème, mais le code à compléter sera dans les classes PlanRouteProblem et PlanShotProblem, qui étendent toutes deux la classe Problem (definie dans search.py) qui sert d'interface au programme de recherche d'AIMA.
Le goal_test pour les deux problèmes renvoie initialement toujours True, et plan_route et plan_shot renvoient des listes d'actions vides si aucune solution n'est trouvée. Cela vous permet d'exécuter l'agent chasseur de Wumpus hybride complet avant que les outils de planification soient implémentés, mais vous aurez bien évidemment à modifier cela.

Une fois implémentées, plan_route et plan_shot utiliseront l'implémentation AIMA de l'algorithme A*, qui est définie dans search.py (comme astar_search()).

Il est recommandé d'implémenter la classe PlanRouteProblem d'abord, car une grande partie de celle-ci pourra être réutilisée pour PlanShotProblem. Pour PlanShotProblem, vous avez uniquement à planifier un chemin vers la position la plus proche dans laquelle vous serez face au Wumpus.

Comme noté dans plan_route et plan_shot, la représentation d'un état est un triplet représentant les coordonnées x, y et l'orientation de l'agent. L'orientation est un entier parmi 0, 1, 2, ou 3, représentant le Nord, l'Ouest, le Sud et l'Est respectivement. Les buts et les états autorisés, toutefois, ne prennent pas en compte l'orientation et sont ainsi juste des listes de tuples x,y. La fonction manhattan_distance_with_heading() est fournie ; comme son nom l'indique, elle calcule la distance de Manhattan en prenant en compte le coût lié au changement d'orientation (pour s'orienter correctement) avant de suivre le chemin de Manhattan.

L'implémentation correcte de chaque problème de recherche vaut 4 points chacune, pour un total de 8 points.

Votre note globale (sur 40) vous sera communiquée. En termes d'évaluation de l'UE sur 20, votre note finale sera obtenue en divisant par deux la note sur 40 puis en combinant le résultat avec la note de TP Prolog.
Bon travail !