5.3.4.2.2 Globale Toleranzpropagation

Neben dem Ansatz des dynamic splitting, der bereits unter geeigneten Umständen zu globaler Konsistenz führt, gibt es ein weiteres Verfahren mit dem sich global konsistente Toleranzsituationen herstellen lassen. Ermöglicht wird dies, weil in der TP die Konsistenzbedingungen als solution functions angegeben werden (vgl. Hyvönen, 1992, S. 83). Da eine lokal konsistente Toleranzsituation nur dann gleichzeitig global konsistent ist, wenn das Constraint-Netz zyklenfrei ist, lässt sich globale Konsistenz erreichen, indem für die Constraints bzgl. kritischer Variablen algebraische Gleichungsumformungen zur Eliminierung eben dieser Variablen vorgenommen werden. Die durch diese algebraischen Transformationen entstehenden Konsistenzbedingungen werden global solution functions genannt (vgl. Hyvönen, 1992, S. 101 ff.):^5.100

Beispiel 5.3.9   Für das ICSP mit den beiden Constraints

$$C_1: v_1+v_2=v_3 \qquad \qquad \quad C_2: v_2+v_3=v_4$$

liefert lokale TP keine global konsistente Lösung. Der Constraint-Graph enthält einen Zyklus, da sowohl $v_2$ als auch $v_3$ in beiden Constraints enthalten ist. Wenn zur Eliminierung dieser Variablen die Gleichung des Constraints $C_2$ jeweils nach $v_2$ und $v_3$ aufgelöst in die Gleichung von $C_1$ eingesetzt wird, erhält man:

$$v_1+v_2=(v_4-v_2) \qquad \qquad v_1+(v_4-v_3)=v_3$$

Aufgelöst nach $v_2$ und $v_3$ ergibt dies die beiden folgenden neuen global solution functions:

$$v_2=\frac{v_4-v_1}{2} \qquad \qquad \qquad \quad v_3=\frac{v_1+v_4}{2}$$

Zusammen mit den beiden solution functions für $v_1$ und $v_4$ ergibt sich die folgende Agenda auszuwertender Funktionen für den Propagationsvorgang:

$$v_1=v_3-v_2, \qquad \quad v_2=\frac{v_4-v_1}{2}, \qquad \quad v_3=\frac{v_1+v_4}{2}, \qquad \quad v_4=v_2+v_3$$

Die restlichen lokalen solution functions $(v_2=v_3-v_1)$, $(v_3=v_1+v_2)$, $(v_2=v_4-v_3)$ und $(v_3=v_4-v_2)$ finden keine Anwendung, da sie für den ursprünglichen Zyklus im Constraint-Netz verantwortlich sind.

Die resultierenden impliziten Funktionen erlauben bei Anwendung von lokaler TP die Herstellung einer global konsistenten Toleranzsituation. Dieses Vorgehen wird globale Toleranzpropagation genannt. Problematisch ist die globale TP, weil nicht alle Gleichungen algebraisch umformbar sind, und universelle Verfahren bis heute nicht bekannt sind. In der Praxis sind diese Umformungen häufig so komplex, dass die globale Konsistenz als nur theoretisch erreichbar angesehen werden muss. Im praktischen Einsatz ist lokale TP anwendbar, wobei Hyvönen darauf hinweist, dass Constraint-Solver inkrementell erweitert werden können, so dass sie nach und nach eine größere Menge Transformationsregeln oder dynamic splitting unterstützen (vgl. Hyvönen, 1991, S. 249). Auf diese Weise werden möglichst viele Fälle abgedeckt, in denen globale Konsistenz herstellbar ist. Für alle weiteren Fälle werden höhere Grade lokaler Konsistenz erreichbar, auch wenn globale Konsistenz nicht garantiert werden kann.

Fußnoten

...^5.100

Auch: universal solution functions und universal relations (vgl. Hyvönen, 1989, S. 1197).