Les mécanismes d'exploitation

d'un système expert

____________________________________________________________________________

• chaînage avant
• chaînage arrière
• chaînage bidirectionnel
• exercices
• tests

____________________________________________________________________________

On considère le système expert " pâtisserie "

Comment exploiter ce système expert ?

• Démarche 1 : Avec les ingrédients (les faits) qu'est-ce que je peux faire ?
• Démarche 2 : Est-ce que je peux faire une tarte aux abricots ?

Description de la démarche 1, le " chaînage avant " :

C'est un mécanisme d'exploitation des règles guidé par les faits. C'est la traduction du modus ponens :
si f1 est vrai et f1 -> f2 alors f2 est vrai.
Le chaînage avant traduit un raisonnement déductif :

• de f1 sont déduits f2 et f3
• de f2 sont déduits f4 et f5
• etc ...

• Règle 1 : est-elle applicable ?
  Oui (tous les faits sont dans la base des faits)
  Le fait pâte est donc rajouté dans la base des faits et la règle 1 est désactivée.
  
  

  Nouvelle base des faits :	base des règles utilisables :
  Pommes Poires Abricots Farine Beurre Sucre Sel Pâte	R2 R3 R4 R5 R6

• Règle 2 : est-elle applicable ?
  Oui
  Le fait pommes sucrées est ajouté dans la base des faits et la règle 2 est désactivée.
  
  

  Nouvelle base des faits :	base des règles utilisables :
  Pommes Poires Abricots Farine Beurre Sucre Sel Pâte Pommes sucrées	R3 R4 R5 R6

  
  
  
• De même, les règles 3, 4 et 5 sont sélectionnées et exécutées.
  
  

  Nnouvelle base des faits :	base des règles utilisables :
  Pommes Poires Abricots Farine Beurre Sucre Sel Pâte Pommes sucrées Tarte aux pommes Tarte aux abricots Tarte aux poires	R6

  
  
  
• Règle 6 : elle ne peut pas être exécutée.
  Le fait "cerises" n'existe pas dans la base des faits.
  
  
• Le mécanisme ne peut plus effectuer de déductions et le moteur s'arrête.

Description de l'algorithme :

• Existe-t-il une règle applicable ? : ceci consiste à trouver parmi toutes les règles celles dont la partie condition est vraie et à en choisir une à l'aide d'une fonction de choix.
  
  
• Appliquer cette règle : une fois la règle choisie, le programme exécute sa partie action ou conclusion.
  Désactiver cette règle : en logique des propositions, il est inutile d'appliquer plus d'une fois la même règle. Ainsi, les règles utilisées sont rendues inactives.
  
  
• Le but souhaité est-il démontré ? : cet algorithme suppose que l'utilisateur du moteur veut obtenir une proposition particulière, but du problème. Si ce fait vient d'être obtenu, il est inutile de poursuivre le travail.
  
  
• Dans le cas où aucun but particulier n'est demandé, le moteur fonctionne jusqu'au moment où aucune règle n'est applicable (condition d'arrêt). On dit alors que le moteur fonctionne par saturation.
  

Description de la démarche 2, le "chaînage arrière":

Est-ce que je peux faire une tarte aux abricots ?

Le chaînage arrière est un mécanisme d'exploitation guidé par les buts. Il traduit la règle du modus tollens.
Si est non vrai et si p implique q alors p est non vrai.
Le chaînage arrière traduit un raisonnement déductif :

• de f4 est déduit f3
• de f3 est déduit f1

On part d'un but qu'on cherche à vérifier.
But : Tarte aux abricots.

• Considérons la règle 6 : les prémisses sont-elles vérifiées dans la base des faits ?
  La première prémisse abricot est vérifiée.
  La deuxième prémisse doit être vérifiée ; on vérifie s'il existe une règle qui a pour but pâte :
  Oui, la règle 1.
• On considère maintenant la règle 1 : les prémisses sont vérifiées
• Donc, on peut conclure que le but tarte aux abricots est vérifié.

Algorithme de chaînage arrière :

Le système recherche, par la méthode du chaînage arrière, si le but souhaité peut être démontré à l'aide des règles présentes dans la base de règles.

L'algorithme est le suivant :

Avec comme définition de VERIFIER (fait) :

et avec comme définition de PROUVER (fait) :

Troisième démarche : le chaînage mixte

Le chaînage mixte utilise le raisonnement inductif et le raisonnement déductif. L'exemple suivant montre une recherche qui devient de plus en plus complexe.

Exemple 2.1 :

Base de faits état initial :
Les_Saintes

Règle déclenchée R5.
Base de faits état 1 cycle :
Les_Saintes
Hôtel Paradisio

Règle déclenchée R9.
Base de faits état 2 cycles :
Les_Saintes
Hôtel Paradisio
Caraïbes

Le moteur est maintenant bloqué en chaînage avant. Il n'existe pas de prémisse qui contienne Caraïbes.
Il passe donc en chaînage arrière mais il n'existe pas de règle activable ayant une partie droite (conclusion) qui contienne Caraïbes.
Le moteur passe à nouveau en chaînage avant.

Les règles activables sont R1, R2, R3, R4, R6, R7,R8.
La règle R6 est sélectionnée et activée.
Elle permet de déduire tourisme chaud.

etc...

Graphe du chaînage mixte :

Exercices :

Exercice 1:

Compléter les solutions proposées dans les cas chaînage avant et chaînage arrière pour le système suivant :

Dans chaque noeud figure le contenu de la base des faits.

Question : peut-on obtenir le fait H ?

Chaînage avant

vérifier son travail : consulter la solution.

 

Chaînage arrière

vérifier son travail : consulter la solution.

Exercice 2 :

1. Résoudre le problème suivant par chaînage avant :

On cherche à démontrer C

Solution

2. Résoudre le problème suivant par chaînage arrière :

On cherche à démontrer C

Solution

3. Résoudre le problème suivant par chaînage arrière avec "backtracking" :

On cherche à démontrer C

Solution