Intelligence Artificielle AI - Prolog : PROgrammation LOGique 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 CM5-6 : PROgrammationLOGique Marie Lefevre
2020-2021
Université Claude Bernard Lyon 1
Sondage Tomuss...
Qui a déjà fait du Prolog ?
ÞMerci de répondre J
BIA 2020 : Prolog2 Origines
•1972 : Prolog I
•Alain COLMERAUER (Université Aix-Marseille)
•Découverte de la programmaEon logique et premier interpréteur
•Robert A. KOWALSKY (Edinburgh University)
•Cadre théorique et premier compilateur
•1982 : Prolog II
•M. VAN CANEGUEM et al.•.... •Nombreux interpréteurs Prolog avec des syntaxes différentes•... •1996 : Prolog IV •SWI-Prolog : syntaxe, convenEons et interpréteur uElisé dans ce cours
BIA 2020 : Prolog3 Différents modes de programmation
•Langages de style impéraEf
•C, ADA, PASCAL, JAVA (objet)... ØOn décrit la suite d'acEons permeXant de passer des données aux résultats
•Langages de style foncEonnel
•Lisp, Scheme, CAML ... ØOn décrit le résultat comme une composiEon de foncEons agissant sur les données
•Langage de style déclaraEf
•Prolog ØOn décrit le problème (les objets, leurs propriétés, leurs relaEons)
ØMais pas comment on le résout
ØSouvent uEliséen Intelligence ArEficielle BIA 2020 : Prolog4 Le langage PROLOG
•Langage d’expression des connaissances fondé sur la logique des prédicats du premier ordre
•ImplémentaEon du principe de résoluEon
•ProgrammaEon déclaraEve •L’uElisateur définit une base de connaissances (des faits, des règles) •Pas d’instrucEon, pas d’affectaEon, pas de boucles explicites •Uniquement des clauses exprimant des faits, des règles, des quesEons •L’interpréteur PROLOG uElise ceXe base de connaissances pour répondre àdes quesEons / résoudre des problèmes
BIA 2020 : Prolog5 De quoi va-t-on parler ?
•Syntaxe et fonc,onnement du Prolog
•Les listes
•Les chaînes de caractères
•Les boucles mues par l’échec
•Points de choix et coupure
•Pour travailler en Swi-Prolog
•Ques,ons à se poser pour «coder en prolog»
•Pour aller plus loin
BIA 2020 : Prolog6 Constantes et variables
•Constantes
•Nombres : 12, 3.5•Atomes •Chaînes de caractères commençant par une minuscule
•Chaînes de caractères entre ""
•Liste vide [ ]
•Variables
•Chaînes de caractères commençant par une majuscule
•Chaînes de caractères commençant par _
•La variable «indéterminée» : _
BIA 2020 : Prolog7 Trois sortes de connaissances : faits, règles, questions
•Programme Prolog
•Ensemble de faits et de règles qui décrivent un problème
•Faits : P(...). avec P un prédicat
•Clause de Horn réduite à un liTéral posiUf
•pere(jean, paul).
•pere(albert, jean).
BIA 2020 : Prolog8 Trois sortes de connaissances : faits, règles, questions
•Règles : P(...) :-Q1 (...), ..., Qn (...).
•Clause de Horn complète
•Correspond en logique àQ1 ∧... ∧Qn → P
P : tête de clause, Q1 ,...,Qn queue de clause •Paquet de clauses = clauses ayant le même nom de liXéral de tête
•Exemple de règle
•RelaEon grand-père en logique du premier ordre :
•∀X∀Y (∃Z pere(X,Z)∧(pere(Z,Y)∨mere(Z,Y))) → papy(X,Y) •∀X∀Y∀Z (((pere(X,Z)∧ pere(Z,Y)) → papy(X,Y)) ∨
((pere(X,Z)∧ mere(Z,Y)) → papy(X,Y))) •FormulaEon Prolog : •papy(X,Y) :-pere(X,Z),pere(Z,Y). •papy(X,Y) :-pere(X,Z),mere(Z,Y).
BIA 2020 : Prolog9 Trois sortes de connaissances : faits, règles, questions
•QuesUons : S(...), ..., T(...).
•Clause de Horn sans liTéral posiUf
•pere(jean,X), mere(annie,X).
•:-pere(jean,X), mere(annie,X).
•Exécuter un programme = résoudre un but
•Trouver toutes les valeurs des variables qui apparaissent dans la quesUon et qui amènent àune contradicUon ØFaire une preuve BIA 2020 : Prolog10 L’unification
•Procédé par lequel on essaie de rendre deux formules idenUques en donnant des valeurs aux variables qu’elles conUennent
•Le résultat est un unificateur •Par exemple : {Jean/X, Paul/Y} •Pas forcément unique, on cherche l’unificateur le plus général •L’unificaUon peut réussir ou échouer •P(X , X ) et P(2, 3) ne peuvent pas être unifiés BIA 2020 : Prolog11 Déclaratif vs Procédural
•Soit la clause P :-Q, R.
•Aspect déclaraUf : •P est vrai si Q et R sont vrais ØL’ordre des clauses n’a pas d’importance •Aspect procédural :
•Pour résoudre P, résoudre d’abord le sous-problème Q, puis le sous-problème R
ØL’interpréteur considère les clauses les unes après les autres, dans l’ordre dans lesquelles elles se trouvent, celui-ci a de l’importance
BIA 2020 : Prolog12 Littéraux ordonnés•P. •P est toujours vrai •P :− Q1 , Q2 , ... , Qn .
•Pour résoudre P, il faut résoudre dans l’ordre Q1 puis Q2 puis ... puis Qn •:− Q1 , Q2 , ... , Qn .
•Pour résoudre la quesUon, il faut résoudre dans l’ordre Q1 puis Q2 puis ... puis Qn BIA 2020 : Prolog13 Réfutation par résolution
•Programme P
P1 :pere(charlie, david).
P2 :pere(henri, charlie).
P3 : papy(X,Y) :-pere(X,Z), pere(Z,Y).
•Appel du programme P
Q : papy(X,Y).
•Réponse
X=henri, Y=david
BIA 2020 : Prolog14 Graphe de résolution
BIA 2020 : Prolog
Q : ¬papy(X,Y)
P3 : papy(X,Y) :-pere(X,Z), pere(Z,Y).
P3 :
( pere(X,Z) ∧pere(Z,Y) ) → papy(X,Y)
P3 :
¬ ( pere(X,Z) ∧pere(Z,Y) ) Úpapy(X,Y)
P3 : ¬pere(X1,Z1)Ú¬pere(Z1,Y1)Úpapy(X1,Y1)
¬pere(X,Z1)Ú¬pere(Z1,Y)
P1 : pere(charlie, david)
P2 : pere(henri, charlie)
¬pere(charlie, Y)
P1 : pere(charlie, david)
¬pere(david, Y)
échec : retour arrière
succès de la réfutation
charlie|X
david|Z1X|X1 Y|Y1henri|X charlie|Z1david|Y 15
Interprétation procédurale :
arbre ET-OU
BIA 2020 : Prolog
échecéchecY=davidsuccès papy(X,Y)
pere(X,Z)
pere(Z,Y)et X=charlieZ=david ouP1P2 ouP1P2 pere(david,Y)ou P1P2X=henri Z=charlie
pere(charlie,Y)P3 Prolog parcourt le paquet de clauses de haut en bas, chaque clause étant parcourue de gauche à droite16 Fonctionnement de l’interpréteur
•L’interpréteur prend un premier but
•Il essaie de le résoudre = de l’unifieravec une tête de clause
•Si il réussit, il cherche à résoudre la queue de la clause instanciée par l’unification
•En résolvant dans l’ordre chacun des littéraux
•Puis il passe au prochain but en attente
•En cas d’échec, retour arrière au dernier choix effectué
•Quand une solution est trouvée, on peut
•Arrêter la recherche •Demander une autre solution •La résolution est terminée s’il n’y a plus de littéraux à résoudre et plus de choix à traiter
BIA 2020 : Prolog17 Un programme Prologpapy.pl pere(charlie,david).
pere(henri,charlie).
papy(X,Y) :-pere(X,Z), pere(Z,Y).
Swi-Prolog
Welcometo SWI-Prolog (Multi-threaded, 64 bits, Version 6.2.6)
Copyright (c) 1990-2012 Universityof Amsterdam, VU Amsterdam
SWI-Prolog comeswithABSOLUTELY NO WARRANTY. This isfree software,
and youare welcometo redistributeitundercertain conditions.
Pleasevisitfor details.
For help, use ?-help(Topic). or ?-apropos(Word).?- BIA 2020 : Prolog18 Des questions Prolog
?-[papy].
% papy compiled0.00 sec, 4 clausestrue. ?-listing.
pere(charlie, david).
pere(henri, charlie).
papy(A, C) :-
pere(A, B),
pere(B, C).true. ?-
BIA 2020 : Prolog
?-pere(charlie,david).true. ?-pere(charlie,henri).false. ?-pere(X,Y).
X = charlie,
Y = david. // touche Entrée
?-pere(X,Y).
X = charlie,
Y = david; // point virgule
X = henri,
Y = charlie.?- 19
Des questions Prolog
?-papy(x,y). // minusculefalse. ?-papy(X,Y). // majuscule
X = henri,
Y = david.
?-papy(henri,X).
X = david.
?-halt. // sortie
BIA 2020 : Prolog20 Exercice : L’énigme policière
•On dispose des informaUons suivantes :
•La secrétaire déclare qu’elle a vu l’ingénieur dans le couloir qui donne sur la salle de conférences
•Le coup de feu a été Uré dans la salle de conférences, on l’a donc entendu de toutes les pièces voisines
•L’ingénieur affirme n’avoir rien entendu
•On souhaite démontrer que «si la secrétaire dit vrai, alors l’ingénieur ment»
BIA 2020 : Prolog21 L’é nigme policiè re en Prolog
•On souhaite démontrer que si la secrétaire dit vrai, alors l’ingénieur ment
•Hypothèse
secretaire_dit_vrai.
•Pour la démonstration, on pose la requête :
ingenieur_ment.
BIA 2020 : Prolog22 L’é nigme policiè re en Prolog
•A parUr des informaUons suivantes :
•Le coup de feu a été Uré dans la salle de conférences, on l’a donc entendu de toutes les pièces voisines
•Règle de la logique du 1er ordre
•Un individu entend un bruit s’il se trouve dans une pièce voisine de celle où le bruit a été produit
entend(Individu,Bruit) :-
lieu(Individu,Piece1),
lieu(Bruit,Piece2),
voisine(Piece1,Piece2).
BIA 2020 : Prolog23 L’é nigme policiè re en Prolog
•A partir des informations suivantes :
•La secrétaire déclare qu’elle a vu l’ingénieur dans le couloir qui donne sur la salle de conférences
•Le coup de feu a été tiré dans la salle de conférences, on l’a donc entendu de toutes les pièces voisines
•L’ingénieur affirme n’avoir rien entendu
•Base de faits :
voisine(couloir,salle_de_conf).
lieu(ingenieur,couloir) :-secretaire_dit_vrai.
lieu(coup_de_feu,salle_de_conf).
ingenieur_ment:-entend(ingenieur,coup_de_feu).
BIA 2020 : Prolog24 L’é nigme policiè re en Prolog
enigme.pl
voisine(couloir,salle_de_conf).
lieu(coup_de_feu,salle_de_conf).
lieu(ingenieur,couloir) :-secretaire_dit_vrai.
ingenieur_ment:-entend(ingenieur,coup_de_feu).
entend(Individu,Bruit) :-lieu(Individu,Piece1), lieu(Bruit,Piece2),
voisine(Piece1,Piece2).
secretaire_dit_vrai.
Swi-Prolog
[trace] ?-ingenieur_ment.
Call: (6) ingenieur_ment? creep
Call: (7) entend(ingenieur, coup_de_feu) ? creep
Call: (8) lieu(ingenieur, _G2981) ? creep
Call: (9) secretaire_dit_vrai? creep
Exit: (9) secretaire_dit_vrai? creep
Exit: (8) lieu(ingenieur, couloir) ? creep
Call: (8) lieu(coup_de_feu, _G2981) ? creep
Exit: (8) lieu(coup_de_feu, salle_de_conf) ? creep
Call: (8) voisin(couloir, salle_de_conf) ? creep
Exit: (8) voisin(couloir, salle_de_conf) ? creep
Exit: (7) entend(ingenieur, coup_de_feu) ? creep
Exit: (6) ingenieur_ment? creeptrue. BIA 2020 : Prolog25 Programmation récursive
•Un programme récursif est un programme qui s’appelle lui-même
•Exemple : factorielle
•factorielle(1) = 1
•factorielle(n) = n * factorielle(n-1)si n≠1
•Pour écrire un programme récursif, il faut :
•Choisir sur quoi faire l’appel récursif
•Choisir comment passer du résultat de l’appel récursif au résultat que l’on cherche
•Choisir le(s) cas d’arrêt
BIA 2020 : Prolog
Appel récursif
Cas d’arrêt26 Bouclage
?-listing.
maries(jean, sophie).
maries(philippe, stephanie).
maries(A, B) :-
maries(B, A).true. ?-maries(jean,sophie).true. ?-maries(sophie,jean).true. ?-maries(X,Y).
X = jean
Y = sophie;
X = philippe
Y = stephanie;
X = sophie
Y = jean ;
X = stephanie
Y = philippe;
X = jean
Y = sophie;... BIA 2020 : Prolog
Call: (7) maries(_G2307, _G2308) ? creep
Exit: (7) maries(jean, sophie) ? creep
X = jean,
Y = sophie;
Redo: (7) maries(_G2307, _G2308) ? creep
Exit: (7) maries(philippe, stephanie) ? creep
X = philippe,
Y = stephanie;
Redo: (7) maries(_G2307, _G2308) ? creep
Call: (8) maries(_G2308, _G2307) ? creep
Exit: (8) maries(jean, sophie) ? creep
Exit: (7) maries(sophie, jean) ? creep
X = sophie,
Y = jean ;... 27
Bouclage
?-listing.
maries(jean, sophie).
maries(philippe, stephanie).
maries(A, B) :-
maries(B, A).true. ?-maries(jean,sophie).true. ?-maries(sophie,jean).true. ?-maries(X,Y).
X = jean
Y = sophie;
X = philippe
Y = stephanie;
X = sophie
Y = jean ;
X = stephanie
Y = philippe;
X = jean
Y = sophie;... BIA 2020 : Prolog
?-listing.
maries(jean, sophie).
maries(philippe, stephanie).
sont_maries(A, B) :-
maries(A, B).
sont_maries(A, B) :-
maries(B, A).true. ?-sont_maries(X,Y).
X = jean
Y = sophie;
X = philippe
Y = stephanie;
X = sophie
Y = jean ;
X = stephanie
Y = philippe;false. ?-28 InNluence de l’ordre des clauses
parent(michelle, bernard). parent(thomas, bernard).
parent(thomas, lise).
parent(bernard, anne).
parent(bernard, pierre).
parent(pierre, jean).
ancetre(X, Z) :-parent(X,Z).
ancetre(X, Z) :-parent(X,Y), ancetre(Y,Z). ancetre2(X, Z) :-parent(X,Y), ancetre2(Y,Z). ancetre2(X, Z) :-parent(X,Z). ancetre3(X, Z) :-parent(X,Z).
ancetre3(X, Z) :-ancetre3(X,Y), parent(Y,Z). ancetre4(X, Z) :-ancetre4(X,Y), parent(Y,Z). ancetre4(X, Z) :-parent(X,Z). BIA 2020 : Prolog29 Influence de l’ordre des clauses
?-ancetre(thomas, pierre).true; false.
?-trace, ancetre(thomas, pierre).
Call: (7) ancetre(thomas, pierre) ? creep
Call: (8) parent(thomas, pierre) ? creep
Fail: (8) parent(thomas, pierre) ? creep
Redo:(7) ancetre(thomas, pierre) ? creep
Call: (8) parent(thomas, _G929) ? creep
Exit: (8) parent(thomas, bernard) ? creep
Call: (8) ancetre(bernard, pierre) ? creep
Call: (9) parent(bernard, pierre) ? creep
Exit: (9) parent(bernard, pierre) ? creep
Exit: (8) ancetre(bernard, pierre) ? creep
Exit: (7) ancetre(thomas, pierre) ? creeptrue. BIA 2020 : Prolog
parent(michelle, bernard). parent(thomas, bernard).
parent(thomas, lise).
parent(bernard, anne).
parent(bernard, pierre).
parent(pierre, jean).
ancetre(X, Z) :-
parent(X,Z).
ancetre(X, Z) :-
parent(X,Y), ancetre(Y,Z). 30
InNluence de l’ordre des clauses
?-ancetre2(thomas, pierre).true; false.
?-trace, ancetre2(thomas, pierre).
Call: (7) ancetre2(thomas, pierre) ? creep
Call: (8) parent(thomas, _G1064) ? creep
Exit: (8) parent(thomas, bernard) ? creep
Call: (8) ancetre2(bernard, pierre) ? creep
Call: (9) parent(bernard, _G1064) ? creep
Exit: (9) parent(bernard, anne) ? creep
Call: (9) ancetre2(anne, pierre) ? creep
Call: (10) parent(anne, _G1064) ? creep
Fail: (10) parent(anne, _G1064) ? creep
Redo: (9) ancetre2(anne, pierre) ? creep
Call: (10) parent(anne, pierre) ? creep
Fail: (10) parent(anne, pierre) ? creep
Fail: (9) ancetre2(anne, pierre) ? creep
Redo: (9) parent(bernard, _G1064) ? creep
Exit: (9) parent(bernard, pierre) ? creep
Call: (9) ancetre2(pierre, pierre) ? creep
Call: (10) parent(pierre, _G1064) ? creep
Exit: (10) parent(pierre, jean) ? creep
Call: (10) ancetre2(jean, pierre) ? Creep
Call: (11) parent(jean, _G1064) ? creep
Fail: (11) parent(jean, _G1064) ? creep
Redo: (10) ancetre2(jean, pierre) ? creep
Call: (11) parent(jean, pierre) ? creep
Fail: (11) parent(jean, pierre) ? creep
Fail: (10) ancetre2(jean, pierre) ? creep
Redo: (9) ancetre2(pierre, pierre) ? creep
Call: (10) parent(pierre, pierre) ? creep
Fail: (10) parent(pierre, pierre) ? creep
Fail: (9) ancetre2(pierre, pierre) ? creep
Redo: (8) ancetre2(bernard, pierre) ? creep
Call: (9) parent(bernard, pierre) ? creep
Exit: (9) parent(bernard, pierre) ? creep
Exit: (8) ancetre2(bernard, pierre) ? creep
Exit: (7) ancetre2(thomas, pierre) ? creeptrue. BIA 2020 : Prolog
parent(michelle, bernard). parent(thomas, bernard).
parent(thomas, lise).
parent(bernard, anne).
parent(bernard, pierre).
parent(pierre, jean).
ancetre2(X, Z) :-
parent(X,Y), ancetre2(Y,Z). ancetre2(X, Z) :-
parent(X,Z). 31
InNluence de l’ordre des clauses
?-ancetre3(thomas, pierre).true; ERROR: Out of local stack
?-trace, ancetre3(thomas, pierre).
Call: (7) ancetre3(thomas, pierre) ? creep
Call: (8) parent(thomas, pierre) ? creep
Fail: (8) parent(thomas, pierre) ? creep
Redo: (7) ancetre3(thomas, pierre) ? creep
Call: (8) ancetre3(thomas, _G1298) ? creep
Call: (9) parent(thomas, _G1298) ? creep
Exit: (9) parent(thomas, bernard) ? creep
Exit: (8) ancetre3(thomas, bernard) ? creep
Call: (8) parent(bernard, pierre) ? creep
Exit: (8) parent(bernard, pierre) ? creep
Exit: (7) ancetre3(thomas, pierre) ? creeptrue; Redo: (9) parent(thomas, _G1298) ? creep
Exit: (9) parent(thomas, lise) ? creep
Exit: (8) ancetre3(thomas, lise) ? creep
Call: (8) parent(lise, pierre) ? creep
Fail: (8) parent(lise, pierre) ? creep
Redo: (8) ancetre3(thomas, _G1298) ? creep
Call: (9) ancetre3(thomas, _G1298) ? creep
Call: (10) parent(thomas, _G1298) ? creep
Exit: (10) parent(thomas, bernard) ? creep
Exit: (9) ancetre3(thomas, bernard) ? creep
Call: (9) parent(bernard, _G1298) ? creep
Exit: (9) parent(bernard, anne) ? creep
Exit: (8) ancetre3(thomas, anne) ? creep
Call: (8) parent(anne, pierre) ? creep
Fail: (8) parent(anne, pierre) ? creep
Redo: (9) parent(bernard, _G1298) ? creep
Exit: (9) parent(bernard, pierre) ? creep
Exit: (8) ancetre3(thomas, pierre) ? creep
Call: (8) parent(pierre, pierre) ? creep
Fail: (8) parent(pierre, pierre) ? creep
Redo: (10) parent(thomas, _G1298) ? creep
Exit: (10) parent(thomas, lise) ? creep
Exit: (9) ancetre3(thomas, lise) ? creep
Call: (9) parent(lise, _G1298) ? creep
Fail: (9) parent(lise, _G1298) ? creep
Redo: (9) ancetre3(thomas, _G1298) ? creep
Call: (10) ancetre3(thomas, _G1298) ? creep
Call: (11) parent(thomas, _G1298) ? creep
Exit: (11) parent(thomas, bernard) ? creep... BRANCHE INFINIE
BIA 2020 : Prolog
parent(michelle, bernard). parent(thomas, bernard).
parent(thomas, lise).
parent(bernard, anne).
parent(bernard, pierre).
parent(pierre, jean).
ancetre3(X, Z) :-
parent(X,Z).
ancetre3(X, Z) :-
ancetre3(X,Y), parent(Y,Z). 32
InNluence de l’ordre des clauses
?-ancetre4(thomas, pierre).
ERROR: Out of local stack
?-trace, ancetre4(thomas, pierre).
Call: (7) ancetre4(thomas, pierre) ? creep
Call: (8) ancetre4(thomas, _G1064) ? creep
Call: (9) ancetre4(thomas, _G1064) ? creep
Call: (10) ancetre4(thomas, _G1064) ? creep
Call: (11) ancetre4(thomas, _G1064) ? creep
Call: (12) ancetre4(thomas, _G1064) ? creep
Call: (13) ancetre4(thomas, _G1064) ? creep
Call: (14) ancetre4(thomas, _G1064) ? creep
Call: (15) ancetre4(thomas, _G1064) ? creep
Call: (16) ancetre4(thomas, _G1064) ? creep
Call: (17) ancetre4(thomas, _G1064) ? creep
Call: (18) ancetre4(thomas, _G1064) ? creep
Call: (19) ancetre4(thomas, _G1064) ? creep
Call: (20) ancetre4(thomas, _G1064) ? creep
Call: (21) ancetre4(thomas, _G1064) ? creep
Call: (22) ancetre4(thomas, _G1064) ? creep