Session 5 :
Programmation par contraintes avec Gnu-Prolog


Sommaire de la session 5 :

Présentation de la session
1 - Variables sur les domaines finis en Gnu-Prolog
2 - Contraintes sur les domaines finis en Gnu-Prolog
3 - Résolution de CSPs par Gnu-Prolog
4 - Un premier exemple : les reines
5 - Un deuxième exemple : les mariages stables




Présentation de la session

Les algorithmes permettant de résoudre des CSPs (dont ceux que vous avez étudiés et programmés lors des deux sessions de cours précédantes) sont appelés des "solveurs" de contraintes. Certains de ces solveurs ont été intégrés dans des systèmes ou des langages de programmation, définissant ainsi un nouveau paradigme de programmation appelé "programmation par contraintes" : pour résoudre un CSP avec un système ou un langage de programmation par contraintes, il suffit de spécifier les contraintes, leur résolution étant prise en charge automatiquement (sans avoir besoin de le programmer) par les solveurs de contraintes intégrés au langage.

Un des tout premiers systèmes à intégrer des algorithmes pour la résolution "automatique" de problèmes formulés en termes de contraintes s'appelle ALICE et a été conçu en 1976 par Jean-Louis Laurière. Depuis, de nombreux langages intégrant des solveurs de contraintes ont été proposés. Ce paradigme de programmation par contraintes est orthogonal aux autres paradigmes de programmation que sont la programmation impérative, la programmation fonctionnelle, la programmation logique ou la programmation orientée objet : il existe des langages de programmation par contraintes logiques (comme CHIP, Eclipse, PrologIV ou Gnu-Prolog), fonctionnels orientés objet (comme Mozart ou Screamer), impératifs orientés objet (comme CHOCO ou encore Ilog Solver).

Si l'intégration de solveurs de contraintes peut se faire dans tous les styles de programmation, elle est particulièrement naturelle en Prolog. De fait, Prolog peut être considéré comme un langage de programmation par contraintes en lui-même : le domaine des variables est l'univers de Herbrand (c'est-à-dire l'ensemble des termes, aussi appelés arbres, que l'on peut construire à partir des symboles fonctionnels du programme) ; les contraintes sont des égalités entre termes (unifier deux termes Prolog revient à poser une contrainte d'égalité entre eux). Ainsi, la sémantique opérationnelle de Prolog a été tout naturellement étendue pour pouvoir prendre en compte des contraintes portant sur d'autres domaines que celui de l'univers de Herbrand : on remplace simplement le mécanisme d'unification utilisé par Prolog par un mécanisme plus général de satisfaction de contraintes. Vous trouverez plus d'informations sur la "machine abstraite" commune aux langages de programmation logique par contraintes, par exemple, dans [Colmerauer 90].

De façon générique, on appelle "CLP(X)" un langage de programmation logique permettant de poser des contraintes sur des variables appartenant à un domaine X : CLP(H) correspond à Prolog (H pour univers de Herbrand) ; CLP(R) désigne les Prolog étendus aux contraintes numériques sur les réels ; CLP(FD) désigne les Prolog étendus aux contraintes sur les domaines finis (FD pour Finite Domains) ; etc.

Gnu-Prolog, le langage que nous allons maintenant étudier, appartient à la famille CLP(FD) et intègre un solveur de contraintes sur les domaines finis. Nous allons étudier lors de cette cinquième session de cours quelques prédicats prédéfinis de Gnu-Prolog permettant de déclarer des variables à valeur dans des domaines finis, poser des contraintes entre elles, et résoudre ces contraintes. Nous ne décrirons explicitement que les prédicats les plus importants ; vous trouverez plus d'informations sur les éléments du langage Gnu-Prolog, et notamment une description détaillée de tous les prédicats sur les domaines finis dans le manuel utilisateur (voir surtout le chapitre 8).

A chaque fois que l'on vous décrira un prédicat prédéfini, on utilisera les conventions suivantes (conventions qui sont d'ailleurs inspirées de celles utilisées dans le manuel utilisateur de Gnu-Prolog). 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 - Variables sur les domaines finis en Gnu-Prolog

En Gnu-Prolog, les variables sur les domaines finis (appelées dans la suite variables FD) ne se distinguent pas, du point de vue syntaxique, des autres variables Prolog : une variable FD est représentée par une chaîne alpha-numérique commençant par une majuscule. Cependant, une variable FD ne peut prendre qu'une valeur entière, positive ou nulle, et possède les caractéristiques suivantes :

Une variable FD est complètement compatible avec les constantes entières ainsi qu'avec les autres variables Prolog : quand on pose une contrainte Prolog entre plusieurs variables FD, une variable FD peut être remplacée par une valeur entière i (qui sera automatiquement assimilée à une variable FD ayant pour domaine l'intervalle [i..i]), ou une variable Prolog "classique" (qui sera automatiquement assimilée à une variable FD ayant pour domaine l'intervalle [0..fd_max_integer]). Ainsi, il n'est pas nécessaire de déclarer spécifiquement les variables FD : toute variable Prolog "classique" sera interprétée comme étant une variable FD à partir du moment où elle apparaît dans une contrainte.

Cependant, si l'on souhaite explicitement déclarer une variable FD (dans le cas notamment où le domaine de la variable est différent du domaine par défaut 0..fd_max_integer), on peut utiliser les prédicats fd_domain/3 et fd_domain/2 suivants :

Etant donnée une variable FD, les prédicats fd_min/2, fd_max/2, fd_size/2 et fd_dom/2 permettent de connaître respectivement la plus petite valeur, la plus grande valeur, le nombre de valeurs et la liste des valeurs de cette variable FD.


2 - Contraintes sur les domaines finis en Gnu-Prolog

2.1 - Contraintes arithmétiques

On peut poser des contraintes d'égalité (=), de différence (≠), ou d'inégalité (<, ≤, >, ≥) entre des expressions arithmétiques sur les domaines finis. Une expression arithmétique sur les domaines finis est une expression arithmétique utilisant les opérateurs classiques (+, -, *, /, etc), et dont les opérandes sont des variables FD ou des entiers.

Syntaxiquement, on distingue deux façons de déclarer des contraintes arithmétiques, suivant que l'on souhaite utiliser un solveur de contraintes établissant une consistance d'arc partielle ou une consistance d'arc totale : on a vu au point 4 de la troisième session de cours que les solveurs de contraintes filtrent les domaines des variables, en enlevant les valeurs inconsistantes par rapport à une consistance donnée. Le solveur de contraintes intégré à Gnu-Prolog propose un filtrage par rapport à deux de ces consistances : la consistance d'arc totale, aussi appelée 2-consistance, est celle introduite au point 4 de la troisième session ; la consistance d'arc partielle est une consistance légèrement plus faible que la consistance d'arc totale, qui revient à considérer les domaines de valeurs des variables FD comme des intervalles de valeurs, et à ne vérifier la consistance d'arc qu'aux bornes minimales et maximales de ces intervalles. Cette consistance partielle est plus rapidement établie, mais en contrepartie elle enlève moins de valeurs des domaines des variables.

Ainsi, les prédicats décrits dans le tableau suivant posent des contraintes d'égalité, de différence, ou d'inégalité entre deux expressions arithmétiques Expr1 et Expr2 ; pour ces contraintes, le solveur de contraintes effectuera un filtrage des domaines des variables par rapport à une consistance d'arc partielle.

Schéma d'appel
Description
?Expr_arith #= ?Expr_arith Expr1 #= Expr2 contraint Expr1 à être égale à Expr2
?Expr_arith #\= ?Expr_arith Expr1 #\= Expr2 contraint Expr1 à être différente de Expr2
?Expr_arith #< ?Expr_arith Expr1 #< Expr2 contraint Expr1 à être inférieure à Expr2
?Expr_arith #=< ?Expr_arith Expr1 #=< Expr2 contraint Expr1 à être inférieure ou égale à Expr2
?Expr_arith #> ?Expr_arith Expr1 #> Expr2 contraint Expr1 à être supérieure à Expr2
?Expr_arith #>= ?Expr_arith Expr1 #>= Expr2 contraint Expr1 à être supérieure ou égale à Expr2

Pour que le solveur de contraintes effectue un filtrage des domaines par rapport à une consistance d'arc totale, il faudra utiliser les prédicats suivants :
Expr1 #=# Expr2, Expr1 #\=# Expr2, Expr1 #<# Expr2, Expr1 #=<# Expr2, Expr1 #># Expr2, Expr1 #>=# Expr2.

2.2 - Contraintes booléennes et contraintes sur les contraintes

Une contrainte booléenne sur les domaines finis est une expression composée à partir des opérateurs booléens suivants :

Les opérandes d'une contrainte booléenne peuvent être la valeur entière 0 (interprétée comme "faux"), la valeur entière 1 (interprétée comme "vrai") ou une variable (interprétée comme une variable FD dont le domaine est restreint aux valeurs 0 et 1). Les opérandes d'une contrainte booléenne peuvent aussi être des contraintes, ce qui permet de poser des contraintes sur les contraintes ! Lorsqu'une contrainte c apparaît dans une contrainte booléenne, elle est "réifiée", c'est-à-dire que dès lors que le solveur de contraintes peut déduire que cette contrainte c est vraie, alors elle est remplacée par la valeur 1, tandis que s'il arrive à prouver quelle est fausse, elle est remplacée par 0.

Par exemple, la contrainte booléenne

(X#=Y) #<=> (Y#=<3)
exprime le fait que les 2 variables X et Y doivent être égales si et seulement si Y est inférieure ou égale à 3. On aurait tout aussi bien pu écrire :
((X#=Y) #==> (Y#=<3)) #/\ ((X#\=Y) #==> (Y#>3))
ou autrement dit, si X=Y alors Y≤3 sinon Y>3.

Le prédicat fd_cardinality/2 décrit ci-dessous permet de poser une contrainte sur le nombre de contraintes devant être satisfaites, parmi une liste donnée de contraintes :

De façon similaire, les prédicats fd_cardinality/3, fd_at_least_one/1, fd_at_most_one/1 et fd_only_one/1 permettent également de poser des contraintes sur le nombre de contraintes satisfaites.

2.3 - Contraintes symboliques

On peut poser des contraintes symboliques, sur des ensembles de variables, à l'aide de prédicats prédéfinis Gnu-Prolog :

3 - Résolution de CSPs par Gnu-Prolog

Une fois que l'on a défini le CSP, en déclarant les domaines des variables FD et en posant des contraintes sur ces variables, on peut demander à Gnu-Prolog de le résoudre, c'est-à-dire de déterminer s'il existe une solution, et le cas échéant de donner les valeurs des variables correspondantes. Gnu-Prolog résoud un CSP en énumérant les différentes affectations possibles de valeurs aux variables FD jusqu'à en trouver une qui satisfasse toutes les contraintes. Pendant l'énumération, Gnu-Prolog utilise les contraintes pour filtrer les domaines des variables en enlevant les valeurs qui ne vérifient pas la consistance d'arc (selon le principe de l'algorithme "anticipation").

Pour demander à Gnu-Prolog de rechercher une affectation de valeurs à une liste de variables, on utilise le prédicat fd_labeling/1 :

Par défaut, le prédicat fd_labeling/1 instancie les variables dans l'ordre donné par la liste de variables (de la gauche vers la droite), et choisit, pour chaque variable, les valeurs à instancier de la plus petite à la plus grande. Pour améliorer les performances de l'algorithme, on peut intégrer des heuristiques (voir le point 5 de la troisième session de cours) pour préciser à Gnu-Prolog l'ordre dans lequel il doit instancier les variables, ainsi que l'ordre dans lequel il doit considérer les valeurs à instancier. On utilise pour cela le prédicat fd_labeling/2 :


4 - Un premier exemple : les reines

4.1 - Comparaison des deux premiers modèles pour 4 reines

Nous avons vu lors de la première session de cours que le problème des reines peut être modélisé de différentes façons : la première modélisation associe deux variables à chaque reine (une pour le numéro de ligne et une pour le numéro de colonne) ; la deuxième modélisation intègre le fait qu'il y a une et une seule reine par colonne et associe donc une seule variable à chaque reine, correspondant au numéro de ligne de la reine. Pour faire nos premiers pas en Gnu-Prolog "avec contraintes", on va écrire les programmes correspondant à ces deux modélisations, dans le cas où l'on a 4 reines, puis on va les comparer expérimentalement.

Programme correspondant à la première modélisation :
reines4_modele1(Vars,Options) :-
/* on déclare les variables */
Vars = [C1,C2,C3,C4,L1,L2,L3,L4],
/* le domaine de chaque variable est {1,2,3,4} */
fd_domain(Vars,1,4),
/* Les reines doivent être sur des lignes différentes */
fd_all_different([L1,L2,L3,L4]),
/* Les reines doivent être sur des colonnes différentes */
fd_all_different([C1,C2,C3,C4]),
/* Les reines doivent être sur des diagonales montantes différentes */
C1+L1 #\= C2+L2, C1+L1 #\= C3+L3, C1+L1 #\= C4+L4,
C2+L2 #\= C3+L3, C2+L2 #\= C4+L4, C3+L3 #\= C4+L4,
/* Les reines doivent être sur des diagonales descendantes différentes */
C1-L1 #\= C2-L2, C1-L1 #\= C3-L3, C1-L1 #\= C4-L4,
C2-L2 #\= C3-L3, C2-L2 #\= C4-L4, C3-L3 #\= C4-L4,
/* on recherche une affectation des variables qui soit solution */
fd_labeling(Vars,Options).

Programme correspondant à la deuxième modélisation :
reines4_modele2(Vars,Options) :-
/* on déclare les variables */
Vars = [X1,X2,X3,X4],
/* le domaine de chaque variable est {1,2,3,4} */
fd_domain(Vars,1,4),
/* Les reines doivent être sur des lignes différentes */
fd_all_different(Vars),
/* Les reines doivent être sur des diagonales montantes différentes */
1+X1 #\= 2+X2, 1+X1 #\= 3+X3, 1+X1 #\= 4+X4,
2+X2 #\= 3+X3, 2+X2 #\= 4+X4, 3+X3 #\= 4+X4,
/* Les reines doivent être sur des diagonales descendantes différentes */
1-X1 #\= 2-X2, 1-X1 #\= 3-X3, 1-X1 #\= 4-X4,
2-X2 #\= 3-X3, 2-X2 #\= 4-X4, 3-X3 #\= 4-X4,
/* on recherche une affectation des variables qui soit solution */
fd_labeling(Vars,Options).

Copiez les deux programmes dans un fichier, avec votre éditeur de texte préféré, et chargez le fichier sous Gnu-Prolog.

Si vous exécutez le programme correspondant au modèle 1, Gnu-Prolog vous affiche les réponses suivantes :

Exécution Gnu-Prolog : Interprétation des résultats :
?-reines4_modele1(L,[backtracks(B)]).

B = 2
L = [1,2,3,4,2,4,1,3] ? ;
La première solution, obtenue en 2 retour-arrières, est L1=1, L2=2, L3=3, L4=4, C1=2, C2=4, C3=1 et C4=3
B = 1
L = [1,2,3,4,3,1,4,2] ? ;
La deuxième solution, obtenue en 1 retour-arrière, est L1=1, L2=2, L3=3, L4=4, C1=3, C2=1, C3=4 et C4=2.
B = 5
L = [1,2,4,3,2,4,3,1] ? ;
La troisième solution, obtenue en 5 retour-arrières, est une permutation de la première solution
(on a échangé la troisième et la quatrième reine).
B = 1
L = [1,2,4,3,3,1,2,4] ? ;
La quatrième solution, obtenue en 1 retour-arrière, est une permutation de la deuxième solution
(on a échangé la troisième et la quatrième reine).
etc... etc...
au total, 48 solutions sont trouvées, en 157 retour-arrières. Les 48 solutions correspondent aux 24 permutations possibles des 2 premières solutions.

Si vous exécutez le programme correspondant au modèle 2, Prolog vous affiche les réponses suivantes :

Exécution Gnu-Prolog : Interprétation des résultats :
?-reines4_modele2(L,[backtracks(B)]).

B = 2
L = [2,4,1,3] ? ;
La première solution, obtenue en 2 retour-arrières, est X1=2, X2=4, X3=1 et X4=3
B = 1
L = [3,1,4,2] ? ;
La deuxième solution, obtenue en 1 retour-arrière, est X1=3, X2=1, X3=4 et X4=2.
no Il n'y a pas d'autre solution

Ainsi, la deuxième modélisation est meilleure que la première dans le sens où elle ne retourne que des solutions différentes (en faisant abstraction des symétries dues au fait que les reines sont interchangeables.

4.2 - Généralisation du deuxième modèle à n reines

Pour généraliser le programme à N reines, il s'agit essentiellement d'écrire un prédicat contraintes/2 qui pose les contraintes sur les diagonales montantes et descendantes sans avoir à les énumérer explicitement. On obtient le programme suivant :

reinesN_modele2(N,Vars,Options) :-
/* on déclare les variables : c'est une liste de N éléments */
length(Vars,N),
/* le domaine de chaque variable est {1,2,...,N} */
fd_domain(Vars,1,N),
/* Les reines doivent être sur des lignes différentes */
fd_all_different(Vars),
/* Les reines doivent être sur des diagonales différentes */
contraintes(1,Vars),
/* on recherche une affectation des variables qui soit solution */
fd_labeling(Vars,Options).

/* contraintes(I,Vars) : Vars est une liste de variables et I est le numéro de la reine correspondant à la première variable de Vars. Ce prédicat pose les contraintes sur les diagonales pour tout couple de variables différentes appartenant à Vars */
contraintes(_,[]).
contraintes(I,[XI|Vars]) :-
Iplus1 is I + 1,
contraintesSurXI(I,XI,Iplus1,Vars),
contraintes(Iplus1,Vars).

/* contraintesSurXI(I,XI,J,Vars) : XI est une variable, et I est le numéro de la reine correspondant à cette variable ; Vars est une liste de variables et J est le numéro de la reine correspondant à la première variable de Vars. Ce prédicat pose les contraintes sur les diagonales entre la variable XI et toutes les variables appartenant à Vars */
contraintesSurXI(_,_,_,[]).
contraintesSurXI(I,XI,J,[XJ|Vars]) :-
I+XI #\= J+XJ,
I-XI #\= J-XJ,
Jplus1 is J + 1,
contraintesSurXI(I,XI,Jplus1,Vars).

On peut utiliser ce programme pour afficher une à une les solutions de la façon suivante :

| ?- reinesN_modele2(8,Vars,[backtracks(B)]).

B = 24
Vars = [1,5,8,6,3,7,2,4] ? ;

B = 8
Vars = [1,6,8,3,7,4,2,5] ? ;

...

On peut également demander à Prolog de rechercher toutes les solutions, et de conserver, pour chaque solution le nombre de retour-arrières nécessaires dans une liste L ; la somme des éléments de L donne alors le nombre total de retour-arrières effectués pour trouver toutes les solutions tandis que sa longueur donne le nombre de solutions trouvées :

| ?- findall(B,reinesN_modele2(8,Vars,[backtracks(B)]),L), sum_list(L,NbRetourArriere), length(L,NbSolutions).

L = [24,8,5,2,16,13,...]
NbRetourArriere = 391
NbSolution = 92

On peut enfin évaluer expérimentalement l'intéret de l'heuristique "échec-d'abord", en comparant les résultats obtenus lorsqu'on ajoute ou non l'option "variable_method(first_fail)" à la liste des options :

Nb reines Nb solutions
Affectation des variables "standard" Affectation des variables "first_fail"
8 92 391 retour-arrières et 0 ms 358 retour-arrières et 10 ms
10 724 6 641 retour-arrières et 60 ms 5 777 retour-arrières et 60 ms
12 14 200 146 047 retour-arrières et 1 440 ms 114 814 retour-arrières et 1 320 ms
14 365 596 4 197 870 retour-arrières et 41 900 ms 3 163 768 retour-arrières et 39 950 ms

Ainsi, on constate que sur ce problème des reines, l'heuristique "échec-d'abord" réduit d'environ 25% le nombre de retours en arrière ; cependant, le temps CPU est quasiment identique car si l'on explore moins de combinaisons, la sélection, à chaque étape, de la variable qui a le plus petit domaine prend du temps.


5 - Un deuxième exemple : les mariages stables

Le problème des mariages stables a été décrit et modélisé lors de la première session de cours ; le code Gnu-Prolog décrivant ce problème vous a été donné lors de la quatrième session de cours. On va maintenant compléter ce code pour effectivement résoudre ce CSP avec le solveur de contraintes de Gnu-Prolog. Le programme proposé utilise le prédicat fd_relation/2 de Gnu-Prolog, prédicat qui permet de définir en extension une contrainte. En effet, il s'agit de vérifier pour chaque couple de mariages qu'il est consistant, c'est-à-dire que l'on ne marie pas I avec VI et J avec VJ alors qu'à la fois VI préfère J à I et J préfère VI à VJ. Pour cela, on va générer pour chaque couple d'hommes (I,J) l'ensemble des couples de femmes (VI,VJ) tels que le mariage de I avec VI soit consistant avec le mariage de J avec VJ.

mariageStable(Vars):-
/* on déclare les variables : c'est une liste de 6 éléments car il y a 6 hommes */
length(Vars,6),
/* on déclare les domaines */
declareDomaines(Vars,1),
/* chaque homme doit être marié à une femme différente */
fd_all_different(Vars),
/* on pose les autres contraintes */
contraintes(Vars,1),
/* on recherche une affectation des variables qui soit solution */
fd_labeling(Vars).

declareDomaines([],_).
declareDomaines([FI|Vars],I) :-
/* le domaine de la variable FI, correspondant à la femme de I, est donné par le prédicat domaine/2 défini lors de la session 4 */
domaine(I,DomI),
fd_domain(FI,DomI),
Iplus1 is I + 1,
declareDomaines(Vars,Iplus1).

/* contraintes(Vars,I) : Vars est une liste de variables et I est le numéro de l'homme correspondant à la première variable de Vars. Ce prédicat pose les contraintes sur tous les couples de variables différentes appartenant à Vars */
contraintes([],_).
contraintes([FI|Vars],I) :-
Iplus1 is I + 1,
contraintesSurFI(FI,I,Vars,Iplus1),
contraintes(Vars,Iplus1).

/* contraintesSurFI(FI,I,Vars,J) : FI est la variable associée à l'homme I ; Vars est une liste de variables et J est le numéro d'homme correspondant à la première variable de Vars. Ce prédicat pose les contraintes entre FI et toutes les variables appartenant à Vars */
contraintesSurFI(_,_,[],_).
contraintesSurFI(FI,I,[FJ|Vars],J) :-
fd_dom(FI,DomI),
fd_dom(FJ,DomJ),
/* on construit la liste L des couples de femmes (VI,VJ) tels que les mariages de I avec VI et J avec VJ soient consistants */
findall([VI,VJ],(member(VI,DomI),member(VJ,DomJ),consistants((femmeDe(I),VI),(femmeDe(J),VJ))),L),
/* la liste des couples de valeurs que l'on peut affecter simultanément à [FI,FJ] est L */
fd_relation(L,[FI,FJ]),
Jplus1 is J + 1,
contraintesSurFI(FI,I,Vars,Jplus1).

On peut utiliser ce programme pour chercher les mariages stables :

| ?- mariageStable(V,[]).
V = [10,8,7,9,11,12] ? ;
V = [10,11,7,9,8,12] ? ;
V = [12,8,7,9,11,10] ? ;
V = [12,11,7,9,8,10] ? ;
(10 ms) no