5.3.3 Label Inference

Zur Einschränkung von Intervallgrenzen adaptierte Ernest Davis auf intervallarithmetischen Grundlagen den Waltz-Algorithmus zur Filterung ungültiger Werte aus den Domänen der Constraint-Variablen. Davis (1987) nennt den Effekt Label Inference und bezeichnet damit das sukzessive Ableiten von Wertebereichseinschränkungen und das Belegen der Variablen bzw. Knoten im Constraint-Netz mit der Menge der jeweils möglichen Werte (engl. interval labeling).

Davis (1987) definiert für den Vorgang des Einschränkens der Intervallgrenzen, auch (engl.) label refinement genannt, eine Funktion REFINE, die innerhalb der REVISE-Prozedur des Waltz-Algorithmus (siehe Abbildung 5.23) aufgerufen wird (vgl. Davis, 1987, S. 285):

Definition 5.3.9   (REFINE-Funktion)
Sei C ein Constraint mit den Variablen $v_1,\ldots,v_k$. Sei das Intervall $I_i$ der Wertebereich für $v_i$. Dann sei

$$\begin{eqnarray*} \textup{REFINE}(C,v_j) = \{a_j \in I_j \mid \exists(a_i \in I_i, i=1,\ldots,k, i\neq j): \\ C(a_1,\ldots,a_j,\ldots,a_k)\}. \end{eqnarray*}$$

Abbildung 5.23: Intervallpropagation basierend auf dem Waltz-Algorithmus (vgl. Davis, 1987, S. 286)

Der Aufruf REFINE$(C,v_j)$ liefert somit die Menge der Werte für $v_j$, die konsistent mit dem Constraint C und allen anderen Wertebereichen $I_i$ sind. Ein Wert $a_j$ befindet sich in dieser Ergebnismenge, wenn er in $I_j$ ist und Teil des k-stelligen Tupels $a_1,\dots,a_k$ ist, der das Constraint $C$ mit den Wertebereichen $I_i$ erfüllt. Eingebettet in die Prozedur REVISE schränkt diese nun, sofern dies aufgrund des Constraints $C$ möglich ist, mit Hilfe von REFINE der Reihe nach die Wertebereiche für alle beteiligten Variablen $v_1,\ldots,v_k$ ein, und gibt die Menge der Variablen zurück, deren Wertebereiche sich geändert haben. Die Ausführung dieser Version des Waltz-Algorithmus soll an dieser Stelle durch ein Beispiel erläutert werden (vgl. Davis, 1987, S. 286 f.):

Beispiel 5.3.5   Die beiden Constraints

$$C_{1,2,3}: v_1 + v_2 = v_3 \quad \mbox{und} \quad C_{1,2}: v_2 \leq v_1$$

mit den Wertebereichen

$$v_1: [2,12], \quad v_2: [4,9], \quad v_3: [2,8]$$

würden durch den Algorithmus auf die folgende Weise verarbeitet werden: Bei Beginn sind in der Warteschlange $Q$ die beiden Constraints $C_{1,2,3}$ und $C_{1,2}$ enthalten.^5.94

$C_{1,2,3}$ wird aus der Warteschlange herausgenommen.
$\rightarrow$ Da $v_1 \geq 2$ und $v_2 \geq 4$, ergibt $C_{1,2,3}$ für $v_3 \geq 6$, daher Einschränkung von $v_3:[6,8]$.
$\rightarrow$ Da $v_3 \leq 8$ und $v_2 \geq 4$, ergibt $C_{1,2,3}$ für $v_1 \leq 4$, daher Einschränkung von $v_1:[2,4]$.
$\rightarrow$ Da $v_3 \leq 8$ und $v_1 \geq 2$, ergibt $C_{1,2,3}$ für $v_2 \leq 6$, daher Einschränkung von $v_2:[4,6]$.
Weil sich die Wertebereiche von $v_1$ und $v_2$ geändert haben, wird $C_{1,2}$ zur Warteschlange hinzugefügt.

$C_{1,2}$ wird aus der Warteschlange herausgenommen.
$\rightarrow$ Da $v_1 \leq 4$, ergibt $C_{1,2}$ für $v_2 \leq 4$, daher Einschränkung von $v_2:[4,4]$.
$\rightarrow$ Da $v_2 \geq 4$, ergibt $C_{1,2}$ für $v_1 \geq 4$, daher Einschränkung von $v_1:[4,4]$.
Weil sich die Wertebereiche von $v_1$ und $v_2$ geändert haben, wird $C_{1,2,3}$ zur Warteschlange hinzugefügt.

$C_{1,2,3}$ wird aus der Warteschlange herausgenommen.
$\rightarrow$ Da $v_1 \geq 4$ und $v_2 \geq 4$, ergibt $C_{1,2,3}$ für $v_3 \geq 8$, daher Einschränkung von $v_3:[8,8]$.
Weil sich der Wertebereich von $v_3$ geändert hat, $v_3$ allerdings nirgends außer in $C_{1,2,3}$ vorkommt, wird kein weiteres Constraint zur Warteschlange hinzugefügt.

Aufgrund der nun leeren Warteschlange wird der Algorithmus beendet. Die Einschränkung der Wertebereiche hat in diesem Fall zu einem eindeutigen Ergebnis in Form von Punktintervallen geführt:

$$v_1: [4,4], \quad v_2: [4,4], \quad v_3: [8,8]$$

Dieser frühe Versuch zur Anwendung von Konsistenztechniken und Constraint-Propagation auf kontinuierliche Domänen war allerdings mit erheblichen Problemen behaftet vgl. Davis, 1987, S. 305; Sam-Haroud, 1995, S. 28. So garantiert das eingesetzte Verfahren Konvergenz und Vollständigkeit nur für eingeschränkte Constraint-Klassen. Bei nichtlinearen Constraints ist das Verhalten nicht vorhersagbar und führt (1) häufig zur frühzeitigen Beendigung der Filterung ohne das Konsistenz hergestellt wird (engl. early quiescence), bzw. (2) dass der Prozess in eine Endlosschleife läuft (engl. cycling) oder (3) nur sehr langsam konvergiert und dadurch zu unakzeptablen Antwortzeiten führt (engl. slow convergence).

Beispiel 5.3.6   Gegeben sei das einfache ICSP mit den beiden Constraints

$$C_1: v_1 = v_2 \qquad \qquad \quad C_2: v_2 = \frac{v_1}{2}$$

und den Wertebereichen $v_1:[0,100]$ und $v_2:[0,100]$. Bei jedem Durchlauf des Propagationsalgorithmus werden die Obergrenzen der Intervalle halbiert. Das ICSP ist in dem Augenblick konsistent, wenn $v_1=v_2=0$. Dieser Fixpunkt wird allerdings theoretisch nie erreicht, da sich die Wertebereiche ihm nur asymptotisch annähern.^5.95

Davis schlägt mehrere Möglichkeiten vor, dem Problem der Terminierung zu begegnen: Abbruchkriterien könnten z.B. ein Zeitlimit für die Propagation, eine Obergrenze für die Anzahl der Auswertungen einzelner Constraints oder eine Beschränkung der Genauigkeit sein, ab der Intervallgrenzen als identisch angesehen werden (vgl. Davis, 1987, S. 305).

Ein weiteres Manko ist, dass die Anwendung des Waltz-Algorithmus lediglich lokale Konsistenz garantiert, d.h. Konsistenz bezogen auf jeweils ein Constraint, und keine globale Konsistenz, bei der die Wertebereiche der Variablen bzgl. sämtlicher Constraints konsistent sind. Trotzdem ist dieses Verfahren für viele Anwendungen bereits ausreichend, und wurde daher in der Vergangenheit in unterschiedlichen Variationen in einer Reihe von Systemen eingesetzt.

Fußnoten

...^5.94

Nachfolgend werden aus Gründen der Übersichtlichkeit ausschließlich Operationen aufgeführt, die eine Änderung der Wertebereiche bewirken.

...^5.95

In der Praxis terminiert dieser Vorgang irgendwann, da die Intervallgrenzen im Rechner nur mit begrenzter Genauigkeit repräsentiert werden können.