Dans le cadre de ce module, a été réalisé en JAVA, de début Mars à fin Juin, un projet par groupe de 3 personnes (les 2 autres étant Gauthier HADERER et Eric BOULAT).Il s'agissait de résoudre le célèbre problème du "monde du Wumpus". Un agent est enfermé dans un labyrinthe. Dans ce labyrinthe, il y a des pièges (les puits), un monstre (le Wumpus) et un trésor (l'or). L'agent doit éviter les puits et le Wumpus. Il dispose d'une flèche qu'il peut tirer dans une salle voisine afin de tuer le Wumpus. L'agent sent les dangers quand il se trouve sur une salle voisine de la salle où il y a le danger (un courant d'air pour un puits, ou une puanteur pour le Wumpus), mais il ne sent ni l'intensité, ni la direction. Forts de tout ce que nous avons appris sur les graphes, nous sommes le seul groupe qui achoisi de poser et résoudre le problème sur des graphes (et non pas sur de simples cadrillages représentés par des matrices comme les autres). Les graphes ont été représentés en mémoire par des listes d'adjacence. La seule contrainte, est qu'il n'y ait pas de piège sur la case de départ, et que le graphe soit connexe (on peut aller partout).

Eric BOULAT s'est occupé de trouver une représentation simple pour les graphes connexes quelconques (on répartit les sommets équitablement sur un cercle et on les relie). Voici d'ailleurs unexemple:

Gauthier HADERER s'est occupé de la classe de base fournissant l'interfaçage entre les agents et les environnements.
Quant à moi, je me suis passionné pour les algorithmes et j'ai donc vraiment fait de l'IA.

J'ai réalisé 8 types d'agents (qui deviennent progressivement de plus en plus intelligents).

• Les agents 1 et 2 se déplacent complètement au hasard et le 2 recule en cas de danger.
• A partir de l'agent 3, une fois que l'agent a trouvé l'or, il dispose d'une stratégie pour revenir (par le plus court chemin à partir de l'agent 4).
• A partir de l'agent 4, les agents choisissent dans quelle salle aller parmi les salles voisines (par exemple: "aller dans une salle non visitée").
• Les agents 6 et 7 font des déductions locales (le 7 en plus du 6 sait qu'il n'y a qu'1 seul or et 1 seul Wumpus).
• Quant à l'agent 8, il reprend les règles de l'agent 7, mais fait une déduction globale et son déplacement est aussi global: "le plus court chemin sûr vers une salle non visitée". L'agent 8 a lui été réalisé grâce à une interface PROLOG pour JAVA. (en effet, réimplémenter la méthode de résolution en JAVA aurait été pénible vu le peu de temps dont nous disposions).

Voici d'ailleurs le graphes du nombre d'actions mis par les agents pourtrouver la solution en fonction de la taille du graphe (moyenne calculée pour 10 essais par agent et par graphe).

• Comme c'était prévisible, les premiers agents ont une croissance exponentielle.
• A partir de l'agent 6, on commence à faire des déductions et un observe un pic à l'origine. Celà s'explique par le fait que sur un petit graphe il faut plus d'infos pour pouvoir déduire quelque chose par les règles que j'ai choisies.
• L'agent 7, lui a des performances très remarquables (en bleu-vert). Sa croissance est linéaire, de pente très faible (pour un graphe de 1000 sommets, il met en moyenne seulement 100 coups pour trouver la solution).
• L'agent 8 (en bleu azur) lui est censé être meilleur que l'agent 7. Néanmoins, réfléchir sur tout le graphe prend beaucoup de temps, et donc nous nous sommes limités àdes petits graphes.

Le meilleur agent est donc l'agent 7, dont le temps d'exécution est très rapide.

Comme nous avons pris des graphes, ce projet est général et peut s'adapter à diverses mondes (mondes en 2 dimensions, éventuellement avec des passages secrets entre des salles éloignées (monde en 2 dimensions généralisé) comme dans Chip's Challenge; ou en 3 dimensions comme dans Doom, ou 3 dimensions généralisées (comme dans Hexen)).