Session 5 :
Programmation par contraintes avec Gnu-Prolog

Sommaire de la session 5 :

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 :

• Le domaine initial (domaine par défaut) d'une variable FD est l'ensemble des entiers compris entre 0 et une valeur maximum constante "fd_max_integer" (cette valeur est donnée par le prédicat fd_max_integer/1).
• Le domaine d'une variable FD est réduit (filtré) petit à petit par les contraintes qui sont posées sur elle ; quand une valeur est supprimée du domaine d'une variable X, elle ne pourra plus être réintégrée au domaine de X dans la suite de la résolution.

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 :

• fd_domain/3 contraint le domaine d'une variable, ou d'une liste de variables, à être un ensemble d'entiers compris entre deux valeurs données :
  
  
  • Schéma d'appel :

    fd_domain(+liste_de_variables_FD,+entier,+entier) ou
    fd_domain(?variable_FD,+entier,+entier)

  • Description :

    fd_domain(L,Min,Max) contraint chaque variable FD de la liste L à prendre une valeur comprise entre Min et Max.
    fd_domain(X,Min,Max) contraint la variable FD X à prendre une valeur comprise entre Min et Max.

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

    Pour le CSP des 4 reines, on pourra déclarer que l'on a 4 variables, chacune prenant des valeurs comprises entre 1 et 4, en écrivant

    fd_domain([X1,X2,X3,X4],1,4)

    A la suite de cette instruction, les variables X1, X2, X3 et X4 sont des variables FD dont le domaine est l'ensemble des entiers compris entre 1 et 4. On aurait tout aussi bien pu écrire

    fd_domain(X1,1,4), fd_domain(X2,1,4), fd_domain(X3,1,4), fd_domain(X4,1,4)

• fd_domain/2 contraint une variable, ou une liste de variables, à prendre leurs valeurs dans une liste donnée d'entiers :
  
  
  • Schéma d'appel :

    fd_domain(+liste_de_variables_FD,+liste_d_entiers) ou
    fd_domain(variable_FD,+liste_d_entiers)

  • Description :

    fd_domain(L,Valeurs) contraint chaque variable FD de la liste L à prendre une des valeurs de la liste Valeurs.
    fd_domain(X,Valeurs) contraint la variable FD X à prendre une des valeurs de la liste Valeurs.

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

    Pour le CSP des mariages, on pourra déclarer que l'homme 1 veut bien se marier avec les femmes 8, 10 et 12 en écrivant

    fd_domain(Epouse_de_1,[8,10,12])

    A la suite de cette instruction, la variable Epouse_de_1 est une variable FD dont le domaine est l'ensemble d'entiers {8,10,12}.

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.

Expr1 #=# Expr2, Expr1 #\=# Expr2, Expr1 #<# Expr2, Expr1 #=<# Expr2, Expr1 #># Expr2, Expr1 #>=# Expr2.

2.2 - Contraintes booléennes et contraintes sur les contraintes

• l'équivalence : E1 #<=> E2
• la non équivalence : E1 #\<=> E2
• l'implication : E1 #==> E2
• le non logique : #\E1
• le ou logique : E1 #\/ E2
• le ou exclusif : E1 ## E2
• le et logique : E1 #/\ E2

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)

((X#=Y) #==> (Y#=<3)) #/\ ((X#\=Y) #==> (Y#>3))

• Schéma d'appel :

  fd_cardinality(+liste_de_contraintes_booléennes,?variable_FD)

• Description :

  fd_cardinality(L,X) unifie X avec le nombre de contraintes de la liste L qui sont satisfaites.

• Exemple d'exécution :

  pour exprimer le fait qu'exactement 3 contraintes parmi les 5 contraintes C1, C2, C3, C4 et C5 doivent être vérifiées, on écrira :

  fd_cardinality([C1,C2,C3,C4,C5],3)

  tandis que pour exprimer qu'au moins 3 contraintes doivent être satisfaites, on écrira :

  fd_cardinality([C1,C2,C3,C4,C5],NbVrai), NbVrai#>=3

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

• Le prédicat fd_all_different/1 contraint un ensemble de variables FD à prendre des valeurs toutes différentes :
  
  
  • Schéma d'appel :

    fd_all_different(+liste_de_variablesFD)

  • Description :

    fd_all_different(L) contraint les variables de la liste L à prendre des valeurs toutes différentes deux à deux.

  • Exemple d'exécution :
    Pour le problème des 4 reines, on exprimera le fait que les reines doivent être placées sur des lignes différentes en écrivant :

    fd_all_different([X1,X2,X3,X4])

• Le prédicat fd_relation/2 permet de définir des contraintes en extension, en donnant explicitement les listes de valeurs que peut prendre une liste de variables :
  
  
  • Schéma d'appel :

    fd_relation(+liste_d_entiers,?liste_de_variablesFD)

  • Description :

    fd_relation(L_Valeurs,Vars) contraint la liste Vars à être égale à une des listes de la liste L_Valeurs.

  • Exemple d'exécution :

    fd_relation([[0,1,2],[3,4,5]],[X,Y,Z]) pose la contrainte "(X=0 et Y=1 et Z=2) ou (X=3 et Y=4 et Z=5)"

• Les prédicats fd_element/3 et fd_element_var/3 contraignent une variable à prendre une valeur de rang donné dans une liste de valeurs ou de variables donnée ; les prédicats fd_atmost/3, fd_atleast/3 et fd_exactly/3 imposent qu'un nombre donné de variables, parmi une liste de variables, prennent une valeur donnée.

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 :

• Schéma d'appel :

  fd_labeling(+liste_de_variables_FD)

• Description :

  fd_labeling(L) affecte une valeur à chaque variable FD de L de telle sorte que toutes les contraintes portant sur ces variables soient satisfaites. Lorsque Prolog "backtrack" sur ce prédicat, il cherche à chaque fois une solution différente.

• Exemple d'exécution :

  Pour le problème des 4 reines, après avoir déclaré 4 variables X1, X2, X3 et X4, et posé les contraintes sur ces variables, on peut demander à Gnu-Prolog de chercher une solution en écrivant : fd_labeling([X1,X2,X3,X4]).

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 :

• Schéma d'appel :

  fd_labeling(+liste_de_variables_FD,+liste_d_options)

• Description :

  fd_labeling(L,O) affecte une valeur à chaque variable FD de L de telle sorte que toutes les contraintes portant sur ces variables soient satisfaites ; O est une liste d'options qui spécifient l'ordre d'affectation des variables et des valeurs (liste des options possibles). L'option correspondant à l'heuristique "échec-d'abord", consistant à affecter en premier la variable dont le domaine a le plus petit nombre de valeurs localement consistantes avec l'affectation partielle en cours, est variable_method(first_fail). L'option backtracks(B) unifie B avec le nombre de retours en arrières effectués par l'algorithme pour trouver la solution.

• Exemple d'exécution :

  Pour le problème des 4 reines, pour demander à Gnu-Prolog d'énumérer les affectations en utilisant l'heuristique "échec-d'abord", on écrira :

  fd_labeling([X1,X2,X3,X4],[variable_method(first_fail)])

  Si en plus on souhaite que les valeurs soient énumérées de la plus grande à la plus petite (au lieu de la plus petite à la plus grande), on écrira :

  fd_labeling([X1,X2,X3,X4],[variable_method(first_fail), value_method(max)])

  Pour savoir combien de retours en arrière ont été effectués, on écrira :

  fd_labeling([X1,X2,X3,X4],[variable_method(first_fail), value_method(max),backtracks(B)])

  et on affichera la valeur de B.

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 :

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

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 :

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

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 :

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 :

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

On peut utiliser ce programme pour chercher les mariages stables :