TP 5 et 6 : Illustration du cours Système à Base de Connaissances

Etude pour la réalisation d'un moteur d'inférence en PROLOG

Objectif des deux séances de TP

BDR de test

On donne une base de règles à titre d'exemple :

• r1 si mange_viande alors carnivore
• r2 si dents_pointues et griffes et yeux_avant alors carnivore
• r3 si mange_herbe alors non carnivore
• r4 si mammifere et sabots alors ongule
• r5 si mammifere et rumine alors ongule
• r6 si mammifere et carnivore et brun et taches alors guepard
• r7 si mammifere et carnivore et brun et raies alors tigre
• r8 si ongule et long_cou et longues_pattes et taches alors girafe
• r9 si ongule et raies alors zebre
• r10 si oiseau et long_cou et longues_pattes et noir_et_blanc et non vol alors autruche
• r11 si oiseau et nage et noir_et_blanc et non vole alors pingouin
• r12 si oiseau et vole alors albatros
• r13 si poils alors mammifere
• r14 si lait alors mammifere
• r15 si plumes alors oiseau
• r16 si vole et pond_oeufs alors oiseau

Premier moteur en chaînage avant

On veut réaliser un moteur d'inférence d'ordre zéro, fonctionnant en chaînage avant, en régime irrévocable et monotone, et qui ne constitue pas d'ensemble de conflit (dès qu'une règle est déclenchable, elle est déclenchée).

1. Définir la base de règles grâce à un prédicat regle/1 :

   regle(ri) :- si(Liste de prémisses), alors(Liste de conclusions).

2. Définir un prédicat permettant à l'utilisateur d'initialiser la base de faits. On utilisera le prédicat assert pour ajouter vrai(Fait) pour les faits positifs et faux(Fait) pour les faits négatifs.
3. Définir un prédicat saturer qui sature la base de règles et produit une trace de son fonctionnement.

4. L'algorithme utilisé pour ce moteur sera le suivant :

   Changement <-- Vrai
   Tant que Changement est Vrai
       Changement <-- Faux
       Boucle sur les règles : soit R une règle de BaseRègles
           Si      R n’est pas marquée et si les prémisses de R appartiennent à BaseFaits
           Alors   ajouter les conclusions de R à BaseFaits
                   changement <-- Vrai
                   marquer R
           FinSi
       FinBoucle
   FinTantQue

Un exemple d'exécution souhaitée est :

?- faits([plumes,non(vole),nage,noir_et_blanc,mange_herbe]).
   Yes
?- saturer.
   r3
   non(vole) non(carnivore) plumes nage noir_et_blanc mange_herbe
   r15
   non(vole) non(carnivore) plumes nage noir_et_blanc mange_herbe oiseau
   r11
   non(vole) non(carnivore) plumes nage noir_et_blanc mange_herbe oiseau pingouin
   Yes

Amélioration (OPTION)

On distingue deux catégories de faits

• les faits "terminaux", qui ne figurent jamais en partie gauche d'une règle,
• les faits "observables", qui ne figurent jamais en partie droite d'une règle.

1. Définir le prédicat terminal(F) (respectivement observable(F)) vrai si le fait F est terminal (resp. observable).
2. Il est possible que la base de faits fournie par l'utilisateur ne permette pas de conclure sur un fait terminal. Dans ce cas, on n'a pas répondu à l'utilisateur sur l'animal qu'il observe (dans notre exemple). On veut donc lui poser des questions afin de conclure sur un fait terminal. Pour cela, on procède en deux temps :
   • On cherche une règle "presque déclenchable", c'est-à-dire dont toutes les prémisses sont vraies sauf une, qui est inconnue et qui porte sur un fait observable.
   • On essaie de déclencher cette règle, en posant une question à l'utilisateur sur la prémisse inconnue. L'utilisateur peut répondre "oui", "non", ou "je ne sais pas". Dès qu'on a une réponse "oui" ou "non" à une de nos questions, on peut ajouter un fait à la base de faits et relancer le moteur. Si l'on n'arrive toujours pas à conclure sur un fait terminal, il faut réitérer le processus. Attention à ne pas poser deux fois la même question à l'utilisateur.

Exemple d'exécution :

   ?- faits([brun,dents_pointues,griffes]).
   Yes
   ?- go.
   Est-ce que mange_viande ? (o/n/i)
   |: i.
   Est-ce que yeux_avant ? (o/n/i)
   |: o.
   r2
   brun dents_pointues griffes yeux_avant carnivore 
   Est-ce que mange_herbe ? (o/n/i)
   |: n.
   Est-ce que poils ? (o/n/i)
   |: o.
   r13
   non(mange_herbe) brun dents_pointues griffes yeux_avant carnivore poils mammifere    
   Est-ce que sabots ? (o/n/i)
   |: n.
   Est-ce que rumine ? (o/n/i)
   |: i.
   Est-ce que taches ? (o/n/i)
   |: o.
   r6
   non(mange_herbe) non(sabots) brun dents_pointues griffes yeux_avant carnivore poils mammifere taches guepard 
   Yes

Remerciements

Ce projet est issu du cours Prolog de Nathalie Guin (UFR informatique - Université Lyon 1)