Intelligence Artificielle AI - Prolog : PROLOG & IA Bases de l’Intelligence Artificielle
Télécharger PDFBases de l’Intelligence Artificielle avec Prolog
Introduction
Ce cours couvre les fondements de l’intelligence artificielle (IA) à travers le langage Prolog. Les thèmes abordés incluent les débuts de l’IA, la résolution par satisfaction de contraintes (CSP), la recherche dans un graphe d’états, la décomposition de problèmes et les systèmes à base de connaissances.
Les débuts de l’IA avec Eliza
Eliza est un exemple classique des débuts de l’IA. Ce programme ne repose pas sur une intelligence artificielle réelle mais simule une conversation avec un psychologue en utilisant des techniques simples.
Exemple de dialogue avec Eliza
L’utilisateur peut interagir avec Eliza de la manière suivante :
Bonjour. Qu’est-ce qui vous amène ?
— "Je suis triste"
Depuis combien de temps êtes-vous triste ?
— "Depuis le départ de mon frère"
Pouvez-vous me parler de votre frère ?
— "J’aime discuter avec lui"
Quelqu’un d’autre dans votre famille aime-t-il cela ?
— "Non"
Continuez.
— "Je me sens seule maintenant"
Ressentez-vous souvent cela ?
— "Oui, depuis que mon frère est parti !"
Pouvez-vous me parler de votre frère ?
— "Vous vous moquez de moi ?"
Continuez.
— "Bye"
Principe du programme Eliza
Eliza fonctionne selon le principe de l’appariement stimulus-réaction. Voici ses étapes clés :
- Lire l’entrée de l’utilisateur.
- Tant que l’entrée n’est pas "bye", choisir une paire stimulus-réaction.
- Apparier l’entrée avec le stimulus.
- Générer la réponse à partir de la réaction et de l’appariement.
- Afficher la réponse.
- Lire l’entrée suivante.
Le programme améliore ses réponses en détectant des mots-clés comme "père", "mère" ou "frère".
Résolution par Satisfaction de Contraintes (CSP)
Le CSP (Constraint Satisfaction Problem) est une méthode pour résoudre des problèmes en définissant un ensemble de variables, leurs domaines possibles et des contraintes entre elles.
- X : Ensemble des variables caractérisant le problème (par exemple, X = {X1, X2, ..., Xn}).
- D(Xi) : Domaine de chaque variable Xi, c’est-à-dire l’ensemble des valeurs que Xi peut théoriquement prendre.
- C : Ensemble des contraintes (C = {C1, C2, ..., Ck}), où chaque contrainte Cj est une relation entre certaines variables de X limitant les valeurs possibles simultanément.
Problème des N-Reines
L’objectif est de placer N reines sur un échiquier de taille N x N de telle sorte qu’aucune reine ne puisse en attaquer une autre. Cela signifie qu’aucune paire de reines ne peut partager la même ligne, colonne ou diagonale.
Première modélisation du problème des 4 reines
Les variables sont définies comme suit :
- X = {L1, L2, L3, L4, C1, C2, C3, C4}, où Li est la ligne de la reine i et Ci sa colonne.
- Les domaines de valeurs sont : D(L1) = D(L2) = D(L3) = D(L4) = D(C1) = D(C2) = D(C3) = D(C4) = {1, 2, 3, 4}.
Les contraintes incluent :
- Clig : Les reines doivent être sur des lignes différentes (L1 ≠ L2, L1 ≠ L3, etc.).
- Ccol : Les reines doivent être sur des colonnes différentes (C1 ≠ C2, C1 ≠ C3, etc.).
- Cdm : Les reines doivent être sur des diagonales montantes différentes (C1 + L1 ≠ C2 + L2, etc.).
- Cdd : Les reines doivent être sur des diagonales descendantes différentes (C1 - L1 ≠ C2 - L2, etc.).
L’ensemble des contraintes est défini par C = Clig ∪ Ccol ∪ Cdm ∪ Cdd.
Résultats pour le problème des 4 reines
Voici quelques solutions possibles :
- R = [1, 2, 3, 4, 2, 4, 1, 3]
- R = [1, 2, 3, 4, 3, 1, 4, 2]
- R = [1, 2, 4, 3, 2, 4, 3, 1]
- R = [1, 3, 2, 4, 2, 1, 4, 3]
- R = [1, 3, 4, 2, 3, 4, 2, 1]
- R = [1, 4, 2, 3, 3, 2, 4, 1]
- R = [2, 1, 3, 4, 1, 3, 4, 2]
- R = [2, 3, 1, 4, 4, 1, 2, 3]
- R = [3, 1, 4, 2, 4, 3, 2, 1]
- R = [4, 1, 3, 2, 3, 2, 1, 4]
Deuxième modélisation du problème des 4 reines
Cette approche simplifie le problème en fixant la colonne de chaque reine et en ne considérant que les lignes :
- X = {L1, L2, L3, L4}, où Li est la ligne de la reine i (sa colonne est fixée).
- Les domaines de valeurs sont : D(L1) = D(L2) = D(L3) = D(L4) = {1, 2, 3, 4}.
Les contraintes deviennent :
- Clig : Les reines doivent être sur des lignes différentes (Li ≠ Lj).
- Cdm : Les reines doivent être sur des diagonales montantes différentes (Li + i ≠ Lj + j).
- Cdd : Les reines doivent être sur des diagonales descendantes différentes (Li - i ≠ Lj - j).
L’ensemble des contraintes est défini par C = Clig ∪ Cdm ∪ Cdd.
Troisième modélisation du problème des 4 reines
Cette approche utilise les états des 16 cases de l’échiquier :
- X = {X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44}, où Xij représente l’état de la case à la ligne i et colonne j.
- Les domaines de valeurs sont : D(Xij) = {0, 1}, où 0 signifie qu’il n’y a pas de reine et 1 qu’il y en a une.
Les contraintes incluent :
- Clig : Une seule reine par ligne (Xi1 + Xi2 + Xi3 + Xi4 = 1).
- Ccol : Une seule reine par colonne (X1i + X2i + X3i + X4i = 1).
- Cdm : Pas deux reines sur la même diagonale montante (Xij + Xkl ≤ 1 si i + j = k + l).
- Cdd : Pas deux reines sur la même diagonale descendante (Xij + Xkl ≤ 1 si i - j = k - l).
L’ensemble des contraintes est défini par C = Clig ∪ Ccol ∪ Cdm ∪ Cdd.
Généralisation du problème des N-Reines
Pour un problème avec N reines, la deuxième modélisation devient :
- Variables : L = {Li / i est un entier compris entre 1 et n}.
- Domaines : Pour chaque Li, D(Li) = {j / j est un entier compris entre 1 et n}.
Les contraintes sont :
- Clig : Li ≠ Lj pour i et j différents.
- Cdm : Li + i ≠ Lj + j pour i et j différents.
- Cdd : Li - i ≠ Lj - j pour i et j différents.
L’ensemble des contraintes est défini par C = Clig ∪ Cdm ∪ Cdd.
Généralisation des prédicats CSP
Pour résoudre des problèmes CSP de manière générique, il faut définir des prédicats spécifiques :
- domaines(L) : Génère la liste des couples [Variable, Domaine].
- consistants(Affectation1, Affectation2) : Vérifie si deux affectations sont compatibles.
Recherche dans un graphe d’états
Cette méthode consiste à modéliser un problème comme un graphe d’états, où chaque état est un nœud et les transitions entre états sont des arêtes. Voici les éléments clés :
- Un ou plusieurs états initiaux.
- Un ou plusieurs états finaux.
- Des états interdits (optionnels).
- Des opérateurs de transition.
Un algorithme général permet de rechercher une solution dans ce graphe.
Exemple : Problème de labyrinthe
Un labyrinthe peut être modélisé comme un graphe d’états où chaque salle est un nœud et les portes entre salles sont des arêtes. Par exemple :
- Salle Thésée (entrée).
- Salle Minotaure.
- Salle Sombre.
- Salle Claire (sortie).
- Salle Ariane.
Les Tours de Hanoi
Les Tours de Hanoi illustrent la décomposition d’un problème en sous-problèmes. L’objectif est de déplacer un ensemble de disques d’une tour à une autre en respectant certaines règles.
FAQ
Qu’est-ce que le principe de l’appariement stimulus-réaction utilisé par Eliza ?
L’appariement stimulus-réaction est une technique où le programme associe une entrée utilisateur (stimulus) à une réponse prédéfinie (réaction) pour simuler une conversation.
Quelles sont les principales contraintes du problème des N-Reines ?
Les contraintes principales sont : aucune reine ne peut partager la même ligne, colonne ou diagonale avec une autre reine.
Comment modéliser un problème comme un graphe d’états ?
Il faut définir les états initiaux et finaux, les états interdits (si nécessaire), et les opérateurs qui permettent de passer d’un état à un autre.