Systemes a base de connaissances:Travaux pratiques de Clips

De Wiki de Romain RUDIGER
Aller à : navigation, rechercher

TP I.A. Voyageur de commerce


Modélisation

1

Pour ce problème, une modélisation en graphe d'état paraît bien adapté. Un noeud représente un état du problème en cours de résolution, soit les villes déjà parcourues, les villes restantes et la distance parcourue. Un arc représente la transformation du noeud courant vers un noeud destination. On cherche un état dans lequel on a balayé tout le circuit, ce sera l'état solution. Le graphe est construit au fur et à mesure de l'avancement.

2

Description des données avec un sextuplet <E, i, F, O, P, C> E l'ensemble des états : les villes à parcourir et les distances entre les villes ; i l'état initial : la ville de départ ; F un sous ensemble d'états finaux : toutes les villes devant être parcourues avec une distance non-infinie ; O opérateur de transformation : nous permet de déterminer la ville suivante ; P l'ensemble de prédicat : la ville suivante ne doit pas déjà être parcourue ; C le coût associé à chaque opérateurs de transformation : distance de la ville suivante choisie.

3

L'état initial est représenté par n'importe quelle des villes de la liste des villes.

Résolution directe

1

Avant de définir les règles de transitions, nous avons définit une règle permettant de définir la distance entre les villes à partir de leur position. Une ville est décrite par son nom, sa latitude et sa longitude. Il s'agit de calculer de façon exhaustive la distance entre toutes les villes (distance euclidienne), voici un exemple de la base de faits initiale :

(deffacts voyageur-de-commerce
	(TempsDepart (time))
	(TempsPasse 0)
	(ville v1)
	(ville v2)
	(ville v3)
	(ville v4)
	(ville v5)
	(ville v6)
	(position v1 0 0)
	(position v2 0 1)
	(position v3 0 2)
	(position v4 2 1)
	(position v5 4 4)
	(position v6 4 5)
)

La règle de calcul :

(defrule calcul-distance (declare (salience 4))
(position ?x1 ?x10 ?x11)
	(position ?x2 ?x20 ?x21)
	=>
	(assert (distance ?x1 ?x2 
		(sqrt(+ 
			  (*(- ?x20 ?x10) (- ?x20 ?x10))
					(*(- ?x21 ?x11) (- ?x21 ?x11)) 
			)) 
	) )
)

Voici les règles de transition d'état :

(defrule start
	(etat (villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) (distanceParcourue -1) (villeParcourue))
	=>
	(assert (etat (villeNonParcourue $?VNPdebut $?VNPfin) (distanceParcourue 0) (villeParcourue ?VNPselect)))
)

(defrule avancer (declare (salience 1))
	(etat 
		(villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) 
		(distanceParcourue ?dist) 
		(villeParcourue ?VPtete $?VPreste))
	(distance ?VNPselect ?VPtete ?NewDist)
	=>
	(assert (etat 
		(villeNonParcourue $?VNPdebut $?VNPfin) 
		(distanceParcourue (+ ?dist ?NewDist)) 
		(villeParcourue ?VNPselect ?VPtete $?VPreste)))
)

2

Règles de détection des solutions : Dans un premier temps une règle permet de détecter un état final et d'ajouter dans la base des faits la solution. Ensuite, une règle choisit la meilleure solution dès que deux solutions existent. La moins bonne solution est supprimée de la base.

(defrule Arrive (declare (salience 2))
	?etatFinal <- (etat (villeNonParcourue) (distanceParcourue ?dist) (villeParcourue $?VPreste))
	?TempsPasse <- (TempsPasse ?TempsP)
	(TempsDepart ?TempsD)
	=>
	(assert (solution (parcour $?VPreste) (distance ?dist)))
	(assert (TempsPasse (-(time) ?TempsD)))
	(retract ?TempsPasse)
	(retract ?etatFinal)
)

(defrule choix_solution	(declare (salience 3))
	?solution1 <- (solution (parcour $?parcour1) (distance ?dist1))
	?solution2 <- (solution (parcour $?parcour2&~$?parcour1) (distance ?dist2))
	(test(<= ?dist1 ?dist2))
	=>
	(retract ?solution2)
)

3

Dans les codes précédents, certaines parties permettent de calculer le temps mis par CLIPS pour calculer le temps de recherche de façon précise. Voici les résultats en fonction du nombre de ville :

Polytech S3 SBC Clips villles.JPG

Polytech S3 SBC Clips villles graph.JPG

Le temps de recherche est bien exponentiel tout comme le nombre de fait.

Résolution heuristique

1

Proposition d'heuristiques :

  • Choix d'une ville de départ au hasard. L'optimalité de cette heuristique est vérifiée, la meilleure solution sera trouvée puisqu'il faut passer par toutes les villes ;
  • Comparaison de la distance parcourue de la solution en cours avec la meilleure solution actuelle. Arrêt de la recherche en cours dans le cas où la distance est supérieure à celle de la soution trouvée.
  • Choix de la ville la plus proche lors de la transformation d'un état au lieu d'essayer toutes les villes ;
Méthodes d'implémentation :
  • Choix d'une ville au hasard, ce qui réduit par x le nombre de graphe à explorer, x étant le nombre de ville. Voici notre proposition :
(deffacts etat-init
	(etat
		(villeNonParcourue v2 v3 v4 v5 v6)
		(distanceParcourue -1)
		(villeParcourue v1)
	)
)
; la règle start n'a donc plus d'utilitée

Ainsi, auparavant il y avait six états initiaux, alors que maintenant un seul est conservé, le nombre de fait passe de 3 447 à 616 et 7,68 secondes au lieu de 44.

  • Comparaison de la distance parcourue de la solution en cours avec la meilleure solution actuelle.

Avec les deux heuristiques, 104 faits sont calculé en 0,93 secondes. On note une réduction non négligeable. Cependant, les chemins inutiles arrêtés sont conservé en mémoire ce qui occupe de l'espace inutilement.

(defrule avancer (declare (salience 1))
	(etat 
		(villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) 
		(distanceParcourue ?dist) 
		(villeParcourue ?VPtete $?VPreste))
	(distance ?VNPselect ?VPtete ?NewDist)
	(solution (parcour $?parcour1) (distance ?dist1))
	(test(<= (+ ?dist ?NewDist) ?dist1))
	=>
	(assert (etat 
		(villeNonParcourue $?VNPdebut $?VNPfin) 
		(distanceParcourue (+ ?dist ?NewDist)) 
		(villeParcourue ?VNPselect ?VPtete $?VPreste)))
)

2

Calcul du nombre d'états développés et profondeur moyenne :

(deftemplate etat
	(multislot villeNonParcourue (type SYMBOL))
	(slot distanceParcourue (type INTEGER))
	(multislot villeParcourue (type SYMBOL))
	(slot Profondeur (type INTEGER))
)
(deffacts voyageur-de-commerce
	[...]
	(nbrEtats 1)
	(Prof 1)
)

(defrule avancer (declare (salience 1))
	(etat 
		(villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) 
		(distanceParcourue ?dist) 
		(villeParcourue ?VPtete $?VPreste)
		(Profondeur ?prof))
	(distance ?VNPselect ?VPtete ?NewDist)
	;calcul si la solution actuelle est valable
	;(solution (parcour $?parcour1) (distance ?dist1))
	;(test(<= (+ ?dist ?NewDist) ?dist1))
	=>
	(assert (etat 
		(villeNonParcourue $?VNPdebut $?VNPfin) 
		(distanceParcourue (+ ?dist ?NewDist)) 
		(villeParcourue ?VNPselect ?VPtete $?VPreste)
		(Profondeur (+ ?prof 1))))
	(assert (NewEtat 1))
)	
(defrule CompterProf (declare (salience 1))
	?NewProf <- (NewProf ?NewProfVal)
	?ProfOld <- (Prof ?Prof)
	(test (< ?Prof 5))
	=>
	(assert (Prof (/ (+ ?Prof ?NewProfVal) 2)))
	(retract ?NewProf)
	(retract ?ProfOld)
)

(defrule CompterNbrEtats (declare (salience 1))
	?NewEtat <- (NewEtat ?x)
	?nbrEtatsOld <- (nbrEtats ?nbrEtats)
	=>
	(assert (nbrEtats (+ ?nbrEtats 1)))
	(retract ?nbrEtatsOld)
	(retract ?NewEtat)
)

Avec la première heuristique nous avons une profondeur moyenne de 5 (nombre de ville = 6) puisque toutes les solutions sont explorées. Le nombre d'état est de : 326. Avec la seconde, une profondeur moyenne de 2,222 et 44 états calculés.


3

La croissance du temps de recherche reste bien exponentielle. Les heurisitiques permettent seulement de réduire l'espace de recherche. Si l'on rajoute des villes à explorer, le temps de recherche augmentera de façon exponentielle mais beaucoup moins vite qu'une résolution directe.

Le programme final

(deftemplate etat
	(multislot villeNonParcourue (type SYMBOL))
	(slot distanceParcourue (type INTEGER))
	(multislot villeParcourue (type SYMBOL))
	(slot Profondeur (type INTEGER))
)
(deftemplate solution
	(multislot parcour (type SYMBOL))
	(slot distance (type INTEGER))
)
(deffacts voyageur-de-commerce
	(TempsDepart (time))
	(TempsPasse 0)
	(ville v1)
	(ville v2)
	(ville v3)
	(ville v4)
	(ville v5)
	(ville v6)
	(position v1 0 0)
	(position v2 0 1)
	(position v3 0 2)
	(position v4 2 1)
	(position v5 4 4)
	(position v6 4 5)
	(nbrEtats 1)
	(Prof 1)
)

(deffacts etat-init
	(etat
		(villeNonParcourue v2 v3 v4 v5 v6)
		(distanceParcourue 0)
		(villeParcourue v1)
		(Profondeur 0)
	)
	(solution
		(parcour x y)
		(distance 99999)
	)
)

(defrule calcul-distance (declare (salience 4))
	(position ?x1 ?x10 ?x11)
	(position ?x2 ?x20 ?x21)
	=>
	(assert (distance ?x1 ?x2 (sqrt
					(+ 
					  (* 
					    (- ?x20 ?x10) (- ?x20 ?x10)
					  )
					  (* 
					    (- ?x21 ?x11) (- ?x21 ?x11)
					  ) 
					)
				   ) 
	) )
)

(defrule avancer (declare (salience 1))
	(etat 
		(villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) 
		(distanceParcourue ?dist) 
		(villeParcourue ?VPtete $?VPreste)
		(Profondeur ?prof))
	(distance ?VNPselect ?VPtete ?NewDist)
	;calcul si la solution actuelle est valable
	(solution (parcour $?parcour1) (distance ?dist1))
	(test(<= (+ ?dist ?NewDist) ?dist1))
	=>
	(assert (etat 
		(villeNonParcourue $?VNPdebut $?VNPfin) 
		(distanceParcourue (+ ?dist ?NewDist)) 
		(villeParcourue ?VNPselect ?VPtete $?VPreste)
		(Profondeur (+ ?prof 1))))
	(assert (NewEtat 1))
)	
(defrule detectionCheminNonSolution (declare (salience 0))
	?etatNonSolution <- (etat
		(villeNonParcourue $?VNPdebut ?VNPselect $?VNPfin) 
		(distanceParcourue ?dist) 
		(villeParcourue ?VPtete $?VPreste)
		(Profondeur ?prof))
	(distance ?VNPselect ?VPtete ?NewDist)
	;calcul si la solution actuelle est valable
	(solution (parcour $?parcour1) (distance ?dist1))
	(test(> (+ ?dist ?NewDist) ?dist1))
	=>
	(assert (NewProf ?prof))
	(retract ?etatNonSolution)
	(assert (NewEtat 1))
)

(defrule Arrive (declare (salience 2))
	?etatFinal <- (etat (villeNonParcourue) (distanceParcourue ?dist) (villeParcourue $?VPreste) (Profondeur ?prof))
	?TempsPasse <- (TempsPasse ?TempsP)
	(TempsDepart ?TempsD)
	=>
	(assert (solution (parcour $?VPreste) (distance ?dist)))
	(assert (TempsPasse (-(time) ?TempsD)))
	(assert (NewProf ?prof))
	(retract ?TempsPasse)
	(retract ?etatFinal)
)


(defrule CompterProf (declare (salience 1))
	?NewProf <- (NewProf ?NewProfVal)
	?ProfOld <- (Prof ?Prof)
	;(test (< ?Prof 5))
	=>
	(assert (Prof (/ (+ ?Prof ?NewProfVal) 2)))
	(retract ?NewProf)
	(retract ?ProfOld)
)

(defrule CompterNbrEtats (declare (salience 1))
	?NewEtat <- (NewEtat ?x)
	?nbrEtatsOld <- (nbrEtats ?nbrEtats)
	=>
	(assert (nbrEtats (+ ?nbrEtats 1)))
	(retract ?nbrEtatsOld)
	(retract ?NewEtat)
)

(defrule choix_solution	(declare (salience 3))
	?solution1 <- (solution (parcour $?parcour1) (distance ?dist1))
	?solution2 <- (solution (parcour $?parcour2&~$?parcour1) (distance ?dist2))
	(test(<= ?dist1 ?dist2))
	=>
	(retract ?solution2)
)