Session 4 :
Réalisation de solveurs de contraintes en Prolog

Sommaire de la session 4 :

Présentation de la session

Lors des sessions de cours précédentes, vous avez appris ce qu'est un CSP, et vous avez étudié un certain nombre d'algorithmes permettant de résoudre ces CSPs. Aujourd'hui, vous allez implémenter en Prolog ces algorithmes : vous allez écrire votre propre solveur de contraintes pour résoudre des CSPs sur les domaines finis. L'objectif est d'une part de vous faire mieux comprendre le fonctionnement de ces algorithmes en les programmant, et d'autre part de vous entrainer un peu plus à la programmation en Prolog.

Pour simplifier la phase de vérification de la consistance d'une affectation, on se limitera aux CSPs binaires, c'est à dire les CSPs dont toutes les contraintes portent sur 2 variables exactement. Le premier point de cette session de cours propose un formalisme pour décrire en Prolog les CSPs binaires que l'on souhaite résoudre ; les points suivants vous permettront d'écrire progressivement les programmes Prolog implémentant les différents algorithmes étudiés au cours de la troisième session.

A chaque fois que l'on vous décrira un prédicat, ou que vous aurez à écrire un prédicat, on utilisera les conventions suivantes. Par ailleurs, à chaque fois que l'on vous donnera un exemple d'exécution sous l'interprète Prolog, on utilisera la fonte courier, et on encadrera la séquence d'exécution.

1 - Description de CSPs binaires en Prolog

Pour concevoir un solveur de contraintes, la première chose à faire est de décider d'une convention pour décrire le CSP à résoudre. On se limite ici à des CSPs binaires, c'est à dire des CSPs dont toutes les contraintes portent sur 2 variables exactement, et on propose de décrire un CSP binaire (X,D,C) en définissant les 2 prédicats Prolog suivants :

• Le prédicat variables/1 décrit les variables du CSP, avec leurs domaines associés :
  
  
  • Schéma d'appel :

    variables(?liste)

  • Description :

    variables(L) unifie L avec la liste des noms des variables du CSP, chaque nom de variable étant suivi du symbole ':' puis du domaine de la variable (la liste des valeurs que la variable peut prendre). Ainsi, si le CSP comporte n variables {x1, x2, ..., xn} , alors L s'unifie avec la liste [x1:D1, x2:D2, ..., xn:Dn] telle que D1 est la liste des valeurs contenues dans D(x1), ..., Dn est la liste des valeurs contenues dans D(xn).
    Remarque : les noms des variables du CSP (x1, x2, ..., xn) ne doivent pas être des variables Prolog, mais des termes constants... il faudra donc être vigilant et choisir des noms, pour les variables du CSP, qui commencent par des lettres minuscules.

  • Exemple d'exécution de variables/1, pour le CSP des 4 reines :

    |?- variables(L). L = [x(1):[1,2,3,4], x(2):[1,2,3,4], x(3):[1,2,3,4], x(4):[1,2,3,4]] yes

• Le prédicat consistants/2 décrit les contraintes binaires du CSP :
  
  
  • Schéma d'appel:
    

    consistants((+terme,+terme),(+terme,+terme))

  • Description :
    

    consistants((Xi,Vi),(Xj,Vj)) réussit si l'affectation partielle {(Xi,Vi),(Xj,Vj)} est consistante, autrement dit, si la contrainte binaire entre les variables Xi et Xj est vérifiée pour les valeurs Vi et Vj.

  • Exemple d'exécution, pour le CSP des 4 reines :
    

    |?- consistants((x(1),2),(x(4),2)). no | ?- consistants((x(1),1),(x(2),3)). yes

Nous vous donnons les codes Prolog décrivant le CSP des 4 reines, le CSP du coloriage d'une carte, et le CSP des mariages stables. Vous pourrez utiliser ces descriptions de CSPs pour tester les solveurs de contraintes que vous allez maintenant écrire.

2 - Programmation de l'algorithme "génère et teste" en Prolog

2.1 - Génération d'affectations totales

• Schéma d'appel :

  genere(+liste_de_termes, ?liste_de_termes)

• Description :

  genere(V,A) réussit si
  

  • V contient la liste des noms des variables du CSP, chaque nom de variable étant suivi du domaine de la variable, et
  • A s'unifie avec une affectation totale des variables de V, c'est à dire une liste de couples (variable,valeur).

• Exemple d'exécution de genere/2 :

  si l'on a 3 variables a, b et c, telles que D(a)={0,1}, D(b)={2,4,6} et D(c)={0}, alors genere([a:[0,1], b:[2,4,6], c:[0]],A) génèrera toutes les affectations totales pour ces variables de la façon suivante :

  | ?- genere([a:[0,1], b:[2,4,6], c:[0]],A). A = [(a,0),(b,2),(c,0)] ? ; A = [(a,0),(b,4),(c,0)] ? ; A = [(a,0),(b,6),(c,0)] ? ; A = [(a,1),(b,2),(c,0)] ? ; A = [(a,1),(b,4),(c,0)] ? ; A = [(a,1),(b,6),(c,0)] ? ; no

| ?- variables(V), genere(V,A).

A = [(x(1),1),(x(2),1),(x(3),1),(x(4),1)] ? ; A = [(x(1),1),(x(2),1),(x(3),1),(x(4),2)] ? ; A = [(x(1),1),(x(2),1),(x(3),1),(x(4),3)] ? ; A = [(x(1),1),(x(2),1),(x(3),1),(x(4),4)] ? ; A = [(x(1),1),(x(2),1),(x(3),2),(x(4),1)] ? ; A = [(x(1),1),(x(2),1),(x(3),2),(x(4),2)] ? ; A = [(x(1),1),(x(2),1),(x(3),2),(x(4),3)] ? ; etc...

2.2 - Test de consistance d'une affectation

• Schéma d'appel :

  teste(+liste_de_termes)

• Description :

  teste(A) réussit si A est une affectation consistante. Rappelons que, les contraintes étant toutes binaires, une affectation A est consistante si toutes les assignations appartenant à A sont consistantes 2 à 2, autrement dit, si pour tout (Xi,Vi) et (Xj,Vj) appartenant à A, l'affectation {(Xi,Vi),(Xj,Vj)} est consistante.

• Exemple d'exécution de teste/1, pour le CSP des 4 reines :

  | ?- teste([(x(1),1),(x(2),3),(x(3),2)]). no | ?- teste([(x(1),2),(x(2),4),(x(3),1),(x(4),3)]). yes

2.3 - Génère et teste

En utilisant les prédicats genere/2 et teste/1, vous pouvez maintenant écrire le prédicat genereEtTeste/1 suivant :

• Schéma d'appel :
  

  genereEtTeste(?liste_de_termes)

• Description :

  genereEtTeste(A) unifie A avec une solution du CSP décrit par les prédicats variables/1 et consistants/2.

• Exemple d'exécution de genereEtTeste pour le CSP des 4 reines :

  | ?- genereEtTeste(A). A = [(x(1),2),(x(2),4),(x(3),1),(x(4),3)] ? ; A = [(x(1),3),(x(2),1),(x(3),4),(x(4),2)] ? ; (10 ms) no

Correction de genereEtTeste

3 - Programmation de "simple retour-arrière" en Prolog

3.1 - Test incrémental de consistance

• Schéma d'appel :

  teste((+terme,+terme),+liste_de_termes)

• Description :

  teste((X,V),A) réussit si l'affectation de X à la valeur V est consistante avec les affectations déjà effectuées dans A.

• Exemple d'exécution de teste/2, pour le CSP des 4 reines :

  | ?- teste((x(3),1),[(x(1),1),(x(2),3)]). no | ?- teste((x(3),1),[(x(1),2),(x(2),4)]). yes

3.2 - Simple retour-arrière

• Schéma d'appel :

  simpleRetourArriere(+liste_de_termes, +liste_de_termes, ?liste_de_termes)

• Description :

  simpleRetourArrière(V,Apartielle,AV) réussit si

  • V contient la liste des variables qui ne sont pas encore affectées, chaque variable étant suivie de son domaine ;
  • Apartielle contient la liste des affectations déjà effectuées (Apartielle=[] au premier appel) ;
  • AV s'unifie avec une affectation des variables de V qui soit consistante avec l'affectation partielle Apartielle.

• Exemples d'exécution de simpleRetourArrière/3 pour le problème des 4 reines:
  

  |?- simpleRetourArriere([x(3): [1,2,3,4], x(4): [1,2,3,4]], [(x(1),2),(x(2),4)],A). A = [(x(3),1),(x(4),3)] ? ; no | ?- simpleRetourArriere( [x(3): [1,2,3,4], x(4): [1,2,3,4]], [(x(1),1),(x(2),3)],A). no | ?- simpleRetourArriere([x(1): [1,2,3,4], x(2): [1,2,3,4], x(3): [1,2,3,4], x(4): [1,2,3,4]],[],A). A = [(x(1),2),(x(2),4),(x(3),1),(x(4),3)] ? ; A = [(x(1),3),(x(2),1),(x(3),4),(x(4),2)] ? ; no

Vérifiez que votre prédicat est bien défini en le testant sur les exemples d'exécution ci-dessus (n'oubliez pas de charger auparavant le code Prolog décrivant le CSP des 4 reines).

Enfin, en utilisant ce prédicat simpleRetourArriere/3, vous pouvez écrire le prédicat simpleRetourArriere/1 tel que simpleRetourArriere(A) unifie A avec une solution du CSP décrit par les prédicats variables/1 et consistants/2.

Correction de simpleRetourArrière.

4 - Programmation de l'algorithme "anticipation/noeud" en Prolog

4.1 - Filtrage des domaines des variables

• Schéma d'appel :

  filtre(+terme,+terme,+liste_de_termes,?liste_de_termes)

• Description :

  filtre(X, V, Variables, VariablesFiltrees) réussit si

  • X est une variable,
  • V est une valeur affectée à X,
  • Variables est la liste des variables qui ne sont pas encore affectées, chaque variable étant suivie de son domaine ;
  • VariablesFiltrees s'unifie avec la liste des variables qui ne sont pas encore affectées, chaque variable étant suivie de son domaine filtré (c'est-à-dire que l'on a enlevé du domaine de chaque variable les valeurs incompatibles avec l'affectation de X à la valeur V) ; chaque domaine filtré doit contenir au moins une valeur (si un domaine filtré est vide, alors le prédicat échoue).

• Exemple d'exécution de filtre/4, pour le CSP des 4 reines :

  | ?- filtre(x(1),1,[x(2):[1,2,3,4], x(3):[1,2,3,4], x(4):[1,2,3,4]],VarFiltrees). VarFiltrees = [x(2):[3,4], x(3):[2,4], x(4):[2,3]] ? yes | ?- filtre(x(1),1,[x(2):[1,2], x(3):[1,2], x(4):[1,2]], VarFiltrees). no

4.2 - Anticipation

• Schéma d'appel :

  anticipation(+liste_de_termes,+liste_de_termes,?liste_de_termes)

• Description :

  anticipation(V,Apartielle,Atotale) réussit si

  • V contient la liste des variables qui ne sont pas encore affectées, chaque variable étant suivie de son domaine ;
  • Apartielle contient la liste des affectations déjà effectuées (Apartielle=[] au premier appel) ;
  • Atotale s'unifie avec une affectation des variables de Vqui soit consistante avec l'affectation partielle Apartielle.

Correction de Anticipation.

5 -Intégration de l'heuristique "échec d'abord"

5.1 - Extraction de la variable ayant le plus petit domaine

• Schéma d'appel :

  extraitMin(+liste_de_termes,?terme,?liste_de_termes)

• Description :

  extraitMin(Variables,Xmin,VariablesSansXmin) réussit si

  • Variables est une liste de variables, chaque variable étant suivie de son domaine ;
  • Xmin s'unifie avec la variable (suivie de son domaine) de la liste Variables qui a le plus petit domaine ;
  • VariablesSansXmin s'unifie avec la liste Variables à laquelle on a enlevé la variable Xmin (et son domaine).

• Exemple d'exécution de extraitMin/3 :

  | ?- extraitMin([a:[1,2,3,4], b:[1,2], c:[1,2,3]], X, LsansX). X = b:[1,2] LsansX = [a:[1,2,3,4],c:[1,2,3]]

5.2 - Anticipation/noeud avec l'heuristique "échec d'abord"

• Schéma d'appel :

  echecDabord(+liste_de_termes, +liste_de_termes, ?liste_de_termes)

• Description :

  echecDabord(V,Apartielle,Atotale) réussit si

  • V contient la liste des variables qui ne sont pas encore affectées, chaque variable étant suivie de son domaine ;
  • Apartielle contient la liste des affectations déjà effectuées (Apartielle=[] au premier appel) ;
  • Atotale s'unifie avec une affectation des variables de V qui soit consistante avec l'affectation partielle Apartielle.

Correction de echecDabord

6 - Comparaison expérimentale des quatre solveurs

On peut maintenant comparer l'efficacité des quatre solveurs que l'on vient de programmer en les exécutant sur le problème du placement de n reines sur un échiquier nxn.

Pour cela, commencez par récupérer le fichier solveurs.pl contenant le code Prolog pour les 4 solveurs, et le fichier reinesN.pl contenant le code Prolog permettant de générer le CSP des n reines... et chargez ces deux fichiers sous l'interprète GNU-Prolog :

| ?- [solveurs,reinesN]. compiling solveurs.pl for byte code... solveurs.pl compiled, 76 lines read - 10671 bytes written, 54 ms compiling reinesN.pl for byte code... reinesN.pl compiled, 20 lines read - 2588 bytes written, 10 ms yes

| ?- genereReines(6).

| ?- anticipation(A). A = [(x(1),2),(x(2),4),(x(3),6),(x(4),1),(x(5),3),(x(6),5)] ? ; A = [(x(1),3),(x(2),6),(x(3),2),(x(4),5),(x(5),1),(x(6),4)] ? ; A = [(x(1),4),(x(2),1),(x(3),5),(x(4),2),(x(5),6),(x(6),3)] ? ; A = [(x(1),5),(x(2),3),(x(3),1),(x(4),6),(x(5),4),(x(6),2)] ? ; (10 ms) no

Pour comparer l'efficacité des 4 solveurs, il est plus significatif de comparer les temps mis pour calculer toutes les solutions (en effet, la première solution est souvent trouvée quasiment instantanément pour les petites valeurs de n).

Pour calculer toutes les solutions à une question, vous pouvez utiliser le prédicat bagof/3 : l'exécution de bagof(A,But,L) a pour effet de calculer tous les termes A pour lesquels But réussit (But étant un atome logique à prouver contenant la variable A), et de collecter la liste de ces termes dans L. Ainsi, pour déterminer le temps mis par le solveur genereEtTeste pour calculer toutes les solutions aux CSP des n reines lorsque n=6, on exécutera la séquence suivante :

| ?- genereReines(6). yes | ?- bagof(A,genereEtTeste(A),L). L = [[(x(1),2),(x(2),4),(x(3),6),(x(4),1),(x(5),3),(x(6),5)],...] (730 ms) yes

| ?- bagof(A,genereEtTeste(A),_). (730 ms) yes

On peut ainsi comparer les temps d'exécution des 4 solveurs que nous avons écrits sur le problème des n reines, pour différentes valeurs de n. On obtient des temps d'exécution de l'ordre des suivants (ces temps dépendent bien évidemment de votre machine !!!) :

nb de reines	"génère et teste"	"simple retour-arrière"	"anticipation/noeud"	"anticipation/noeud + échec d'abord"
6	730 ms	10 ms	10 ms	10 ms
8	288 530 ms	210 ms	140 ms	130 ms
10	-	5 880 ms	2 520 ms	2 310 ms
12	-	183 110 ms	62 820 ms	52 240 ms

Sur ce problème, on peut constater que "simple retour-arrière" est considérablement plus efficace que "génère et teste" ; "anticipation/noeud" est environ 2 fois plus rapide que "simple retour-arrière", et enfin l'heuristique d'ordonnancement des variables "échec d'abord" améliore légèrement les temps d'exécution de "anticipation/noeud".

Sur le problème du coloriage de la carte (avec 14 pays), on obtient des résultats similaires : pour calculer simplement la première solution, "génère et teste" prend 794 670 ms, tandis que pour trouver toutes les solutions (il y en a 1968), "simple retour-arriere" prend 7 230 ms, "anticipation/noeud" prend 1 310 ms et "anticipation/noeud" couplé avec l'heuristique "échec d'abord" prend 580 ms.