I4IRSD11 - Intelligence Artificielle - Méthodes de résolution de problèmes
Aperçu des sections
-
Objectifs
Ce cours a pour objectif de maîtriser les algorithmes de résolution de problèmes basés sur un recherche arborescente avec heuristique :
- algorithme A* pour la recherche heuristique dans les graphes d'état
- algorithme MinMax et alpha-beta dans les arbres de jeux avec adversaires
- algorithme A0* pour les graphes ET/OU et hyper-graphes de sous-problèmes
Pré-requis : les travaux pratiques s'appuient sur le langage Prolog (langage utilisé pour l'UF Informatique Fondamentale / Logique et Programmation Logique).
Volumes horaires
CM : 8,75h
TP : 11h (4 x 2,75h)
Responsable de l'UEPatrick Esquirol : esquirol@insa-toulouse.fr
Trombinoscope...Composition des groupes de TP....Feuille de notes ...
-
Les notes de cours version 2023
Un problème pour l'algo alphabeta résolu en cours le 06/02/2023.
Une animation pour l'algorithme alpha-beta (convention minmax)
Une applet Java pour alpha-beta
Une animation pour l'algorithme AO*
Un problème AO* résolu en cours 2022
new : les notes de la dernière partie sur l'algorithme MCTS (31 février 2022) et l'animation pdf illustrative pour démarrer l'algo
Références
- Algorithmes de planification d'actions : un livre téléchargeable ici
-
Sujet n°1 : Algorithme A* - Taquin
Fichiers à télécharger et compléter : taquin.pl (description du problème), aetoile.pl (solveur)
Fichier à télécharger : avl.pl (arbres binaires de recherche équilibrés)nouveau : jeux de tests (etats de taquin 3x3 et 4x4 pour tester A*) : data_taquin.txt
Sujet n°2 : Negamax - TicTacToe
Fichiers à télécharger :
tictactoe.pl (description du jeu)
negamax.pl (algorithme negamax)COMPTE-RENDUS
Ils interviennent pour 1/3 de votre note dans cette UFVous pouvez n'envoyer qu'un seul document (formats acceptés : pdf, doc, odt) pour les 2 sujets de TP (aetoile et negamax).
Le compte-rendu doit inclure :
- les réponses aux questions posées dans chaque sujet,
- le code source (avec des commentaires pertinents si possible aux endroit les plus intéressants), éventuellement une copie des tests unitaires effectués
- les temps de réponse du programme pour différents problèmes de difficulté variée
- les limitations du programme (peut-on facilement réutiliser le code pour d'autres problèmes ?)
- les extensions réalisées ou entrevues
Envoyez votre compte-rendu au plus tard le 17 mars 2023 à l'enseignant qui a encadré les séances de votre groupe de TP :
groupe IR_A1: Arthur Bit-Monnot <arthur.bit-monnot@insa-toulouse.fr>
groupe IR_A2 : Pierre Coupechoux <pierre.coupechoux@laposte.net>
groupes IR_B1 et IR_C1 : Patrick Esquirol <esquirol@insa-toulouse.fr>
groupe IR_B2 : Olivier de Mouzon <olivier.de_mouzon@inra.fr>
-
Les 3 dernières annales
- Le sujet 2021-2022 session 1
- Une correction
- Le sujet 2022-2023 session1
- Une correction
- Le sujet 2023-2024 session 1
- Une correction
- Une animation pour l'exercice 2 (A*)
- La feuille de notes anonymisée (à venir)
- Le sujet 2021-2022 session 1
