Algorithmes de moteurs d'inférence
(Cours IA Lyon 1, 1990)
Version 1.0 du 2/5/2003
Table des matières
Algorithme
minimal : chaînage avant
Variante :
recherche en largeur
Recherche en
profondeur : gestion d'une pile d'état
Recherche en
profondeur : version optimisée
Régime irrévocable en chaînage arrière : gestion d'une
pile de buts
Ce régime convient dans les (rares !) cas où la plupart des chemins mènent à la solution.
Organigramme :
Etat courant <- Etat initial
Répéter
Choisir une Transition
Etat courant -> (Transition) nouvel Etat courant
Jusqu'à Condition d'arrêt
Caractéristiques du moteur :
Il s'agit du moteur intitulé "MOTEUR_1_AVI"
Chaînage avant ("AV")
Régime irrévocable ("I")
Choix de règle : procédure quelconque (par exemple, la première règle)
Conclusions de la règle déclanchée : elles sont immédiatement intégrées à la BF
Une règle ne peut être déclanchée qu'une seule fois (si elle est déclanchée au mauvais moment, c'est irrévocablement perdu)
Seul l'état courant est mémorisé, en écrasant l'état précédant
Définitions :
BF : Base des faits
BR : Base des règles
Q : Fait à déduire
ER : Ensemble des règles considérées (ER appartient à BR)
Algorithme :
Procédure DEDUIRE(Q)
Si Q Appartient à BF Alors Ecrire "succès" ;
Sinon Appel CYCLE(BR) ; ' Passage de l'argument BR en guise de 1er ER
Procédure CYCLE(ER)
Si ER Vide Alors Ecrire "échec" ; Retour ;
R <- CHOIX(R, ER) ; ' Choisir une règle
ER <- ER - R ; ' La retirer de l'ensemble des règles considérées
Si Toutes les prémisses de R Appartiennent à BF Alors
Si Conclusions de R Contiennent Q Alors Ecrire "succès" ; Retour ;
Sinon ' On n'a pas encore prouvé Q mais on progresse
' Application d'une règle R
BF <- BF Union Conclusions de R ; ' Ajout des nouveaux faits prouvés
BR <- BR - R ; ' La règle R a été utilisée avec succès, on la retire irrévocablement de la BR
Appel CYCLE(BR) ;
Sinon Appel CYCLE(ER) ;
Retour ;
VBBrainBox fonctionne de manière analogue (mais sans utiliser la récursivité : il est en effet inutile ici d'empiler des appels de fonction lorsqu'une simple boucle fait l'affaire !), excepté le fait que VBBrainBox cherche à appliquer toutes les règles, tandis que ce moteur cherche si Q peut être déduit de la BF.
MOTEUR_1BIS_AVI_bf
bf : Breadth first : recherche d'abord en largeur
Le moteur MOTEUR_1BIS_AVI_bf est une variante du MOTEUR_1_AVI : il procède par une recherche en largeur, toujours en régime irrévocable.
Pour chaque état, on déclenche toutes (ou bien certaines) les règles possibles et, seulement après, on intègre globalement leurs conclusions NF dans la BF pour produire l'état suivant.
NF : Ensemble des nouveaux faits prouvés pour cet état seulement
Compteur : nombre de règles déclanchées entre l'état n et n+1
Algorithme :
Procédure DEDUIRE(Q)
Si Q Appartient à BF Alors Ecrire "succès" ;
Sinon
NF <- Vide ;
Appel CYCLE(BR, NF) ;
Retour ;
Procédure CYCLE(ER, NF)
Global : BR, BF, Q, Compteur ; ' Ces variables doivent survivrent à la récursivité
Local : ER, NF, R ; ' Ces variables sont distinctes à chaque profondeur
Si ER Vide Alors
Si NF Vide Alors Ecrire "échec" ; Retour ;
Sinon
BF <- BF + NF ;
NF <- Vide ;
Compteur = 0 ;
Appel CYCLE(BR, NF) ; ' état suivant
Sinon ' ER n'est pas vide
R <- Première règle de ER ;
ER <- ER - R ; ' La règle peut être supprimée car Logique d'ordre 0 : les règles ne sont pas générales
Si Prémisses de R Appartiennent à BF Alors
Si Conclusions de R Contiennent Q Alors Ecrire "succès" ; Retour ;
Sinon
Ajouter à NF les conclusions de R qui n'appartiennent pas déjà à BF ou à NF ;
BR <- BR - R ; ' Une règle ne peut être appliquée qu'une fois : régime irrévocable
Compteur += 1 ;
Tant que Compteur <=3 ' Par exemple, les 3 meilleures règles
Appel CYCLE(ER, NF) ; ' Règle suivante
Retour ;
- Aucun retour en arrière n'est nécessaire ici, car cette procédure est exhaustive. Sinon on utilise un compteur de règles envisagées ;
- Ecrasement successif des états et aussi des règles ;
- Ce moteur est incapable d'indiquer les règles qui lui ont effectivement été utile (sûr ?) ;
- Solution très coûteuse s'il y a beaucoup de fils à chaque noeud, même si la solution est peu profonde (par exemple, ce moteur n'est pas applicable pour le jeu d'échec) ;
- Ce moteur ne marche pas si certaines règles sont en concurrence : les conclusions de l'une inhibant une prémisse de l'autre (paire critique).
MOTEUR_2_AVRM_df
Caractéristiques :
df : Depth first : recherche d'abord en profondeur
backtrack d'état (avec blocage) : on dépile lorsque l'on n'a plus besoin de l'état. Possibilité de restauration de l'état antérieur. Dans ce cas (backtrack), perte de l'ancienne portion de l'arbre des états.
Organigramme :
Arbre des Etats <- Etat initial
Répéter
Choisir un Etat "vivant" E
Choisir une Transition T possible sur E
Etat courant E -> (Transition T) nouvel Etat courant E' ajouté à l'Arbre des Etats
Jusqu'à Condition d'arrêt
On développe toujours sur l'état courant si possible. En cas de blocage (soit il n'y a plus de transition possible, soit l'état est jugé sans intérêt), retour au dernier point de choix possible : exploration d'une branche le plus loin possible (en profondeur).
Si les choix de transition sont bons (selon le domaine), cette stratégie permet de trouver une solution, même profonde dans l'arbre des solutions (la qualité du choix de transition est crucial, surtout au départ).
Si l'état est jugé sans intérêt, soit la direction est définitivement inhibée, ou bien alors, l'état est inhibé mais éventuellement ré-activable en cas de blocage général (les contraintes du jugement sont alors abaissées pour être moins sévères).
Définitions :
IP : pointeur de pile (IP = 0 : pile vide)
Règle marquée "en bleu" : règle déjà testée pour cet état
Règle marquée "en rouge" : règle en cours d'utilisation
Règle non marquée : ni "rouge" ni "bleu" : jamais utilisée dans cette situation
ER : Ensemble des règles considérées (ER appartient à BR)
EF : Ensemble des faits : BF + nouveaux faits prouvés
Explications : un exemple
Etat e : Faits : Règles applicables : Règle appliquée : Suite
Etat 0 : ABC : R1 R2 R3 R4 R5 : état initial : R2 va être appliquée
Etat 1 : ABCD : R1 R3 R4 R5 : R2 appliquée, R4 va être appliquée
Etat 2 : ABCDF : R1 R3 R5 : R4 appliquée : impasse, on retourne à l'état 1
Etat 1' : ABCD : R1 R3 R5 (R4 déjà tentée à cette profondeur) : R1 va être appliquée
Etat 3 : ABCDG : R3 R4 R5 (R4 peut à nouveau être appliquée) : R1 appliquée
|
Etat 2 |
1 2 3 4
5 |
A B C F |
R4 : A, D ->
F |
|
Etat 1 |
1 2 3 4
5 |
A B C D |
R2 : A, B ->
D |
|
Etat 0 |
1 2 3 4 5 |
A B C |
|
|
Etat n° |
Pile des règles |
Faits prouvés |
Règles appliquées |
On effectue le bactrak d'état : les règles en cours d'utilisation sont en rouge
|
Etat 3 |
1 2
3 4 5 |
A B C D G |
R1 : B, C ->
G |
|
Etat 1' |
1 2
3 4 5 |
A B C D |
|
|
Etat 0 |
1 2 3 4 5 |
A B C |
|
|
Etat n° |
Pile des règles |
Faits prouvés |
Règles appliquées |
Dans l'état 3, on a plus besoin de se souvenir de la preuve de F, cela n'est pas propagé (si les faits étaient propagés alors la pile de faits serait inutile, et seule la pile de règles suffirait : notion différente du backtrack d'état). Faut-il propager ? cela dépend de la nature des conclusions déductibles, par exemple, ne pas propager le fait : casserole vide.
Algorithme :
Procédure DEDUIRE(Q)
Si Q Appartient à BF Alors Ecrire "succès" ;
Sinon
Empiler BR, BF ;
IP <- 1 ;
Appel CYCLE(BR, BF) ;
Retour ;
Procédure CYCLE(ER, EF)
Local : ER, EF, R ; ' Ces variables sont distinctes à chaque profondeur
Si ER Vide Alors
IP <- IP -1 ; ' Dépiler d'un niveau
Si IP = 0 Alors Ecrire "échec" ; Retour ;
Sinon
ER <- Règles de Sommet_pile non marquées ; ' ni rouge, ni bleu
EF <- Faits de Sommet_pile ;
Appel CYCLE(ER, EF) ; Retour ;
R <- CHOIX(R, ER) ; ' Choisir une règle
ER <- ER - R ; ' La retirer de l'ensemble des règles considérées
Si Prémisses de R Appartiennent à EF Alors
Si (Conclusions de R sont contenues dans Q) Alors Ecrire "succès" ; Retour ;
Sinon
Empiler (EF Union Conclusions de R) et BR ; ' (IP <- IP +1)
Propager dans Sommet_pile les marques rouges de l'état Sommet_pile - 1 ;
Marquer R en rouge dans Sommet_pile ;
Marquer R en bleu dans Sommet_pile - 1 ;
ER <- Règles de Sommet_pile non marquées ; ' il existe seulement des rouges car en ce moment même, on est en train de progresser en avant
EF <- Faits de Sommet_pile ;
Appel CYCLE(ER, EF) ; Retour ;
Appel CYCLE(ER, EF) ;
Retour ;
Il est aberrant d'empiler tous les états, on n'empile que les règles marquées.
PR : Pile de règles marquées en rouge : règles en cours d'utilisation
PF : Pile de faits nouveaux prouvés
PB : Pile de règles marquées bleu seulement : règles déjà testées pour cet état
|
2 |
4 |
|
F |
R4 : A, D -> F |
|
1 |
2 |
4 |
D |
R2 : A, B -> D |
|
0 |
|
2 |
|
|
|
IP |
PR |
PB |
PF |
Règle appliquée |
Remarque : il y a toujours un décalage de 1 entre PB et PR (si on avance toujours en ligne droite)
Il n'y a pas de marque rouge pour la racine (les marques rouges ayant toujours un antécédent bleu)
Algorithme :
Procédure DEDUIRE(Q)
Si Q Appartient à BF Alors Ecrire "succès" ;
Sinon
IP <- 1 ;
Appel CYCLE(BR, BF) ;
Retour ;
Procédure FABETAT(ER, EF) ;
ER <- BR - chaque règle PR(J), pour J = 1 à IP (si IP >= 1, IP = 0 étant la racine)
- les règles de PB(IP) ; ' lors d'un bactrack, supprimer les règles déjà testées pour l'état pointé par IP
EF <- BF + les faits des PF(J), pour J = 1 à IP (si IP >= 1) ;
Retour ;
Procédure CYCLE(ER, EF)
Local : ER, EF, R ; ' Ces variables sont distinctes à chaque profondeur
Si ER Vide Alors
IP <- IP -1 ; ' Dépiler d'un niveau
Si IP = 0 Alors Ecrire "échec" ; Retour ;
Sinon
Appel FABETAT(ER, EF) ;
Appel CYCLE(ER, EF) ; Retour ;
R <- CHOIX(R, ER) ; ' Choisir une règle
ER <- ER - R ; ' La retirer de l'ensemble des règles considérées
Si Prémisses de R Appartiennent à EF Alors
Si (Conclusions de R sont contenues dans Q) Alors Ecrire "succès" ; Retour ;
Sinon
IP <- IP +1 ;
PF(IP) <- Conclusions de R ; ' Nouveaux faits prouvés
PR(IP) <- R ; ' Règle en cours d'utilisation
PB(IP - 1) <- PB(IP - 1) + R ; ' Règle R déjà testée pour cet état
Appel FABETAT(ER, EF) ;
Appel CYCLE(ER, EF) ; Retour ;
Appel CYCLE(ER, EF) ;
Retour ;
Note : Cet arbre des états ne contient que des noeuds ET car lorsque l'on effectue le backtrack, on ne tient plus compte de l'impasse : il n'y a donc pas de noeud OU : voir le backtrack du buts :
Ce moteur est le plus complexe présenté ici. Le backtrack de buts crée aussi des noeuds OU afin de conserver tous les buts rencontrés, contrairement au backtrack d'état dans lequel les résultats des impasses sont effacées au fur et à mesure de la progression.
Remarques :
- Critère de choix de buts : appel à une procédure qui peut retourner n'importe lequel des buts disponibles ;
- Chaque fois qu'un but sera prouvé, des simplifications locales de l'arbre des buts seront entreprises ;
- Chaque but prouvé est ajouté définitivement à la base de faits ;
- Les règles qui concluent sur B ne seront pas enlevées de la BR : c'est une simplification locale et non globale ;
- A chaque noeud est associé la nature de la liaison : NAT(n) appartient à {'ET', 'OU', 'BUT'} ;
- Chaque noeud 'ET' possède un ou plusieurs fils 'BUT' ;
- Chaque noeud 'OU' a pour père un 'BUT' exclusivement et a au moins 2 fils 'ET' ;
- Un noeud 'BUT' a soit :
* pas de fils : c'est une feuille,
* 1 fils 'ET' (1 seulement),
* 1 fils 'OU'(1 seulement),
- Le noeud 'BUT' a forcément un père 'ET' (sauf la racine).
Exemple :
- Si l'on rencontre A, B, C -> Q, on génère la branche suivante : Q? - ET(A?, B?, C?) ;
- S'il n'y a qu'un fils : F -> A, la branche devient : Q? - ET(A? - ET(F?), B?, C?) ;
- Si maintenant on trouve G, H -> A, on a donc A par F OU G, H : on remplace A? - ET(F?) par A? - OU(ET(F?), ET(G?, H?)) ;
- La branche devient donc : Q? - ET(A? - OU(ET(F?), ET(G?, H?)), B?, C?).
Algorithme :
Procédure APPLIQUER(R, B, STOP)
STOP <- Faux ;
EP <- Prémisses de R qui n'appartiennent pas à BF ;
Si EP Vide Alors Appel SIMPLI_BUT_PROUVE(BUT, STOP) ;
Sinon Appel ACCROCHER(EP, B) ;
Retour ;
Procédure ACCROCHER(EP, B)
' EP : Ensemble des branches inférieures de ARBO : prémisses de R restantes à prouver
Créer ARBO ;
NAT(ARBO) <- 'ET' ;
Pour chaque feuille de ARBO : ' F : Feuille
NAT(F) <- 'BUT' ;
R_INTERD <- Vide ;
Calculer NOTE(F) ;
Si NOTE(F) >= SEUIL Alors ETAT(F) <- 'ACTIF' ;
Sinon ETAT(F) <- 'INHIBE' ;
Au cas où :
Fils(B) = 0 : ACCROCHER ARBO à B ; ' Feuille
NAT(FILS(B)) = 'OU' : ACCROCHER ARBO à ce 'OU' ;
NAT(FILS(B)) = 'ET' : ACCROCHER 'OU' entre 'ET' et ARBO ;
Retour ;
Procédure SIMPLI_BUT_PROUVE(BUT, STOP)
' Simplification locale seulement : il faudrait simplifier toutes les occurrences de B
Si BUT = Q Alors STOP <- Vrai ; Retour ;
Sinon BF <- BF + BUT ;
P <- PERE(BUT) ' Un 'ET' sauf la racine
Si P à au moins 2 fils Alors Décrocher le sous-arbre racine de BUT ;
Sinon, Si PERE(P) est un but B1 Alors
On décroche le noeud 'ET' ;
puis on Appel SIMPLI_BUT_PROUVE(B1, STOP) ; ' car B1 vient d'être prouvé
Sinon, Si PERE(P) est un noeud 'OU' dont le PERE est B2 Alors
On décroche le noeud 'OU' ;
puis on Appel à nouveau SIMPLI_BUT_PROUVE(B2, STOP) ; ' car B2 vient d'être prouvé
Retour ;
Procédure DEDUIRE(Q)
Si Q Appartient à BF Alors Ecrire "Succès" ;
Sinon
ARBRE <- Q ;
NAT(Q) <- 'BUT' ;
R_INTERD(Q) <- Vide ; ' Cf. marque bleue
SEUIL <- NOTE(Q) ;
ETAT(Q) <- 'ACTIF' ;
Appel CYCLE() ;
Retour ;
Procédure CYCLE()
Appel CHOIX_BUT(BUT, BUT_TROUVE) ;
' BUT_TROUVE = Vrai : BUT = noeud actif but ayant la meilleure note
' BUT_TROUVE = Faux : aucun noeud actif but de note >= seuil
Si BUT_TROUVE = Faux Alors
Si Arbre ne contient aucun but inhibé de note >= 0 Alors Ecrire "échec" ; Retour ;
Sinon Appel BAISSER_SEUIL() ; ' Diminuer le seuil pour réactiver certains noeuds
Si BUT_TROUVE = Vrai Alors
' Retourner la meilleure règle de BR-R_INTERD(BUT) Si R_TROUVE = Vrai
Appel CHOIX_REGLE(BUT, R, R_TROUVE) ;
Si R_TROUVE = Faux Alors
Si BUT = Q Alors Ecrire "échec" ; Retour ;
' Ce noeud est tué : il ne sera jamais réactivé
Sinon Etat(BUT) <- Inhibé ; Note(N) <- -1 ;
Si R_TROUVE = Vrai Alors
R_INTERD(BUT) <- R ;
Appel APPLIQUER(R, BUT, STOP) ;
Si STOP = Vrai Alors Ecrire "Succès" ; Retour ;
Appel CYCLE() ;
Retour ;
Critique de ce moteur :
- Tel qu'il est, ce moteur ne présente aucun focus d'attention (au niveau but), la procédure de choix de but peut retourner un but de n'importe où dans l'arbre, de sorte qu'une explication de son raisonnement semblera opaque. Amélioration : développer à priori en profondeur et seulement ailleurs si on le juge nécessaire, il faut modifier la procédure CHOIX_BUT. La technique à employer repose sur l'utilisation d'une pile des buts produits et tant que NOTE(Sommet_pile) >= Seuil, Alors CHOIX_BUT retournera Sommet_pile ;
- Lorsqu'un BUT est prouvé, on a une simplification locale autour du noeud BUT ; or il faudrait chercher toutes les occurrences de BUT et simplifier partout (appel récursif sur B1 et B2 : traiter aussi toutes les occurrences de B1 et B2). Attention, il y a peut être beaucoup de travail pour cette simplification ;
- Lorsque l'on ne sait pas prouver un BUT (improuvable), on n'essaie pas de propager BUT dans l'arbre (amélioration moins puissante que la précédente) ;
- Au niveau de la propagation, ce moteur suppose que l'on a la possibilité de propager tout ce que l'on peut démontrer (ne traite pas les problèmes du type casserole vide).
Par Patrice Dargenton : patrice.dargenton@free.fr