Lab 3 : Moteur d’inférence à chaînage avant avec variables

Dans cette série, vous allez construire un moteur d’inférence à chaînage avant qui va autoriser les variables dans les règles.

Dans un premier temps, vous allez construire un filtre qui permet de comparer deux expressions, dont l’une peut contenir des variables. Ensuite en utilisant votre filtre, vous implémenterez un moteur d’inférence avec variables. Enfin, vous aurez la possibilité d’implémenter un unificateur et de le tester sur votre moteur à chaînage avant.

Comme vu dans le cours, un unificateur permet aussi de comparer deux expressions. La différence fondamentale entre les deux est le fait qu’un unificateur autorise les variables dans les deux expressions, ce qui permet d’utiliser l’unificateur dans le chaînage arrière.

Durée estimée : 2 heures

Les faits et règles

Dans la série 2, vous avez manipulé des faits simples et des règles sans variables. Dans cette série, les faits pourront être composés, et les règles pourront contenir des variables. De plus, nous utiliserons le terme proposition pour parler de faits et règles. Concrètement, une proposition peut être :

  • un atome (un symbole représentant soit une variable, soit une valeur)
  • une liste contenant des atomes ou/et d’autres listes.

Par conséquent, les faits composés seront une liste d’axiomes. Voici deux exemples :

['Paul']
['bas-salaire', 'Paul']

Et voici deux exemples de règles :

[[['pas-d-enfants', '?x']],['reduc-enfant', '0','?x']]
[[['reduc-enfant', '100','?x'],['reduc-loyer', '200', '?x'],['long-trajet', '?x']],['reduc-trajet', '0', '?x']]

Par convention, une variable est un symbole dont le nom commence par un point d’interrogation, c’est à dire : '?x'.

Exercice 1 : Le filtrage

La technique du filtrage permet d’établir des correspondances entre deux propositions. Plus précisément, un filtre établit les substitutions variables-valeurs qui permettent de retrouver une proposition sans variables (le datum) à partir d’une autre (le pattern) pouvant contenir des variables.

Dans un premier temps, nous allons écrire une fonction filtrer qui implémente l’algorithme vu en cours. La fonction filtrer retournera :

  • un dictionnaire de substitutions variable-valeur, {'?x':'toto', ...,     '?y':'titi'}, dans le cas où le processus aboutit avec des substitutions,
  • un dictionnaire vide, {}, si le processus réussit sans aucune substitution, c’est à dire que les deux propositions sont identiques,
  • un échec sinon, ECHEC.

Une substitution sera une définition de dictionnaire dont la clé représente une variable et la définition correspond à la valeur à substituer (ex : {' ? x’:'toto'}).

Format d’appel : filtrer(datum, pattern), où

  • datum est une proposition sans variables.
  • pattern est une proposition pouvant contenir des variables.

Exemples :

filtrer(['vincent', 'est un', 'doctorant'], ['?x', 'est un', 'doctorant'])
   -> {'?x': 'vincent'}

filtrer(['vincent', 'est un', 'doctorant'] , ['vincent', 'est un', 'doctorant'])
  -> {}

filtrer(['vincent', 'est un', 'doctorant'], ['?x', 'est un', '?x'])
  -> ECHEC

Le fichier filtreurTemplate.py fournit le squelette du module de filtrage. Commencez par le copier chez vous et renommez-le filtreur.py. Ce fichier définit notamment la fonction testVariable, qui vous dit si l’argument est une variable, et la constante echec qui indique l’échec d’une tentative de filtrage.

Le fichier contient aussi des fonctions déjà implémentées qui permettent de manipuler des substitutions :

  • construitSubstitution: construit et retourne une substitution entre une variable '?variable' et une proposition sans variable datum. (ex : {'?VARIABLE': DATUM})
  • retourneVariable: retourne la variable de la substitution.
  • retourneValeur : retourne la valeur de la substitution.
  • trouveSubstitution : retourne la substitution {'?VARIABLE': DATUM} pour une variable donnée si elle existe dans la liste des substitutions passée en paramètre, False sinon.
  • unionSubstitutions : fait l’union de deux substitutions passées en paramètres, mais retourne echec si l’un des arguments n’est pas une substitution. (Note : si une même variable est présente dans les deux substitutions avec deux valeurs différentes, la première valeur est écrasée par la deuxième.)

Rappel

Voici quelques fonctions utiles pour manipuler des dictionnaires.

En complétant le squelette, vous devrez écrire plusieurs fonctions avant d’écrire le filtrage. Nous les expliquons ci-après.

Substitution de variables

L’algorithme de filtrage exige que lorsqu’un ensemble de substitutions a été établi, il faille remplacer les variables de cet ensemble par leur valeur dans le reste du pattern avant de poursuivre le filtrage.

Écrivez donc une fonction substitueVariables, qui prend en entrée une proposition avec des variables et un dictionnaire de substitutions. Elle retournera la proposition dont les variables qui possèdent une substitution auront été remplacées par leur valeur correspondante.

Exemples :

substitueVariables(['?x', 'est un', 'doctorant'] , {})
   -> ['?x', 'est un', 'doctorant']

substitueVariables(['?x', 'est un', 'doctorant'] , {'?y':'michael'})
  -> ['?x', 'est un', 'doctorant']

substitueVariables(['?x', 'est un', ['?a']] , {'?z': 'paolo', '?y': 'michael', '?x': 'vincent'})
  -> ['vincent', 'est un', ['?a']]

substitueVariables('doctorant', {'?z': 'paolo', '?y': 'michael', '?x': 'vincent'})
  -> doctorant

Le fichier testSubstitueVariables.py vous permet de tester votre fonction.

Astuce

Si vous devez modifier la liste ma_liste sur laquelle vous itérez, utilisez l’opérateur de copie de surface, c’est à dire : ma_liste[:]

Filtrage

Vous avez maintenant tout ce qu’il faut pour définir la fonction filtrer.

L’algorithme de filtrage a été vu en cours. Rappelons-le :

filtrer(datum, pattern)
    1. IF pattern==[] AND datum==[]: RETURN {}.
    2. ELSE IF pattern==[] OR datum==[]: RETURN échec.
    3. ELSE IF pattern est un atome:
    4.    IF pattern et datum sont identiques: RETURN {}.
    5.    ELSE IF pattern est une variable: RETURN {pattern:datum}.
    6.    ELSE RETURN échec.
    7.    END IF
    8. ELSE IF datum est un atome: RETURN échec.
    9. ELSE
   10.    F1 <- premier élément de datum
   11.    T1 <- reste de datum
   12.    F2 <- premier élément de pattern
   13.    T2 <- reste de pattern
   14.    Z1 <- filtrer(F1, F2)
   15.    IF Z1 = échec, RETURN échec.
   16.    G1 <- T1
   17.    G2 <- remplacer les variables de T2 selon les substitutions de Z1.
   18.    Z2 <- filtrer(G1, G2)
   19.    IF Z2 = échec, RETURN échec.
   20.    RETURN {Z1 UNION Z2}
   21. END IF
END  filtrer

Le fichier testFiltrer.py vous permet de tester votre fonction.

Note

filtrer retourne un dictionnaire de substitutions si le filtrage a réussi, ECHEC sinon. Il faut donc, au pas 5 de l’algorithme, retourner un dictionnaire contenant la substitution trouvée, c’est à dire : {pattern:datum}.

Astuce

Utilisez la constante globale ECHEC pour indiquer un échec.

La vraie fonction d’interface : patternMatching

La fonction filtrer n’est pas très pratique pour un programme hôte, ceci pour deux raisons :

  1. Il n’est pas possible de lui fournir en entrée un dictionnaire de substitutions déjà établies (que nous appelons environnement).
  2. Il est assez lourd de s’assurer que le filtre ait réussi.

Dans le processus de chaînage avant que vous allez écrire dans l’exercice 3, chaque condition d’une règle doit être vérifiée avant de pouvoir être utilisée. Cela implique que chaque condition doit être filtrée avec succès par un fait existant. Comme il peut y avoir plusieurs conditions, il est nécessaire de respecter les substitutions obtenues lors des filtrages précédents. Il faut donc pouvoir fournir à la fonction de filtrage une liste de substitutions déjà établies.

Vous devez donc écrire une fonction patternMatching qui permet de prendre en compte un environnement de substitutions déjà existantes.

Voici une liste d’exemples qui prennent en compte des environnements préexistants :

patternMatching(['vincent', 'est un', 'doctorant'],['?x', 'est un', 'doctorant'] , {'?y':'doctorant'})
  -> {'?y': 'doctorant', '?x': 'vincent'}

patternMatching(['vincent', 'est un', 'doctorant'], ['?x', 'est un', '?y'], {'?y':'doctorant'})
  -> {'?y': 'doctorant', '?x': 'vincent'}`

patternMatching(['vincent', 'est un', 'doctorant'], ['?x', 'est un','doctorant'] , 'ECHEC')
  -> ECHEC
patternMatching('vincent', '?x', 'ECHEC')
  -> ECHEC
patternMatching('vincent', '?x', {})
  -> {'?x': 'vincent'}

Écrivez une fonction patternMatching qui prend deux expressions (un datum et un pattern) et un environnement (argument optionnel) en paramètres et qui retourne un nouvel environnement, ou ECHEC, suivant que le « matching » a réussi ou échoué. Cette fonction s’appuiera bien évidemment sur filtrer et substitueVariables. N’oubliez pas que ces deux fonctions utilisent un dictionnaire de substitutions !

Le fichier testPatternMatching.py vous permet de tester votre fonction.

Note

Une fois assuré(e) que l’environnement est valable, commencez par remplacer les variables de la proposition pattern avec les définitions de l’environnement.

Note

En cas de non ECHEC, le nouvel environnement devra contenir l’ancien environnement et toutes les nouvelles substitutions trouvées lors du filtrage.

Rappel

Les arguments optionnels d’une fonction Python ont la syntaxe argument=valeur. Lorsque le programme hôte ne les fournit pas, ces arguments optionnels valent {}, sauf si une valeur par défaut est fournie (voir le squelette du programme).

Exercice 2 : Chaînage avant avec variables

Grâce au module de filtrage que nous avons développé, nous pouvons maintenant réaliser une nouvelle version de notre moteur d’inférence à chaînage avant : nous pouvons traiter des règles avec des variables.

chainageAvantAvecVariables(faitsDepart, faits, regles)

  1. Q <- faitsDepart
  2. WHILE Q n'est pas vide DO
  3.     q <- premier (Q), Q <- reste (Q)
  4.     IF q n'est pas dans faits THEN
  5.         ajouter q à faits
  6.         imprimer q
  8.         FOR EACH règle r de règles DO
  9.             IF c = conditions(r) and patternMatching(q,c)!= échec THEN
 10.                 FOR EACH environnement déduit de  patternMatching(q, c) DO
 11.                     environnements2 <- retourne les environnements déduits
...      des conditions restantes de r  tout en respectant environnement
 12.                     n <- instancie la conclusion de r tout en respectant
...      environnements2
 13.                     ajouter n en queue de Q
 14.                 END FOR
 15.             END IF
 16.         END FOR
 17. END WHILE
END chainageAvantAvecVariables

Le fichier chainageAvantAvecVariablesTemplate.py fournit le squelette du fichier, qui est très similaire à celui de la série 2 (chainageAvantSimple). Commencez par le copier chez vous et renommez-le chainageAvantAvecVariables.py. Ensuite, codez les fonctions suivantes :

faitSatisfaitUneCondition

Vérifie qu’un seul fait passé en paramètre est un déclencheur des conditions d’une règle, les conditions étant aussi passées en paramètres. Cette fonction, via le patternMatching, permet de vérifier qu’un nouveau fait est un déclencheur d’une nouvelle règle.

Attention

Cette fonction doit vérifier toutes les conditions de la règle. Pour chaque condition vérifiée, la fonction retournera les substitutions trouvées et les autres conditions à satisfaire.

Par exemple, imaginez la règle suivante :

`(père ?x ?y) AND (père ?y ?z) => (grand-père ?x ?z)`

Le fait (père Jean Paul) peut satisfaire la première ou la seconde condition :

patternMatching(['père', 'Jean', 'Paul'] , ['père', '?x', '?y'])
  -> {'?x':'Jean', '?y':'Paul'}
patternMatching(['père', 'Jean', 'Paul'] , ['père', '?y', '?z'])
  -> {'?y':'Jean', '?z':'Paul'}

faitSatisfaitUneCondition prend 2 arguments :

  1. un fait à vérifier
  2. les conditions d’une règle (sous forme d’une liste: [‘cond1’,....,’condn’])

et retourne deux valeurs :

  1. Une liste d’environnements (un environnement étant un dictionnaire de substitutions) réussis qui correspond à toutes les substitutions possibles entre une condition de la règle par le fait.
  2. Une liste de la liste des conditions restant à satisfaire pour chaque patternMatching réussi entre une condition et le fait.

Lorsque le fait passé en paramètre ne permet pas de satisfaire une seule condition, c’est à dire le fait n’est pas un déclencheur, le résultat retourné sera donc [[],[]].

Plus concrètement, voici quelques exemples pour vous aider.

faitSatisfaitUneCondition(['pere','jean','paul'],[['pere','?x','?y'],['pere','?y','?z']])
  ->[[{'?y': 'paul', '?x': 'jean'}, {'?z': 'paul', '?y': 'jean'}], [[['pere', '?y', '?z']], [['pere', '?x', '?y']]]]

faitSatisfaitUneCondition(['pere','jean','paul'],[['fils','?x','?y'],['pere','?y','?z'],['mere','?x','?y']])
  ->[[{'?z': 'paul', '?y': 'jean'}], [[['fils', '?x', '?y'], ['mere', '?x', '?y']]]]

faitSatisfaitUneCondition(['tonton','jean','paul'],[['fils','?x','?y'],['pere','?y','?z'],['mere','?x','?y']])
   -> [[], []]

Le fichier testFaitSatisfaitUneCondition.py vous permet de tester votre fonction.

Note

Pour utiliser la fonction patternMatching du fichier filtre.py, utilisez la notation suivante: paquetage.patternMatching(). Notez que la variable globale paquetage fait référence au module filtre. Pour éviter de ré-écrire du code inutile, nous utiliserons cette variable afin de pouvoir utiliser le module d’unificateur (à faire dans l’exercice 3) dans le moteur de chaînage avant.

Note

N’oubliez pas de faire des copies en profondeur de votre fait, et de la liste des conditions de la règle passée en paramètre.

satisfaitUneCondition

satisfaitUneCondition vérifie qu’une condition passée en paramètre (qui sera une des conditions restantes générées par faitSatisfaitUneCondition) peut être satisfaite par des faits existants dans une liste des faits, tout en respectant l’environnement déjà déduit (de faitSatisfaitUneCondition).

Cependant chaque environnement de la liste fournie en paramètre peut conduire à plusieurs environnements lors du pattern matching des conditions restantes avec des faits de la liste, puisqu’une condition peut être remplie par plusieurs faits différents. Donc, cette fonction va vérifier la validité de la condition passée en paramètre en essayant toutes les substitutions (par du pattern matching) par des faits de la liste des faits, et ce, pour chaque environnement passé en paramètre. Elle retournera donc une liste d’environnements valides.

satisfaitUneCondition prend en entrée 3 paramètres :

  • condition: une condition qui doit être remplie.
  • faits: une liste des faits
  • environnements : une liste d’environnements déjà établis pour les conditions précédentes.

Voici un petit exemple pour clarifier les choses :

faits = [['a', 'and', 'b'],['b', 'and', 'b']]
satisfaitUneCondition(['?x', 'and','b'], faits, [{'?y':'b'}])
    -> [{'?y': 'b', '?x': 'a'}, {'?y': 'b', '?x': 'b'}]

Le fichier testSatisfaitUneCondition.py vous permet de tester votre fonction.

satisfaitConditions

satisfaitConditions vérifie maintenant qu’une liste de conditions (toutes les conditions restantes générées par faitSatisfaitUneCondition) peut être satisfaite par des faits existant dans une liste des faits, tout en tenant compte de l’environnement à respecter (l’un de ceux établis lors de l’appel de faitSatisfaitUneCondition).

satisfaitConditions implémente l’algorithme suivant:

satisfaitConditions(conditions, faits, environnement)
    environnements <- [environnement]
    FOR EACH condition c de conditions DO
        IF environnements est vide THEN RETURN [].
        environnements <- satisfaitUneCondition(c, faits, environnements)
    END DO
    RETURN environnements
END satisfaitConditions

où conditions est l’une des conditions restantes générées par faitSatisfaitUneCondition, faits est la liste des faits, et environnement est l’environnement correspondant. La fonction retourne une liste d’environnements correspondant au pattern matching réussi d’un ensemble de conditions restantes d’après un environnement de départ.

faits=[['a', 'et', 'b'],['b', 'et', 'b']]

satisfaitConditions([['?x', 'et','?y'], ['?x', 'et','?x']], faits, {'?y':'b'})
    -> [{'?y': 'b', '?x': 'b'}]

satisfaitConditions([['?x', 'et','?y'],['?x', 'et','?z']], faits, {'?y':'b'})
   -> [{'?z': 'b', '?y': 'b', '?x': 'a'}, {'?z': 'b', '?y': 'b', '?x': 'b'}]

Le fichier testSatifaitConditions.py vous permet de tester votre fonction.

instantieVariables

Une fois que les conditions d’une règle ont été validées, il faut instancier la conséquence de la règle au moyen de la liste des environnements obtenue, afin de créer de nouveaux faits. La fonction instantieVariables prend comme paramètre une proposition et une liste d’environnements, et retourne une liste de nouveaux faits (un par environnement).

instantieVariables(['?x',['?y', '?z']],[{'?x':'X','?y':'Y'},{'?x':'X','?z':'Z'}])
   -> [['X', ['Y', '?z']], ['X', ['?y', 'Z']]]

Le fichier testInstantieVariables.py vous permet de tester votre fonction.

Indication : utilisez la fonction substitueVariables.

Chaînage avant avec filtrage

Enfin, implémentez l’algorithme de chaînage avant décrit au début de l’exercice, et testez-le sur le fichier impots2.py.

Exercice 3 : L’unification [OPTIONNEL]

Nous allons maintenant construire un unificateur. C’est un outil analogue à un filtre mais bien plus puissant. L’objectif d’un unificateur est de comparer deux expressions pouvant toutes deux contenir des variables, contrairement au filtre qui comparait deux expressions, dont seulement l’une contient des variables ; l’unificateur est donc une version généralisée d’un filtre. Il fournit comme résultat les correspondances entre les deux propositions sous la forme de substitutions variable-valeur (lorsqu’il y en a).

Pour mieux comprendre l’unification, voyons quelques exemples :

unifier(['vincent', 'est un', 'doctorant'],['vincent', 'est un', 'doctorant'])
   -> {}

unifier(['vincent', 'est un', 'doctorant'],['micheal', 'est un', 'doctorant'])
   -> ECHEC

unifier(['foo', '?x', ['?y', 'bar', 'jean']],['foo', 'jean', ['marc', 'bar', '?x']])
   -> {'?y': 'marc', '?x': 'jean'}
 unifier(['p', '?x', ['f', '?y']],['p', ['f','a'], '?x'])
   -> {'?y': 'a', '?x': ['f', 'a']}`

Nous allons utiliser les mêmes conventions que lors du filtrage, à savoir qu’une substitution est une définition de dictionnaire entre une variable et une valeur, et qu’un environnement est un dictionnaire contenant des substitutions. La fonction unifier travaillera avec une liste de substitutions (à l’image de filtrage) tandis que patternMatching utilisera un environnement (comme patternMatching pour le filtrage).

Copiez chez vous unificateurTemplate.py. C’est un squelette (bien rempli) d’un unificateur dont vous allez remplir quelques trous.

Substitution de variables

La fonction substitueVariables permet d’instancier une proposition d’après un ensemble de substitutions variable-valeur. Ici, cette fonction est légèrement plus compliquée que celle pour le filtrage : en effet, une variable peut être remplacée par une définition de substitution, contenant elle-même des variables. Il faut donc veiller à remplacer toutes les variables de la valeur d’une substitution !

Exemples :

substitueVariables(['?x', 'est un', 'doctorant'] , {})
  -> ['?x', 'est un', 'doctorant']

substitueVariables(['p', '?x'] , {'?y':['g','?z'],'?x':['f','?y'],'?z':['a']})
  -> ['p', ['f', ['g', ['a']]]]

substitueVariables(['p', '?x'] , {'?y':['g','?z'],'?x':['f','?y'],'?z':['?q']})
   -> ['p', ['f', ['g', ['?q']]]]

Indication : inspirez-vous de la même fonction que vous avez écrite pour le filtrage et pensez récursif.

Unification

Vous avez maintenant tout ce qu’il faut pour définir la fonction unifier.

L’algorithme d’unification a été vu en cours. Rappelons-le:

unifier(proposition1, proposition2)
    1. IF proposition1 ou proposition2 est un atome THEN
    3.     Echanger proposition1 et proposition2 au besoin pour que proposition1 soit un atome
    4.     IF proposition1 et proposition2 sont identiques THEN
    5.        RETURN {}.
    6.     ELSE IF proposition1 est une variable THEN
    7.         IF proposition1 apparaît dans proposition2 THEN RETURN echec.
    8.         ELSE RETURN la substitution {proposition1:proposition2}.
    9.         END IF
   10.     ELSE IF proposition2 est une variable THEN RETURN la substitution {proposition2:proposition1}.
   11.     ELSE RETURN échec.
   12. ELSE
   13.     F1 <- premier élément de proposition1
   14.     T1 <- reste de proposition1
   15.     F2 <- premier élément de proposition2
   16.     T2 <- reste de proposition2
   17.     Z1 <- unifier(F1, F2)
   18.     IF Z1 = échec THEN RETURN échec END IF
   19.     G1 <- remplacer les variables de T1 selon les substitutions de Z1
   20.     G2 <- remplacer les variables de T2 selon les substitutions de Z1
   21.     Z2 <- unifier(G1, G2)
   22.     IF Z2 = échec THEN RETURN échec END IF
   23.     RETURN { Z1 UNION Z2 }
   12. END IF
END unifier

Le fichier testUnifier.py vous permet de tester votre fonction.

La vraie fonction d’interface : patternMatching

Comme pour la fonction filtrer, unifier n’est pas très pratique pour un programme hôte.

Vous devez donc écrire une fonction patternMatching qui permet de prendre en compte un environnement de substitutions déjà existantes.

Voici une liste d’exemples qui prennent en compte des environnements préexistants :

patternMatching(['foo', '?x', ['?y', 'bar', 'jean']], ['foo', 'jean', ['marc', 'bar', '?x']] ,{'?y':'marc'})
   -> {'?y': 'marc', '?x': 'jean'}

patternMatching(['foo', '?x', ['?y', 'bar', 'paul']], ['foo', 'jean', ['marc', 'bar', '?x']],{})
   -> ECHEC

patternMatching(['frere', '?x', '?y'], ['frere', '?y', '?z'], {'?z':'?x'})
   -> {'?z': '?x', '?x': '?y'}

Écrivez une fonction patternMatching qui prend deux expressions pouvant contenir des variables et un environnement (argument optionnel) en paramètres et qui retourne un nouvel environnement, ou ECHEC, suivant que le « matching » a réussi ou échoué. Cette fonction s’appuiera bien évidemment sur unifier et substitueVariables. N’oubliez pas que ces deux fonctions utilisent un dictionnaire de substitutions !

Le fichier testPatternMatching2.py vous permet de tester votre fonction.

Indication : Une fois assuré(e) que l’environnement est valable, commencez par remplacer les variables des deux propositions avec les définitions de l’environnement.

Chaînage avant avec unificateur

Essayez d’utiliser l’unificateur à la place du filtre ; que constatez-vous et pourquoi ?

Indication : Est-il vraiment nécessaire d’utiliser un unificateur dans le chaînage avant ?