Intelligence Artificielle AI - Prolog : PROLOG & IA Bases de l’Intelligence Artificielle
Télécharger PDFObtenir le pack complet des cours, TDs, TPs et projets sur intelligence artificielle!
Vous souhaitez maîtriser l'intelligence artificielle ? Ne cherchez plus, nous avons le pack parfait pour vous.
Accédez à une collection complète des supports de cours, des travaux dirigés (TD) corrigés, des travaux pratiques (TP) et des projets.
Obtenir le pack maintenantBases de l’Intelligence Artificielle PROLOG & IA
Marie Lefevre
2020-2021
Université Claude Bernard Lyon 1
De quoi va-t-on parler ?
•Les débuts •Avec Eliza
•Résolution par satisfaction de contraintes (CSP) •Avec les N-Reines
•Recherche dans un graphe d’états •Avec le labyrinthe
•Décomposition de problèmes •Avec les Tours de Hanoi
•Système à base de connaissances en TP...
BIA 2020 : Prolog & IA2 Les débuts avec Eliza
•Classique des débuts de l’IA
•N’u2lise absolument pas d’IA
•Est censé simuler une conversa2on avec un psychologue
BIA 2020 : Prolog & IA3 Dialogue avec Eliza
?-eliza.
Bonjour. Quest ce qui vous amene?
|: "je suis triste".
depuis combien de temps etesvous triste ? |: "depuis le departde mon frere".
pouvez vous me parler de votre frere? |: "j aime discuter avec lui".
quelquun d autre dans votre famille aime til cela ? |: "non".
continuez |: "je me sens seule maintenant".
ressentez vous souvent cela ? |: "oui, depuis que mon frereest parti !".
pouvez vous me parler de votre frere? |: "vous vous moquez de moi ?".
continuez |: "bye".
BIA 2020 : Prolog & IA4 Eliza : principe du programme
•Principe du «S-mulus –Réac-on»
•«bonjour / bienvenu»
•«je suis X / depuis combien de temps êtes vous X ?»
•Lire l’entrée de l’u-lisateur
•Tant que l’entrée n’est pas «bye»
•Choisir une paire «s:mulus-réac:on»
•Apparier l’entrée avec le s:mulus
•Générer la réponse à par:r de la réac:on et de l’appariement
•Afficher la réponse
•Lire l’entrée suivante
•Améliora-on avec des mots-clés à détecter
•pere, mere, frere....
BIA 2020 : Prolog & IA5 De quoi va-t-on parler ?
•Les débuts •Avec Eliza
•Résolution par satisfaction de contraintes (CSP) •Avec les N-Reines
•Recherche dans un graphe d’états •Avec le labyrinthe
•Décomposition de problèmes •Avec les Tours de Hanoi
•Système à base de connaissances en TP...
BIA 2020 : Prolog & IA6 CSP
•X = X1 , X2 , ..., Xn l’ensemble des variables caractérisant le problème•D(X i
) le domaine de chaque variable Xi = l’ensemble des valeurs que Xi peut prendre théoriquement
•C = C1 , C2 , ..., Ck l’ensemble des contraintes
•Chaque contrainte Cj est une rela:on entre certaines variables de X restreignant les valeurs que peuvent prendre simultanément ces variables
BIA 2020 : Prolog & IA7 Problème des N reines
Placer N reines sur un échiquier (une grille N x N)
tel qu’aucune reine attaque une autre reine
c’est-à-dire qu’il n’y a pas deux reines sur la même colonne,
la même ligne, ou sur la même diagonale
BIA 2020 : Prolog & IA8 4 reines : 1ère modélisation
•Les variables
•Associer à chaque reine i deux variables Li (sa ligne) et Ci (sa colonne)
•X = {L1, L2, L3, L4, C1, C2, C3, C4}
•Les domaines de valeurs
•D(L1) = D(L2) = D(L3) = D(L4) = D(C1) = D(C2) = D(C3) = D(C4) = {1,2,3,4}
•Les contraintes :
•Les reines doivent être sur des lignes différentes. •Clig= {L1≠L2, L1≠L3, L1≠L4, L2≠L3, L2≠L4, L3≠L4 }
•Les reines doivent être sur des colonnes différentes. •Ccol= {C1≠C2, C1≠C3, C1≠C4, C2≠C3, C2≠C4, C3≠C4 }
•Les reines doivent être sur des diagonales montantes différentes.
•Cdm= {C1+L1≠C2+L2, C1+L1≠C3+L3, C1+L1≠C4+L4, C2+L2≠C3+L3, C2+L2≠C4+L4, C3+L3≠C4+L4}
•Les reines doivent être sur des diagonales descendantes différentes. •Cdd = {C1-L1≠C2-L2, C1-L1≠C3-L3, C1-L1≠C4-L4, C2-L2≠C3-L3, C2-L2≠C4-L4, C3-L3≠C4-L4}
•L'ensemble des contraintes est défini par l'union de ces 4 ensembles :
•C = CligU CcolU CdmU Cdd
BIA 2020 : Prolog & IA9 4 reines : 1ère modélisation
?-reines4_v1(R).
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, 2, 4, 3, 3, 1, 2, 4] ;
R = [1, 3, 2, 4, 2, 1, 4, 3] ;
R = [1, 3, 2, 4, 3, 4, 1, 2] ;
R = [1, 3, 4, 2, 2, 1, 3, 4] ;
R = [1, 3, 4, 2, 3, 4, 2, 1] ;
R = [1, 4, 2, 3, 2, 3, 4, 1] ;
R = [1, 4, 2, 3, 3, 2, 1, 4] ;
R = [1, 4, 3, 2, 2, 3, 1, 4] ;
R = [1, 4, 3, 2, 3, 2, 4, 1] ;
R = [2, 1, 3, 4, 1, 3, 4, 2] ;
R = [2, 1, 3, 4, 4, 2, 1, 3] ;
R = [2, 1, 4, 3, 1, 3, 2, 4] ;
R = [2, 1, 4, 3, 4, 2, 3, 1] ;
R = [2, 3, 1, 4, 1, 4, 3, 2] ;
R = [2, 3, 1, 4, 4, 1, 2, 3] ;
R = [2, 3, 4, 1, 1, 4, 2, 3] ;
R = [2, 3, 4, 1, 4, 1, 3, 2] ;
R = [2, 4, 1, 3, 1, 2, 3, 4] ;
R = [2, 4, 1, 3, 4, 3, 2, 1] ;
R = [2, 4, 3, 1, 1, 2, 4, 3] ;
R = [2, 4, 3, 1, 4, 3, 1, 2] ;
R = [3, 1, 2, 4, 1, 2, 4, 3] ;
R = [3, 1, 2, 4, 4, 3, 1, 2] ;
R = [3, 1, 4, 2, 1, 2, 3, 4] ;
R = [3, 1, 4, 2, 4, 3, 2, 1] ;
R = [3, 2, 1, 4, 1, 4, 2, 3] ;
R = [3, 2, 1, 4, 4, 1, 3, 2] ;
R = [3, 2, 4, 1, 1, 4, 3, 2] ;
R = [3, 2, 4, 1, 4, 1, 2, 3] ;
R = [3, 4, 1, 2, 1, 3, 2, 4] ;
R = [3, 4, 1, 2, 4, 2, 3, 1] ;
R = [3, 4, 2, 1, 1, 3, 4, 2] ;
R = [3, 4, 2, 1, 4, 2, 1, 3] ;
R = [4, 1, 2, 3, 2, 3, 1, 4] ;
R = [4, 1, 2, 3, 3, 2, 4, 1] ;
R = [4, 1, 3, 2, 2, 3, 4, 1] ;
R = [4, 1, 3, 2, 3, 2, 1, 4] ;
R = [4, 2, 1, 3, 2, 1, 3, 4] ;
R = [4, 2, 1, 3, 3, 4, 2, 1] ;
R = [4, 2, 3, 1, 2, 1, 4, 3] ;
R = [4, 2, 3, 1, 3, 4, 1, 2] ;
R = [4, 3, 1, 2, 2, 4, 3, 1] ;
R = [4, 3, 1, 2, 3, 1, 2, 4] ;
R = [4, 3, 2, 1, 2, 4, 1, 3] ;
R = [4, 3, 2, 1, 3, 1, 4, 2] ;false. BIA 2020 : Prolog & IA10 Enorme combinatoire...
4 reines : 2ème modélisation
•Intégrer une par;e des contraintes :
•On ne peut pas avoir deux reines sur la même colonne
•Les variables
•Associer à chaque reine i une variable Li, sa colonne étant fixée
•X = {L1, L2, L3, L4}
•Les domaines de valeurs
•D(L1) = D(L2) = D(L3) = D(L4) = {1,2,3,4}
•Les contraintes :
•les reines doivent être sur des lignes différentes •Clig= {Li ≠ Lj/ i élément_de{1,2,3,4}, j élément_de{1,2,3,4} et i ≠ j}
•les reines doivent être sur des diagonales montantes différentes •Cdm= {Li+i≠ Lj+j/ i élément_de{1,2,3,4}, j élément_de{1,2,3,4} et i ≠ j}
•les reines doivent être sur des diagonales descendantes différentes •Cdd = {Li-i≠ Lj-j / i élément_de{1,2,3,4}, j élément_de{1,2,3,4} et i ≠ j}
•L'ensemble des contraintes est défini par l'union de ces 3 ensembles
•C = CligU CdmU Cdd
BIA 2020 : Prolog & IA11 4 reines : 3ème modélisation
•Les variables
•Non pas les posiUons des reines
•Mais les états des 16 cases de l'échiquier Xij(ligne i et colonne j)
•X = { X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44}
•Les domaines de valeurs
•chaque variable peut prendre pour valeur 0 (pas de reine sur la case) ou 1
•D(Xij) = {0,1} pour tout i et tout j compris entre 1 et 4
•Les contraintes :
•les reines doivent être sur des lignes différentes •Clig= {Xi1 + Xi2 + Xi3 + Xi4 = 1 / i élément_de{1,2,3,4}}
•les reines doivent être sur des colonne différentes •Ccol= {X1i + X2i + X3i + X4i = 1 / i élément_de{1,2,3,4}}
•les reines doivent être sur des diagonales montantes différentes •Ccol= pour tout couple de variables différentes Xijet Xkl, i+j=k+l=> Xij+ Kkl≤ 1
•les reines doivent être sur des diagonales descendantes différentes •Cdd = pour tout couple de variables différentes Xijet Xkl, i-j=k-l=> Xij+ Kkl≤ 1
•L'ensemble des contraintes est défini par l'union de ces 3 ensembles
•C = CligU CcolU CdmU Cdd
BIA 2020 : Prolog & IA12 Généralisation à N reines
•Par exemple, la deuxième modélisa;on devient :
•Variables :
•L = {Li / i est un enQer compris entre 1 et n}
•Domaines :
•Quelque soit Li élément de L, D(Li) = {j / j est un enQer compris entre 1 et n}
•Contraintes :
•les reines doivent être sur des lignes différentes •Clig= {Li ≠ Lj/ i et j sont 2 enUers différents compris entre 1 et n}
•les reines doivent être sur des diagonales montantes différentes •Cdm= {Li+i≠ Lj+j/ i et j sont 2 enUers différents compris entre 1 et n}
•les reines doivent être sur des diagonales descendantes différentes •Cdd = {Li-i≠ Lj-j / i et j sont 2 enUers différents compris entre 1 et n}
•L'ensemble des contraintes est défini par l'union de ces 3 ensembles
•C = CligU CdmU Cdd
BIA 2020 : Prolog & IA13 CSP : généralisation
•Prédicats de résolu-on génériques
•Nécessitent la défini-on pour chaque problème des prédicats •domaines(L) qui génère la liste L des couples [Variable,Domainede la variable]
•consistants(affecta:on1,affecta:on2) si les deux affecta:ons sont compa:bles
BIA 2020 : Prolog & IA14 De quoi va-t-on parler ?
•Les débuts •Avec Eliza
•RésoluCon par saCsfacCon de contraintes (CSP) •Avec les N-Reines
•Recherche dans un graphe d’états •Avec le labyrinthe
•DécomposiCon de problèmes •Avec les Tours de Hanoi
•Système à base de connaissances en TP...
BIA 2020 : Prolog & IA15 Un problème de labyrinthe
BIA 2020 : Prolog & IA16 Salle ThéséeEntrée Salle Minotaure
Salle SombreSortie Salle Claire
Salle Ariane
Généralisation : recherche dans un graphe d’états
•On définit pour chaque problème :
•Un état ini-al (ou plusieurs)
•Un état final (ou plusieurs)
•Des états interdits (éventuellement)
•Des opérateurs de transi-on
•On définit un algorithme général de recherche dans le graphe ainsi construit
BIA 2020 : Prolog & IA17 Algorithme de recherche
BIA 2020 : Prolog & IA18 État initial
État courant
Liste des états déjà rencontrés
Opérateur
État suivantÉtat final
Liste des opérateurs à appliquer
De quoi va-t-on parler ?
•Les débuts •Avec Eliza
•RésoluCon par saCsfacCon de contraintes (CSP) •Avec les N-Reines
•Recherche dans un graphe d’états •Avec le labyrinthe
•DécomposiCon de problèmes •Avec les Tours de Hanoi
•Système à base de connaissances en TP...
BIA 2020 : Prolog & IA19 Les tours de Hanoï
BIA 2020 : Prolog & IA20 Situation initialeObjectif
Problème ini;al
Sous-problème 1
Sous-problème 2
Sous-problème 3
Décomposition un problème en sous-problèmes
BIA 2020 : Prolog & IA21 De quoi va-t-on parler ?
•Les débuts •Avec Eliza
•RésoluCon par saCsfacCon de contraintes (CSP) •Avec les N-Reines
•Recherche dans un graphe d’états •Avec le labyrinthe
•DécomposiCon de problèmes •Avec les Tours de Hanoi
•SBC en TP...
BIA 2020 : Prolog & IA
22