Intelligence Artificielle AI - Prolog : Examen Intelligence Artificielle 2019 CCF Session1 correcti
Télécharger PDFModélisation de problèmes en CSP (Contraintes Satisfaction Problem)
Question 1 : Proposez une modélisation du problème des carrés latins pour N=4 sous forme d’un CSP.
Variables
S = [ [X11, X12, X13, X14], [X21, X22, X23, X24], [X31, X32, X33, X34], [X41, X42, X43, X44] ] où Xij représente la couleur d’une case (i, j) avec 1 ≤ i ≤ 4 et 1 ≤ j ≤ 4, soit 16 variables.
Domaines
Dxij = {1, 2, 3, 4} pour toute case (i, j), ou Domaine = {rouge, vert, bleu, jaune} selon la représentation choisie.
Contraintes
Pour tout i ∈ [1 ;4], pour tout j ∈ [1 ;4], pour tout k ∈ [1 ;4] :
- Si j ≠ k alors Xij ≠ Xik (contrainte de ligne)
- Si i ≠ k alors Xij ≠ Xkj (contrainte de colonne)
Raisonnement logique avec la logique des prédicats
Question 2 : Comment démontrer qu’un raisonnement est valide à l’aide de la logique des prédicats ? Illustrez avec la formule suivante : F = ∀x ∃y ∀z (R(x, z) → R(x, y)).
Étapes pour prouver la validité universelle
1. Formaliser le problème en logique des prédicats : traduire toutes les clauses et la négation de la conclusion.
2. Mettre la formule sous forme clausale (FNC) : conjonction de disjonctions, puis prénexe, puis skolémisation (fixer toutes les ∃).
3. Appliquer une preuve par réfutation avec unification dans le monde de Herbrand.
4. Si l’ensemble des instances de base est insatisfiable, alors le raisonnement est valide.
Exemple de preuve
La négation de F donne : ¬F = ∃x ∀y ∃z (R(x, z) ∧ ¬R(x, y)).
Après skolémisation : ¬F = ∃f ∀y (R(a, f(y)) ∧ ¬R(a, y)).
Forme clausale
C¬F = {R(a, f(y1)), ¬R(a, y2)}.
Monde de Herbrand
H0 = {a, f(a)}.
Unification : y1 = a et y2 = f(a) → C¬F = {R(a, f(a)), ¬R(a, f(a))} devient insatisfiable.
Conclusion : ¬F ne peut être vraie, donc F est universellement valide.
Système à base de connaissances pour les réunions
Question 3 : Base de règles exploitable par un moteur d’inférence pour prédire le déroulement des réunions.
Règles
R1 : Si retard Alors non(reunion(alphonse)).
R2 : Si reunion(jules) ∧ reunion(eva) Alors non(calme).
R3 : Si reunion(sophie) Alors retard.
R4 : Si reunion(marc) Alors reunion(eva).
R5 : Si reunion(jules) ∧ reunion(sophie) ∧ reunion(eva) ∧ non(reunion(alphonse)) Alors fructueuse.
Deduction avec chainage avant
Question 4 : Avec Jules et Marc présents, déduire le déroulement de la réunion.
Mécanisme utilisé : Chainage avant
Base de faits (BF) = {reunion(jules), reunion(marc)}.
1ère boucle : R4 → BF = {reunion(jules), reunion(marc), reunion(eva)}.
2ème boucle : R2 → BF = {reunion(jules), reunion(marc), reunion(eva), non(calme)}.
Conclusion : La réunion ne sera pas calme.
Deduction avec chainage arrière
Question 5 : Avec Jules, Marc et Sophie présents, la réunion sera-t-elle fructueuse ?
Mécanisme utilisé : Chainage arrière
But : prouver fructueuse.
R5 prouve fructueuse si on a : reunion(jules), reunion(sophie), reunion(eva), non(reunion(alphonse)).
Vérification des prémisses :
- reunion(jules) et reunion(sophie) sont dans la BF.
- R4 prouve reunion(eva) si reunion(marc) est dans la BF.
- R3 prouve retard si reunion(sophie) est dans la BF.
- R1 prouve non(reunion(alphonse)) si retard est vrai.
Conclusion : La réunion sera fructueuse.
Modélisation en Prolog
Question 6 : Prédicats pour décrire les recettes de confitures.
preparation(sucre, 1).
preparation(pomme, 15).
preparation(figue, 10).
preparation(abricot, 5).
preparation(noisette, 15).
preparation(vanille, 1).
cuisson(conf_figue, 30).
cuisson(conf_abricot, 25).
ingredients(conf_figue, [sucre, figue, vanille]).
ingredients(conf_abricot, [sucre, abricot, vanille]).
Prédicat quialetemps(X, Conf)
Question 7 : Déterminer qui a le temps de faire une confiture.
prepaingredient([], Td, Td).
prepaingredient([X|L], Td, Tr) :- preparation(X, T), T1 is Td - T, T1 >= 0, prepaingredient(L, T1, Tr).
quialetemps(X, Conf) :- temps(X, T), ingredients(Conf, Liste), cuisson(Conf, Tc), T1 is T - Tc, T1 >= 0, prepaingredient(Liste, T1, TR), TR >= 0.
Prédicat quipeut(X, Conf)
Question 8 : Déterminer qui peut faire une confiture.
prepaingredient2(_, [], Td, Td).
prepaingredient2(P, [X|L], Td, Tr) :- possede(P, X), preparation(X, T), T1 is Td - T, T1 >= 0, prepaingredient2(P, L, T1, Tr).
quipeut(X, Conf) :- temps(X, T), ingredients(Conf, Liste), cuisson(Conf, Tc), T1 is T - Tc, T1 >= 0, prepaingredient2(X, Liste, T1, TR), TR >= 0.
FAQ
Qu’est-ce qu’un CSP ?
Un CSP (Contraintes Satisfaction Problem) est un modèle mathématique utilisé pour résoudre des problèmes où certaines variables doivent prendre des valeurs dans un domaine tout en respectant un ensemble de contraintes.
Comment fonctionne le chainage avant en logique des prédicats ?
Le chainage avant consiste à appliquer les règles en partant des faits connus pour déduire de nouvelles conclusions jusqu’à ce qu’il n’y ait plus de règles applicables ou que le but soit atteint.
Qu’est-ce que la skolémisation en logique des prédicats ?
La skolémisation est une transformation qui élimine les quantificateurs existentiels (∃) en les remplaçant par des constantes ou des fonctions, facilitant ainsi la preuve par réfutation.