5.3 Intervall Constraint Satisfaction Probleme

Neben klassischen CSP über finite Domänen stellt sich für die Constraint-Verarbeitung in ENGCON das Problem der Behandlung von reellwertigen algebraischen Constraints. Die Wertebereiche der Constraint-Variablen werden hier als Ober- und Untergrenzen von reellwertigen Intervallen definiert, zwischen denen sich unendlich viele, nicht abzählbare Elemente befinden (vgl. Benhamou, 2001; van Emden, 2002). Diese Wertebereiche werden deshalb auch kontinuierlich genannt. Der Einsatz von Intervall-Constraints bietet sich für eine Reihe von Szenarien an:

• Zur Behandlung unscharfer Informationen, d.h. wenn das Wissen über Parameter nur in Form eines Werteintervalls bekannt ist.

• Wenn die Aufzählung aller Lösungen nicht möglich ist, da unendlich viele existieren.

• Unterbestimmte Systeme, für die mehr als eine Lösung bzw. ein Lösungsintervall existiert, können besser behandelt werden. Beispiel: optimaler Drehzahlbereich für einen Motor ist $7000 \leq x \leq 9000$, d.h. $x \in [7000,9000]$.

• Statt kombinatorischer Verfahren über einzelne Werte, wird die gleichzeitige Einschränkung von unendlich vielen Werten ermöglicht.

Im Gegensatz zu diskreten, endlichen Wertebereichen, für die Konsistenz- und Lösungsalgorithmen die einzelnen Werte in den Domänen der Constraint-Variablen mittels kombinatorischer Methoden aufzählen und auf Zugehörigkeit zu den Constraint-Relationen überprüfen können, lässt sich im Fall von reellwertigen Intervallen nicht für jeden einzelnen Wert bestimmen, ob er als konsistente Belegung geeignet ist. Während CSPs über endliche Domänen zur Klasse der NP-vollständigen Probleme zählen, sind CSPs über unendliche Domänen unentscheidbar (vgl. Güsgen, 2000, S. 269). Daher werden hier durch Konsistenz- und Suchverfahren lediglich die Ober- und Untergrenzen der Intervalle überprüft bzw. angepasst, so dass inkonsistente Werte ausgeschlossen werden. Dieses Framework wird Interval Constraint Satisfaction Problem (ICSP) (vgl. Yang und Yang, 1997; Hyvönen, 1989,1992,1991; Chopra, 1997) genannt, ist aber auch unter den Namen Numerical Constraint Satisfaction Problem (NCSP) (vgl. Benhamou, 2001; Ruttkay, 1998; Silaghi et al., 2001; Vu et al., 2003c; Lebbah und Lhomme, 1998,2002; Lhomme, 1993; Vu et al., 2002) und Continuous Constraint Satisfaction Problem (CCSP) (vgl. Benhamou, 2001; Haroud und Faltings, 1994; Sam-Haroud und Faltings, 1996a,b; Sam-Haroud, 1995; Cruz und Barahona, 2003) bekannt. Für gewöhnlich werden reellwertige Intervalle vorausgesetzt, das Konzept lässt sich jedoch auch auf andere Domänen, wie diskrete Integer-Intervalle, verallgemeinern (vgl. Benhamou, 2001; Yang und Yang, 1997; Lhomme, 1993; Chopra, 1997).

Definition 5.3.1   (Intervall Constraint Satisfaction Problem, ICSP)
Ein Intervall Constraint Satisfaction Problem wird durch ein Tripel $(V,I,C)$ beschrieben. Neben den die Menge der Constraints $C$ beschränkenden Variablen $V = \{v_1,\ldots,v_n\}$ wird eine Menge von Intervallen $I = \{I_1,\ldots,I_n\}$ als Wertebereiche der Variablen mit $\{v_1 : I_1,\ldots,v_n : I_n\}$ definiert. $C$ ist die endliche Menge von Constraints $C_j(V_j)$, $j \in \{1,\ldots,m\}$. Jedes Constraint $C_j(V_j)$ setzt eine Teilmenge $V_j = \{v_{j_1},\ldots,v_{j_k}\} \subseteq V$ zueinander in Relation, und beschränkt den Lösungsraum der involvierten Variablen auf eine Teilmenge des kartesischen Produkts $I_{j_1} \times \cdots \times I_{j_k}$ von k Subintervallen.

Das kartesische Produkt mehrerer Intervalle wird aus geometrischen Gründen auch kurz Box genannt (siehe Abbildung 5.21). Ziel ist es, eine Menge n-stelliger, möglichst kanonischer Boxen zu isolieren, die den Lösungsraum des CSP approximieren, ohne gültige Lösungen zu verlieren. Jede n-stellige Box approximiert jeweils eine mögliche Lösung des CSP. Eine Box wird ,,kanonisch`` genannt, wenn sie aus Intervallen besteht, deren Grenzen entweder jeweils dieselben oder direkt aufeinander folgende Zahlen sind, d.h. wenn sie möglichst punktgenaue Lösungen darstellen. Um dies zu erreichen wird mittels Such- und Konsistenztechniken sowie mathematischer Verfahren durch den Raum navigiert, der durch das kartesische Produkt $I_1 \times \cdots \times I_n$ aufgespannt wird (vgl. Benhamou, 2001, S. 45). Für diese Art der Constraint-Propagation, auch Intervallpropagation genannt, gibt es eine Reihe von in den folgenden Abschnitten aufgezeigten Verfahren, die auch unter den Begriffen bound consistency und bound propagation zusammengefasst werden (vgl. Russel und Norvig, 2002, S. 148).

Abbildung 5.21: Lösungsraum für ein ICSP mit den Variablen $v_1$ und $v_2$

Constraint satisfaction über reellwertige Intervalle wurde erstmals von John G. Cleary und Ernest Davis betrachtet. Ziel von Cleary (1987) war es, im Rahmen von Constraint Logic Programming (CLP) Abhilfe für die Inkorrektheit von Fließkomma-Berechnungen in der Sprache Prolog zu schaffen. Die Bemühungen mündeten in einem neuem Prolog-Dialekt mit dem Namen BNR Prolog und führten seitdem zu einer Reihe weiterer CLP-Sprachen, die über integrierte Constraint-Solver in der Lage sind, reellwertige Intervall-Constraints zu verarbeiten vgl. Benhamou, 2001, S. 46; Sam-Haroud, 1995, S. 30.^5.85 Das Einschränken der Intervallgrenzen wurde von Cleary (1987) mittels einfachem Domänen-Splitting und einer Backtracking-Suche auf dem entstehenden Baum durchgeführt (vgl. Abschnitt 5.3.2). Davis (1987) hingegen adaptierte eine Version des Waltz-Filteralgorithmus für die Behandlung von Intervall-Constraints (vgl. Abschnitt 5.3.3). Bei diesen ersten Ansätzen waren für jede Constraint-Art jeweils spezielle Algorithmen notwendig, um eine Einschränkung der Wertebereiche vornehmen zu können.^5.86 Weiterentwicklungen dieser Verfahren wurden verallgemeinert, so dass beliebige algebraische Constraints verarbeitet werden können (vgl. Benhamou et al., 1994a; Hyvönen, 1992; Lhomme, 1993).

Den Verfahren zum Auflösen eines ICSP ist gemein, dass mit Hilfe von Intervallmathematik, bzw. sog. Intervallarithmetik, lediglich die Intervallgrenzen der Constraint-Variablen propagiert werden. Intervallarithmetik beschreibt dazu arithmetische Operationen auf Intervallen.

Fußnoten

...^5.85

Beispielsweise CLP(BNR), Prolog IV, Newton, Numerica, etc. (vgl. Abschnitt 4.5.1).

...^5.86

Vgl. global constraint, Abschnitt 4.1.