Programmation par contraintes

Exemples d'applications

Génération d'emplois du temps
Planification
Diagnostic (rechercher les causes d'une panne)
Debugging de programmes
Conception d'interface (animées par exemple), vision, ...
Conception de systèmes distribués
Sequençage de l'ADN
Design de circuits électroniques

Les CSPs

Un CSP est défini par un tripler (V, D, C) :

→ Ensemble définit par (V, D, C)
→ Ensemble de domaines (1 par variable) => D = {D1, D2, ..., Dn}
→ Ensemble fini de contraintes => C = {C1, C2, ..., Cn}

On dit qu'une variable est assignée d'une valeur lorsqu'on lui attribue l'une des valeurs.

On appelle assignation partielle toute assignation où une partie des variables est assignée (pas toutes).

Quand les contraintes portent sur n variables, au maximum, on parle de CSP n-aires. Cas particulier des CSP binaires : ils ont une représentation grapique simple. Les variables sont représentés par des noeuds et les contraintes par des arcs.

Tout problème n-aire peut être ramené à un problème binaire.

Une solution est une assignation totale qui respecte toutes les contraintes.
Une solution partielle est une assignation partielle qui respecte toutes les contraintes

Problèmes :

Trouver une solution
Trouver une solution qui satisfasse un critère
Trouver toutes les solutions
Déterminer le nombre de solutions
Déterminer si une assignation totale est une solution
Déterminer si une solution partielle peut faire partie d'une solution totale
etc.

Un CSP qui n'a pas de solution est dit surcontraint, incohérent, inconsistent. On peut se demander quelles sont les causes de cette incohérence (recherche d'explications).

Dans un premier temps on s'intéresse aux problèmes dans lesquels toutes les contraintes doivent être satisfaites (contraintes "dures"). Mais dans la réalité, il est fréquent de traiter les problèmes pour lesquels certaines contraintes (de préférence soft constaints) peuvent être violées. Les contraintes peuvent être hiérarchisées en fonction d'un degré de préférence.

Exemple : les 4 reines

On représente un échiquier en 4x4. On base la réalisation des contraintes sur les colonnes (V1, V2, V3, V4) (implicitement, la contrainte qui fait que les reines ne doivent pas se trouver sur la même colonne est déjà résolue).

    V1  V2  V3  V4
  +---+---+---+---+
1 |   |   |   |   |
  +---+---+---+---+
2 |   |   |   |   |
  +---+---+---+---+
3 |   |   |   |   |
  +---+---+---+---+
4 |   |   |   |   |
  +---+---+---+---+

On peut représenter l'ensemble de ces contraintes comme suit :

Pour un problème avec 4 reines, l'arbe de possibilité a déjà 256 feuilles !

pour i1 de 1 à 4 faire
  v1 <- i1

  pour i2 de 1 à 4 faire
    v2 <- i2

    pour i3 de 1 à 4 faire
      v3 <- i3

      pour i4 de 1 à 4 faire
        v4 <- i4

        vérifier les contraintes

        (i3, i4) ∈ C34
        (i2, i3) ∈ C23
        ...
      fin
    fin
  fin
fin

Exemple : Le problème du zèbre

Enoncé : il y a 5 maisons de couleurs différentes 2 à 2. Elles sont habitées par des hommes de nationalité différentes. Chaque homme aime une marque de cigarettes et une boisson particulière et possède un animal de compagnie. Les couleurs des maisons sont : Rouge, Bleue, Jaune, Verte et Ivoire. Les nationalités sont : norvégienne, ukrainienne, anglais, espagnole et japonnaise. Les marques de cigarettes sont : Old-Gold, Parliament, Kools, Lucky et Chesterfield. Les animaux de compagnie sont : zèbre, chien, cheval, renard et escargots. Les boissons sont : café, thé, eau, lait et jus d'orange.

On sait que :

L'anglais vit dans la maison rouge
L'espagnol possède un chien
On boit un café dans la maison verte
L'ukrainien boit du thé
La maison verte est immédiatemment à droite de la maison ivoire
Le fumeur de Old-Gold possède des escargots
...

Traitement des CSPs

La recherche d'une solution ou de toutes les solutions se fait par énumération. On dit souvant par backtracking. On distingue :

L'étape de l'assignation d'une valeur (à choisir) à une variable (à choisir)
L'étape du test de cohérence de l'assignaton (partielle) courante
L'étape (éventuelle) de remise en cause (backtracking) d'un choix précédent, en cas de situtation d'échec

Dans la communauté CSP on classe les algorithmes en 2 groupes :

Le groupe des algorithmes de type look-back ou rétrospectifs : il s'agit des algorithmes qui effectuent un travail après l'assignation d'une variable.
Le groupe des algorithmes de type look-ahead ou prospectifs : il s'agit des algorithmes qui effectuent un travail de préparation avant l'assignation d'une variable.

Le backtracking

BT : Backtracking chronologique (on conserve l'ordre des opérations)
BJ : Backjumping

Le backtracking chronologique

Objectif :

Instancier progressivement les variables. Les valeurs et les variables sont ordonnées arbitrairement et de manière statique (l'ordre ne change pas en cours de traitement).
Faire un retour en arrière (backtracking) dès qu'on a essayé toutes les valeurs du domaine d'une variable et qu'à chaque fois on a été en présece d'une incohérence (au moins une contrainte est violée).

procédure BT
début
  i <- 1
  Di* <- Di

  tant que 1 <= i <= n faire
    soit // x une valeur prise dans Di* telle que l'assignation
         // courante soit cohérente

    OK <- false

    tant que non OK et Di* != ∅ faire
      soit x ∈ Di* : Di* <- Di* - {x}

      si // l'assignation courante est cohérente
        OK <- true
      fin
    fin

    si non OK // x n'existe pas
      backtracking
      i <- i - 1
    sinon
      i <- i + 1
      Di* <- Di
    fin
  fin

  si i = 0
    renvoyer(UNSAT)
  sinon
    renvoyer(assignation courante)
  fin
fin

Forces et faiblesses

Très facile à programmer
Souffre du phénomène de trashing : BT refait souvent plusieur fois la même chose car los d'une backtrack, BT oublie ce qui vient d'être fait.
Le backtrack se fait systématiquement sur la dernière variable assignée.

Lorsqu'on fait un backtrack sur la variable X_i-1 on ne se préoccupe pas (à tord) de savoir s'il y a une contrainte entre X_i et X_i-1. Dans le backjumping, on prend en compte cette remarque.

Le backjumping

Quand on ne peut pas assigner de valeur à la variable X sans faire apparaître d'incohérence, le backjump se fait vers la variable la plus "récente" Y "connectée" à X.

Forward checking

Idée (simple et naturelle) : dès qu'une vafiable est instanciée, on propage vers les variables non encore instanciées.

On réduit le domaine des autres variables en fonction de la nouvelle instanciation.

Version 1 : dès qu'une variable est instanciée, on propage vers les prochaines variables non encore instanciées.

Version 2 : dès qu'une variable est instanciée, on propage vers toutes les variables non encore instanciées.

Lorsque le domaine d'une variable est vide, on revient sur le travail effectué auparavant.

Elements de complexité

Nombre de noeuds visités

                 +----+
                 | BT |
                 +----+
                   |
                 +----+
                 | BJ |
                 +----+
                   /\
                  /  \
                 /    \
            +----+    +-----+
            | FC |    | CBJ |
            +----+    +-----+

Le filtrage

Objectif :

Limiter la taille de l'espace de recherche de solutions
Supprimer des domaines les valeurs des variables qui ne sont dans aucune solution
On dit qu'on renforce la consistance ou qu'on filtre

Il y a plusieurs niveaux de consistances. Exemple : consistance locale, consistance de chemin. Plus la consistance est forte, plus l'espace de recherche est réduit mais plus il faut des traitements lourds et coûteux.

Problème : peut-on trouver les solutions uniquement par filtrage ?

Node consistency

Il s'agit d'un filtrage trivial. On ne traite que les contrainte d'arité 1 (qui ne portent que sur une seule variable) : on parle également de contrainte sur les domaines.

procédure NC(i : une variable du CSP)
début
  Di <- Di ∩ { x / Ri(x) }
fin

procédure NC(CSP : un CSP)
début
  pour tout i dans CSP
    NC(i)
  fin
fin

Filtrage d'arc

Ces algorithmes sont également qualifiés de propagation par contraintes et on dit qu'ils font du filtra local. Ils sont généralement simples à mettre en oeuvre et fournissent un bon compromis entre réduction de l'espace de recherche et le temps de calcul.

Historiquement, l'idée est née dans le domaine de la vision (reconnaissance de forme).

AC1

AC1 est trivial : on traite de manière cyclique tous les arcs du réseau. Dès qu'il est possible de réduire un domaine grâce à un arc, on réitère le processus.

procédure AC1(G : un réseau)
début
  Q <- { (i, j) / arc(i, j) dans G ∧ i != j }

  répéter
    CHANGE <- faux

    pour chaque (i, j) dans Q faire
      CHANGE <- (REVISE((i, j) ∨ CHANGE)
    fin
  jusqu'à non CHANGE
fin

fonction REVISE((i, j) : un arc du réseau G) : booléen
début
  DELETE <- faux

  pour chaque vi dans Di faire
    si { vj appartient a Dj / R(vp vj)}
    fin
  fin

  retourner DELETE
fin

AC2

AC1 est trivial : on traite de manière cyclique tous les arcs du réseau. Dès qu'il est possible de réduire un domaine grâce à un arc on réitère le processus.

AC3

AC3 : on considère chaque arc (k, m). Si l'on modifie le domaine de la variable k, alors il y a des chances pour que l'on soit amené à modifier le domaine de ses noeuds prédécesseurs.

AC4

Notion de support : le support d'une valeur a pour une variable V_i par rapport à la contrainte C_ij est l'ensemble des valeurs b des autres variables V_j telles que (a, b) ∈ C_ij(V_i, V_j).

Idée : dès qu'une valeur n'a plus de support, elle peut être supprimée du domaine auquel elle appartient ce qui entraine une révision des supports des valeurs qu'elle supporte.

On construit l'ensemble des paires [(i, j), b] qui représentent les relations R_ij(b, ?).

AC6

AC6 se base également sur la notion de support mais au lieu de gérer tous les supports de chaque valeur, ici on se limite à gérer l'existence d'au moins un support pour chaque valeur. Une valeur a de la variable i est viable si pour chaque contrainte Cij la variable j possède une valeur b qui supporte a. Seules les valeurs viables doivent être conservées, les autres peuvent êtres supprimées.

Éléments de compléxité

Éléments caractéristiques d'un CSP :

Taille des domaines (a = taille du plus grand domaine)
Nombre de variables (n)
Nombre de contraintes (e)

Consistances plus fortes

Peut-on filtrer plus fortement ?

Oui ! Au lieu de travailler uniquement avec des relations entre 2 variables on peut travailler avec des relations sur 3 variables ou plus.

Définitions :

Un CSP est k-consistant si toute affectation de k-1 variables peut être éténdu en une affectation de k variables.
Un CSP est fortement k-consistant si ∀ j ≤ k, il est j-consistant
Un CSP est chemin-consistant s'il est fortement 3-consistant
Un CSP est (i, j)-consistant si toute affectation de i variables peut être étendue en une affectation de i+j variables

M2