La 2B-consistance

Intuitivement, la 2B-consistance[16,15,6] est une consistance d'arc sur les bornes des domaines. Elle garantit que l'instanciation de l'une des variables mises en jeu par une contrainte possède un support validant cette contrainte dans les domaines des autres variables.

Définition 2.3 (2B-consistance d'une contrainte)   Soit $(\mathcal{X,D,C})$ un $\mathcal{CSP}$ et $c \in C$ une contrainte k-aire sur les variables $(x_1,\ldots,x_k)$. On dit que la contrainte $c$ est 2B-consistante ssi : $\forall i$, $D_{x_i}=\square\{x_i \in D_{x_i} \vert \exists v_1 \in D_{x_1} \ldots \exists v_k \in D_{x_k}$ tel que $c(v_1,\ldots,v_{i-1},x_i,v_{i+1},\ldots,v_k)$ est vérifiée }.
La notion $\square\{E\}$ désigne la plus petite boîte contenant tous les éléments de l'ensemble $E$.

Définition 2.4 (2B-consistance d'un $\mathcal{CSP}$)   Un $\mathcal{CSP}$ est 2B-consistant ssi toutes ses contraintes sont 2B-consistantes.

L'algorithme de calcul de la 2B, commence par construire un ensemble $Q$ de couples $<C,x>$, où $C$ est une contrainte du $\mathcal{CSP}$ et $x$ est une variable qui apparaît dans $C$. Chaque élement $<C,x>$ de cet ensemble est alors traité, en projetant le domaine des variables de la contrainte $C$ sur celui de la variable $x$. Une fois la projection effectuée on retire l'élément $<C,x>$ de $Q$,et ainsi de suite jusqu'à ce que $Q$ soit vide. Si le domaine de $x$ est modifié alors on rajoute à $Q$ l'emsemble $\{<C',y> \vert C \neq C', x,y \in variables(C'), y\neq x\}$, pour remettre à jour les variables liées à $x$ par une autre contrainte. Le point fixe est atteint lorsque $Q$ est vide.
Une trace de l'éxécution de la 2B sur l'exemple 1.1 est donnée en annexe.

Figure: Résolution du problème du quadrilatère par la 2B-consistance

Localité :
A chaque étape, on fait une projection sur le domaine $D_x$ de la variable $x$ et pour une contrainte $C$. Ce qui revient à éliminer les éléments de $D_x$ qui n'ont pas de support dans les domaines des autres variables de $C$. Or un élément $e$ de $D_x$ peut avoir un support localement pour chaque contrainte sans pourtant faire partie des solutions globales du système. C'est-à-dire qu'il n'existe pas forcément de valuation de toutes les autres variables qui satisfait l'ensemble des contraintes lorsque $x=e$. Dans l'exemple 1.1, si $x_C=2$, l'instanciation { $y_C=\sqrt{5}$} vérifie la contrainte $C_1$, l'instanciation {$y_C=0$, $y_D=0$, $x_D=6$} vérifie la contrainte $C_2$. Mais pourtant le point C= $(2,\sqrt{5})$ n'est pas solution du problème en entier, puisque le cercle centré en ce point et de rayon 4 n'a pas d'intersection avec le cercle de centre $B$ et de rayon 2 ( voir figure 2 ).

Décomposition des points :
Intuitivement la notion géomètrique de point dans un espace euclidien est indivisible. La 2B-consistance traite séparemment chaque variable du problème, ce qui implique que les domaines des composantes des points sont filtrés indépendemment. Comme on l'a vu dans la section précédente $x_C=2$ ne fait pas partie des solutions globales du système. Pourtant cette valeur aurait pu être éliminée si on avait instancié $y_C$ dans le même temps. Les seules valeurs possibles pour $y_C$ sont $\sqrt{5}$ et $-\sqrt{5}$, qui ne permettent pas de vérifier la contrainte $C_2$. On verra dans la section suivante pour quelles raisons la 3B-consistance résout ce problème, dans le cadre de cet exemple. Un contrainte de distance est une contrainte binaire au sens où elle lie deux points indépendants et non $2p$ coordonnées indépendantes. Pour garantir la validité d'une instanciation il faut donc instancier toutes les coordonnées d'un point simultanément.

Propagation de l'erreur :
Le but de la 2B-consistance est de trouver le plus petit intervalle qui encadre les solutions. Les équations de distances étant quadratiques, on est amené à évaluer la racine carrée d'un intervalle à chaque étape de l'algorithme. Or la racine carrée d'un intervalle n'est pas toujours un intervalle, par exemple $\sqrt{[4,9]}=[-3,-2]\cup[2,3]$. Par souci d'encadrer toutes les solutions par le plus petit intervalle et également pour éviter l'explosion combinatoire des domaines¹ , la 2B approxime grossièrement ce calcul, dans l'exemple précédent son évaluation serait $[-3,3]$. La propagation d'intervalles, accentuée par la décomposition des points, induit donc une propagation de l'erreur. Cette erreur est d'autant plus importante que les points sont éloignés dans le graphe de distance.

Convergence asymptotique :
Ce phénomène intervient lorsque des cycles aparaissent dans l'éxécution de la méthode. La fonction de projection retire très peu de valeurs d'un domaine, et la 2B doit propager cette information à travers plusieurs autres contraintes avant de pouvoir à nouveau retirer des valeurs de ce domaine. Considérons l'exemple suivant :

Exemple 2.2 (Convergence asymptotique)   Soient 3 points alignés sur l'axe horizontal $y=0$, $A(x_A,0)$, $B(x_B,0)$ et $C(x_C,0)$ tels que :

$AB=BC=8$ et $AC=16.0001$
$D_{x_A}=[0,4]$, $D_{x_B}=[8,12]$ et $D_{x_C}=[16,20]$.

Nos inconnues sont donc $x_A$, $x_B$ et $x_C$ et les contraintes :
$C_1$ : $(x_A-x_B)^2=8^2$
$C_2$ : $(x_B-x_C)^2=8^2$
$C_3$ : $(x_A-x_C)^2=16.0001^2$
Ce système n'a évidemment pas de solutions puisque $AB+BC < AC$.

Voici une trace informelle avec une illustration graphique de l'éxécution de la 2B sur cet exemple :

1. Les domaines de $A$ et $B$ vérifient la contrainte $C_1$.
2. Les domaines de $B$ et $C$ vérifient la contrainte $C_2$.
3. Pour la contrainte $C_3$, la projection de $x_C$ retire à $D_{x_A}$ un intervalle de taille 0.0001 $\Longrightarrow D_{x_A}=[0, 3.9999]$.
4. Pour la contrainte $C_3$, la projection de $x_A$ retire à $D_{x_C}$ un intervalle de taille 0.0001 $\Longrightarrow D_{x_C}=[16.0001, 20]$.
5. Pour la contrainte $C_1$, la projection de $x_A$ retire à $D_{x_B}$ un intervalle de taille 0.0001 $\Longrightarrow D_{x_B}=[8, 11.9999]$.
6. Pour la contrainte $C_2$, la projection de $x_B$ retire à $D_{x_C}$ un intervalle de taille 0.0001 $\Longrightarrow D_{x_C}=[16.0001, 19.9999]$.
7. Pour la contrainte $C_2$, la projection de $x_C$ retire à $D_{x_B}$ un intervalle de taille 0.0001 $\Longrightarrow D_{x_B}=[8.0001, 11.9999]$.
8. On reprend alors à l'étape 3 jusqu'à épuisement total des domaines puisque le système n'a pas de solutions.

Figure: Illustration de la convergence asymptotique sur l'exemple 2.2

Le temps d'éxécution de la 2B est de plusieurs secondes sur cet exemple à 3 points, ce qui est relativement long. De plus il ne s'agit pas d'un cas particulier de points alignés, car si l'on avait choisi $D_{x_A}=D_{y_A}$, $D_{x_B}=D_{y_B}$, $D_{x_C}=D_{y_C}$, le même comportement se serait reproduit, à savoir que tous les flottants sont retirés un par un dans chacun des domaines jusqu'à épuisement(voir l'exemple 4.1).