Intelligence Artificielle AI - Prolog : TD2 avec Correction – Graphe de décomposition et CSP
Télécharger PDFBase de l’Intelligence Artificielle 2020-2021
Partie 1 – Résolution par Satisfaction de Contraintes
Ce paradigme de résolution de problèmes a été présenté en cours. Pour faire de la résolution de problèmes par CSP (Contrainte de Satisfaction de Problèmes), nous devons définir un problème selon ce formalisme :
- X = {X1, X2, ..., Xn} : l’ensemble des variables caractérisant le problème ;
- D(Xi) : le domaine de chaque variable Xi, c’est-à-dire l’ensemble des valeurs que Xi peut prendre théoriquement ;
- C = {C1, C2, ..., Ck} : l’ensemble des contraintes, sachant que chaque contrainte Cj est une relation entre certaines variables de X, restreignant les valeurs que peuvent prendre simultanément ces variables.
L’exemple de la coloration de carte vu lors du dernier TD est classiquement un problème que l’on peut résoudre en le modélisant ainsi. Pour travailler durant ce TD, nous allons utiliser un cryptarithme, c’est-à-dire un casse-tête numérique et logique qui consiste en une équation mathématique où les lettres représentent des chiffres à trouver.
L’équation comporte habituellement des opérations mathématiques de base, telles que l’addition et la multiplication. L’exemple le plus connu, publié en juillet 1924, est dû à Henry Dudeney :
S E N D + M O R E = M O N E Y
Chaque lettre représente un seul chiffre, et le chiffre le plus significatif est différent de zéro. Idéalement, le casse-tête doit avoir une solution unique. La solution ici est : O=0, M=1, Y=2, E=5, N=6, D=7, R=8, S=9.
Modélisation du problème
Plusieurs modélisations respectant le formalisme précédent peuvent être proposées.
Modélisation 1
- Variables : S, E, N, D, M, O, R, Y
- Domaines :
- DS = DM = {1, 2, 3, 4, 5, 6, 7, 8, 9}
- DE = DN = DD = DO = DR = DY = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- Contraintes :
- (D + E) = Y + Ret1 * 10, où Ret1 a pour domaine de valeur {0, 1}
- (N + R + Ret1) = E + Ret2 * 10, où Ret2 a pour domaine de valeur {0, 1}
- (E + O + Ret2) = N + Ret3 * 10, où Ret3 a pour domaine de valeur {0, 1}
- (S + M + Ret3) = M * 10 + O
- Toutes les variables sont différentes
Modélisation 2
- Variables : S, E, N, D, M, O, R, Y
- Domaines :
- DS = DM = {1, 2, 3, 4, 5, 6, 7, 8, 9}
- DE = DN = DD = DO = DR = DY = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
- Contraintes :
- 1000(S + M) + 100(E + O) + 10(N + R) + (D + E) = 10000M + 1000O + 100N + 10E + Y
- Toutes les variables sont différentes
Méthode « Générer et Tester »
Si on utilise la méthode classique consistant à construire l’espace des états en générant toutes les solutions puis en les testant, combien d’affectations différentes doit-on tester pour trouver toutes les solutions ?
On teste toutes les affectations possibles. Pour chaque variable, on multiplie les tailles des domaines :
Taille de l’espace = taille de DS * taille de DM * taille de DE * taille de DN * taille de DD * taille de DO * taille de DR * taille de DY = 9 * 9 * 10 * 10 * 10 * 10 * 10 * 10 = 81 millions d’états.
Méthode « Retour Arrière »
Dans cette méthode, on retourne en arrière quand, à l’évidence, il n’y a plus de solutions possibles.
Avec la modélisation 1, les affectations effectuées sont :
- A = {(S, 1)} → consistant
- A = {(S, 1), (E, 0)} → consistant
- A = {(S, 1), (E, 0), (N, 0)} → inconsistant car deux variables ont la même valeur
- A = {(S, 1), (E, 0), (N, 1)} → inconsistant car deux variables ont la même valeur
- A = {(S, 1), (E, 0), (N, 2)} → consistant
- A = {(S, 1), (E, 0), (N, 2), (D, 0)} → inconsistant car deux variables ont la même valeur
- A = {(S, 1), (E, 0), (N, 2), (D, 1)} → inconsistant car deux variables ont la même valeur
- A = {(S, 1), (E, 0), (N, 2), (D, 2)} → inconsistant car deux variables ont la même valeur
- A = {(S, 1), (E, 0), (N, 2), (D, 3)} → consistant (l’algorithme ne vérifie pas encore la contrainte (D + E) = Ret1 * 10 + Y)
- A = {(S, 1), (E, 0), (N, 2), (D, 3), (M, 1)} → inconsistant
Méthode « Filtrage »
Dans cette méthode, à chaque fois qu’une affectation est faite, on réduit le domaine des variables. Si on n’est pas arrivé au but et qu’un domaine de variable est vide, alors on ne va pas plus loin dans l’affectation.
Avec la modélisation 1, les affectations effectuées sont :
- A = {(S, 1)} → consistant, on enlève le 1 de tous les domaines de valeurs
- A = {(S, 1), (E, 0)} → consistant, on enlève le 0 de tous les domaines de valeurs
- A = {(S, 1), (E, 0), (N, 2)} → consistant, on enlève le 2 de tous les domaines de valeurs
- A = {(S, 1), (E, 0), (N, 2), (D, 3)} → en enlevant les valeurs du domaine de Y, l’algorithme se rend compte que le domaine de Y devient vide et donc backtracke
- A = {(S, 1), (E, 0), (N, 2), (D, 4)} → idem pour toutes les valeurs de D, mais on les teste toutes
Heuristique Générale
Une heuristique générale pour résoudre un problème de satisfaction de contraintes consiste à :
- Toujours commencer par les variables les plus contraintes.
- Si une variable n’a plus qu’une seule valeur possible, on l’affecte immédiatement.
Heuristique Spécifique aux Cryptarithmes
Pour les cryptarithmes, une heuristique efficace est :
- D’abord les unités, puis les dizaines, puis les centaines, etc.
Partie 2 – Décomposition de Problèmes en Graphe d’États
Pour résoudre un problème, une approche consiste à le décomposer en sous-problèmes « triviaux » que l’on pourra résoudre facilement. Nous étudions ici l’algorithme BSH (Backtrack Search dans un Hypergraphe) qui permet de parcourir un graphe ET/OU pour trouver une décomposition qui résout le problème.
Cet algorithme est applicable à des problèmes modélisables de manière récursive ou selon une base d’opérateurs de décomposition. Il utilise un majorant sur le rang des états, noté rg(u). Si le rang dépasse un seuil, BSH retourne « Échec ».
- RESOLUS : ensemble des états terminaux et des états u tels qu’il existe un connecteur Si(u) dont tous les successeurs v sont dans RESOLUS.
- INSOLUBLES : ensemble des états non terminaux sans successeur et des états u tels que pour tout connecteur Si(u), il existe un successeur v dans INSOLUBLES.
Exemple d’Application de l’Algorithme BSH
Pour illustrer cet algorithme, considérons un problème décomposé selon les règles suivantes :
- R1 : P → A, B
- R2 : P → C, D, E
- R3 : C → G, I
- R4 : E → H
- R5 : P → C, F
- R6 : E → I, J
- R7 : F → D, K
Les problèmes terminaux sont : G, D, I, K. Le problème à résoudre est : P.
Graphe ET/OU de Résolution
Quand on fait tourner BSH(P) à la main, voici les étapes clés :
- Variables initiales : u = P, RESOLUS = {}, INSOLUBLES = {}, rg(u) = 0.
- Règles applicables en P : R1, R2, R5.
- Application de R1 : successeurs A, B.
- BSH(A) échoue car A n’est pas terminal et sans règle de décomposition → A est ajouté à INSOLUBLES.
- Retour à R2 : successeurs C, D, E.
- BSH(C) : C est décomposable en G, I via R3.
- BSH(G) : G est terminal → succès.
- BSH(I) : I est terminal → succès.
- C est ajouté à RESOLUS.
- Successeur D : terminal → ajouté à RESOLUS.
- Successeur E : mène à un échec → E est ajouté à INSOLUBLES.
- Retour à R5 : C est dans RESOLUS, F résolu via D et K → succès avec R5, R3 et R7.
Problème de Planification : Le Singe et les Bananes
Le problème du singe et des bananes implique un singe, des bananes et une caisse. Voici une modélisation possible :
Représentation d’un État
- Position(Singe, X) où X ∈ {A, B, C}
- Position(Banane, X) où X ∈ {A, B, C}
- Position(Caisse, X) où X ∈ {A, B, C}
- Hauteur(Singe, H) où H est un entier positif
- Hauteur(Banane, H) où H est un entier positif
- Hauteur(Caisse, H) où H est un entier positif
- Possède(Singe, Banane) : vrai ou faux
État Initial
- Position(Singe, A)
- Position(Banane, B)
- Position(Caisse, C)
- Hauteur(Singe, 1)
- Hauteur(Banane, 2)
- Hauteur(Caisse, 1)
- Possède(Singe, Banane) : faux
État Final
- Possède(Singe, Banane) : vrai
- Position(Singe, X) et Position(Banane, X) où X ≠ C
- Position(Caisse, C)
Opérateurs
- Op1 : Aller(P1, P2) : Le singe se déplace d’un point à un autre.
- Op2 : Déplacer(Caisse, P1, P2) : Le singe déplace la caisse d’un point à un autre.
- Op3 : Saisir(Banane) : Le singe saisit les bananes.
- Op4 : Lâcher(O) : Le singe lâche un objet.
- Op5 : Grimper(Caisse) : Le singe grimpe sur la caisse.
- Op6 : Descendre(Caisse) : Le singe descend de la caisse.
FAQ
Qu’est-ce qu’un cryptarithme ?
Un cryptarithme est un casse-tête logique où chaque lettre représente un chiffre unique, et où l’objectif est de résoudre une équation mathématique en trouvant les valeurs des lettres.
Comment modéliser un problème de satisfaction de contraintes ?
Un problème de satisfaction de contraintes se modélise en définissant un ensemble de variables, leurs domaines respectifs et les contraintes qui limitent les combinaisons possibles de valeurs pour ces variables.
Quelle est la différence entre les méthodes « Retour Arrière » et « Filtrage » ?
La méthode « Retour Arrière » explore toutes les possibilités sans réduire les domaines des variables, tandis que la méthode « Filtrage » réduit dynamiquement les domaines des variables à chaque affectation pour éviter des explorations inutiles.