next up previous contents index
Nächste Seite: 6.4.3 Heterogenes Constraint-Lösen Aufwärts: 6.4 Ein hybrides Constraint-System Vorherige Seite: 6.4.1 Ausführungsmodelle   Inhalt   Index

6.4.2 Hybridizität versus Heterogenität

Üblicherweise wird ein Constraint-Problem von einem einzigen Constraint-Solver mit einem eindeutigen Namensraum und eindeutigen Variablenbelegungen bzw. Wertebereichen bearbeitet. Unterschiedliche Constraint-Lösungsstrategien allerdings bedingen getrennt voneinander zu verarbeitende Teilbereiche des ursprünglichen Constraint-Problems. Unterschiedliche Constraint-Solver kooperieren in diesem Fall, um gemeinsam mögliche Lösungen für das Constraint-Problem zu generieren.

Ein wesentliches Problem in diesem Szenario ist, wie aus den einzelnen Teillösungen vollständige Gesamtlösungen (globale Lösungen) generiert werden können. Ein in diesem Zusammenhang zentraler Punkt betrifft die Frage, ob die Constraint-Netze der unterschiedlichen Constraint-Solver innerhalb von YACS denselben Namensraum aufweisen oder nicht, d.h. die Frage ob ,,Überlappungen`` der Constraint-Netze möglich sein sollen oder nicht, und wie diese zu behandeln sind. Überlappungen treten an den Stellen auf, an denen dieselben Variablen in den Constraint-Netzen mehrerer Strategien auftauchen.

Das Szenario mit voneinander getrennten, disjunkten Constraint-Netzen mit jeweils eigenem Namensraum ohne Überlappungen wird lokale Sicht genannt:

Definition 6.4.2   (lokale Sicht)
Für eine Menge von Problemen $\{P_1,\ldots,P_m\}$ und einer Menge von Variablen $\{v_1,\ldots,v_n\}$ bedeutet eine lokale Sicht, dass die Mengen der in zwei unterschiedlichen Problemen $P_1$ und $P_m$ enthaltenen Variablen $\{v_{1_1},v_{1_2},\ldots\}$ und $\{v_{m_1},v_{m_2},\ldots\}$ disjunkt sind.

Mit einer lokalen Sicht wäre das System hybrid, ließe aber keine Überlappungen zwischen den einzelnen Teilproblemen und den unterstützten Domänen zu. Eine derartige Verarbeitung innerhalb von YACS würde eine Vereinfachung bedeuten. Gleichzeitig wird das Problem allerdings verlagert, wenn für die übergeordnete Anwendung globale Lösungen für das Constraint-Problem benötigt werden. Hierfür ist ein einheitlicher Namensraum erforderlich. Existiert nur ein einziger Namensraum und sind Überlappungen von Constraint-Netzen unterschiedlicher Strategien zulässig, so wird dies globale Sicht genannt:

Definition 6.4.3   (globale Sicht)
Für eine Menge von Problemen $\{P_1,\ldots,P_m\}$ und einer Menge von Variablen $\{v_1,\ldots,v_n\}$ bedeutet eine globale Sicht, dass die Mengen der in zwei unterschiedlichen Problemen $P_1$ und $P_m$ enthaltenen Variablen $\{v_{1_1},v_{1_2},\ldots\}$ und $\{v_{m_1},v_{m_2},\ldots\}$ dieselben Elemente beinhalten können.

Ein System mit globaler Sichtweise ist nicht nur hybrid, es müsste zudem heterogene Constraints und damit heterogenes Constraint-Lösen unterstützen.

Für eine genauere Untersuchung erfolgt an dieser Stelle wiederum eine phasenweise Betrachtung des Constraint-Lösungsprozesses. Dies geschieht jeweils in Bezug auf voneinander getrennte Namensräume (lokale Sicht) und in Bezug auf denselben Namensraum für alle beteiligten Constraint-Verfahren (globale Sicht):

Während Preprozessingverfahren von der globalen Sicht i.A. nicht profitieren, ergibt sich für Konsistenzverfahren der Vorteil, dass bei überlappenden Constraint-Netzen Wertebereichseinschränkungen innerhalb von YACS global propagiert werden können, anstatt nur innerhalb des durch die jeweilige Strategie definierten Teilproblems. Ebenso ermöglicht die globale Sicht das Generieren globaler Lösungen für überlappende Constraint-Netze.

Wenn innerhalb von YACS hingegen eine lokale Sichtweise angenommen wird, führt dies zu einer Vereinfachung, da die Constraint-Verfahren jeder Strategie ausschließlich ihr zugewiesenes Teilproblem bearbeiten müssen. Übergreifende Wertebereichseinschränkungen könnten bei einer erneuten Propagierung verarbeitet werden. Globale Lösungen allerdings können von YACS in diesem Fall nur dann berechnet werden, wenn sichergestellt wird, dass sich die einzelnen Teilprobleme auch global nicht überlappen.

Werden in einer globalen Sichtweise überlappende Constraint-Lösungsstrategien, die Suchverfahren einsetzen, gleichzeitig mit solchen Strategien verwendet, in denen auf Suchverfahren verzichtet wird (Strategien, die lediglich die Wertebereiche durch Konsistenzverfahren einschränken), so muss die Lösungssuche für die betroffenen Variablen auch von einem übergeordnetem Lösungsmechanismus nicht geleistet werden. An den Stellen allerdings, wo es zu Überlappungen kommt, müssen für die betreffenden Constraints Lösungen berechnet werden, die konsistent mit den entsprechenden Wertebereichen sind.6.7

Abbildung 6.8: Einfaches Szenario mit zwei überlappenden Constraint-Netzen
\begin{figure}\centering
\includegraphics[width=14.8cm]{images/konzept_modell_3}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Überlappungen der Constraint-Netze unterschiedlicher Strategien können das Vermischen unterschiedlicher Wertedomänen bedeuten. Während dies in Szenario 1 aufgrund der begrenzten Anzahl Strategien bei Überlappungen grundsätzlich der Fall ist (vgl. Abbildung 6.8), kann dies auch in der Verallgemeinerung des Problems in Szenario 2 gegeben sein: Bei Überlappungen ist es möglich, dass intervallwertige Domänen infiniter Variablen von diskreten Werten finiter Variablen beschränkt werden und umgekehrt (vgl. Abbildung 6.9). Das in diesem Fall vorliegende CSP ist, wie in Abschnitt 4.4.4 beschrieben, ein Mixed CSP (vgl. Gelle und Faltings, 2003; Gelle, 1998) bzw. ein heterogenes Constraint-Problem (vgl. Benhamou, 1996):

Definition 6.4.4   (Heterogenes Constraint-Problem)
Ein heterogenes Constraint-Problem ist ein CSP, welches heterogene Constraints enthält. Heterogene Constraints sind Constraints über Variablen verschiedener Constraint-Domänen. Ein heterogenes Constraint-Problem setzt daher min. ein hybrides CSP voraus.

Die Einschränkung der Wertebereiche und die Lösungssuche hat in Bezug auf die globale Sicht analog zu anderen Überlappungen zu erfolgen. Zu beachten ist allerdings, dass in diesem Fall durch YACS automatische Konvertierungen der Wertebereiche vorgenommen werden müssen. Dies bedeutet eine Diskretisierung von intervallwertigen Domänen und umgekehrt die Propagation der Grenzen von Wertebereichen, wenn FD-Variablen von Intervall-Constraint-Solvern verarbeitet werden.6.8 Wenn Konvertierungen der Wertebereiche vorgenommen werden, ist von dem Wissensingenieur zu beachten, dass nach Möglichkeit keine ,,ungünstigen`` Domänen konvertiert werden. Das heißt, es sollte vermieden werden, dass z.B. eine Domäne mit den Werten $\{0,10000,1000000\}$ in eine (konvexe) Intervalldomäne konvertiert wird. Umgedreht sollte eine Variable mit einer intervallwertigen Domäne von bspw. $[0,1000000]$ nicht innerhalb eines FD-Constraints verwendet werden.6.9

Abbildung 6.9: Erweitertes Szenario mit überlappenden Constraint-Netzen
\begin{figure}\centering
\includegraphics[width=14.8cm]{images/konzept_modell_4}
\ifx\pdfoutput\undefined
\fi
\end{figure}

Die Überlappung von Constraints mit finiten und infiniten Wertedomänen kann dazu führen, dass wenn eine Intervallvariable von einem FD-Constraint beschränkt wird, dies (in Abhängigkeit von den Beschränkungen durch die Constraints) bei Auftauchen von Punktintervallen eine Kettenreaktion auslöst, an deren Ende ggf. alle Intervallvariablen auf einzelne Punktintervalle beschränkt sind. Wenn das System diskontinuierliche Intervalle unterstützt, tritt dieser Effekt bei überlappenden Constraint-Netzen verstärkt auf. Wenn hingegen ausschließlich konvexe Intervalle verarbeitet werden, tritt ein Informationsverlust auf, denn der FD-Solver hat ggf. mehr Werte aus einer Domäne herausgefiltert, als von den konvexen Intervallgrenzen umschlossen werden.



Fußnoten

...6.6
Sämtliche Teillösungen - auch unterschiedlicher Strategien - welche sich auf dieselbe Variablenmenge beziehen, müssen hierbei ggf. zusammen betrachtet werden, um eine vollständige Relation mit allen Abhängigkeiten zwischen diesen Variablen zu erhalten (vgl. Definition 4.1.2, totales Constraint).
...6.7
Durch eine erneute Propagation kann es bei Übernahme der Werte aus den Lösungsverfahren als neue Domänenwerte auch durch Konsistenzverfahren zu eindeutigen Lösungen kommen.
...6.8
Eine intelligente Diskretisierungsmethode würde bspw. eine FD-Variable mit dem Wertebereich $\{3,17,27\}$, welcher durch Intervallpropagationsverfahren auf das Intervall $[3,20]$ beschränkt wurde, bezogen auf den ursprünglichen Wertebereich auf die Werte $\{3,17\}$ beschränken, und das Constraint anschließend für eine erneute Propagation vorsehen.
...6.9
Alternativ könnte in letzterem Fall zur Effizienzverbesserung innerhalb der betreffenden Constraint-Lösungsstrategie für FD-Constraints ein Intervallverfahren als Preprozessing integriert werden.

next up previous contents index
Nächste Seite: 6.4.3 Heterogenes Constraint-Lösen Aufwärts: 6.4 Ein hybrides Constraint-System Vorherige Seite: 6.4.1 Ausführungsmodelle   Inhalt   Index