5.2.2 Lösen eines CSP

Mit Constraint Satisfaction wird die Suche nach einer global konsistenten Wertebelegung für alle Constraint-Variablen eines CSP bezeichnet, d.h. es müssen alle Constraints erfüllt sein. Ein Constraint wird erfüllt, wenn die Wertezuweisungen zu den jeweils involvierten Variablen den Anforderungen der Constraint-Relation genügen (vgl. Güsgen, 2000, S. 269):

Definition 5.2.4   (Constraint-Erfüllung)
Gegeben sei ein CSP mit den Constraints $C_1,\ldots,C_m$ auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Ein Tupel $(d_1,\ldots,d_n) \in D_1 \times \cdots \times D_n$ erfüllt ein Constraint $C_j$, $j \in \{1,\ldots,m\}$, falls die zu den Variablen von $C_j$ gehörenden Werte aus $(d_1,\ldots,d_n)$ ein Element der Relation von $C_j$ bilden.

Es genügt allerdings nicht, wenn jedes Constraint für sich genommen gültige Wertekombinationen aufweist, d.h. konsistent ist. Dies ist aber häufig die Vorstufe, um zu einer globalen Lösung eines CSP zu gelangen, welche ,,aus einer eindeutigen Belegung der Variablen mit genau einem Wert aus dem jeweiligen Wertebereich besteht, so dass alle Constraints erfüllt sind`` (Kolbe, 2000, S. 36). Die Lösung eines CSP lässt sich formal folgendermaßen definieren (vgl. Güsgen, 2000, S. 269):

Definition 5.2.5   (Lösung eines CSP)
Gegeben sei ein CSP mit den Constraints $C_1,\ldots,C_m$ auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Eine Lösung des CSP ist ein Tupel $(d_1,\ldots,d_n){}\in{}D_1{}\times{}\cdots{}\times{}D_n$, das $C_1,\ldots,C_m$ erfüllt.

Das Auflösen eines CSP stellt sich als Suche im Lösungsraum dar, welcher durch alle möglichen Lösungen aufgespannt wird. Jede Variable kann dabei Werte aus ihrem Wertebereich annehmen.^5.8 Je nach Fragestellung können unterschiedliche Ergebnisse erwünscht sein. So kann sich zum einen die Frage nach der Existenz einer Lösung stellen, zum anderen, wenn es mehrere Lösung gibt, die Frage nach deren Anzahl bzw. nach deren konkreten Ausprägungen. Weiterhin ist bei Optimierungsproblemen die Frage nach der besten Lösung von Interesse (vgl. Dechter, 1999, S. 195). Da bei einem CSP die Frage nach der Lösbarkeit gleichbedeutend mit der Suche nach der ersten Lösung ist, reduziert sich die Aufgabenstellung hier auf die Suche nach einer Lösung bzw. nach allen möglichen Lösungen (vgl. Kolbe, 2000, S. 37). Die Berechnung erfolgt durch spezielle Lösungsverfahren, die innerhalb von Constraint-Solvern implementiert werden. Durch Constraint-Solver wird die Trennung von Problemstellung und Lösungsverfahren realisiert, da sie generelle Mechanismen zum Auflösen von kombinatorischen Problemen, formalisiert als CSP, bieten. In ihnen können unterschiedliche Algorithmen Verwendung finden, die je nach Bedarf für bestimmte Problemstellungen optimiert sein können, und die ebenfalls nach Bedarf ein entsprechendes Antwortverhalten bieten. Die meisten Algorithmen zum Lösen eines CSP sind Varianten bzw. Kombinationen von Lösungsverfahren, die sich in zwei Klassen einteilen lassen: Konsistenzverfahren und Suchverfahren:

Konsistenzverfahren

werden von vielen Constraint-Solvern zum effizienten Auflösen von CSPs eingesetzt, um eine Reduzierung des Lösungsraums vorzunehmen, bevor sie eine global gültige Lösung suchen. Sie eliminieren ungültige Werte aus den Wertebereichen der Constraint-Variablen und stellen dadurch einen Grad lokaler Konsistenz her. Constraint-Solver, die lokale Konsistenz herstellen, sind korrekt, d.h. es gehen keine Lösungen verloren. Gleichzeitig sind sie unvollständig, da sie für gewöhnlich nicht alle ungültigen Werte aus den Wertebereichen herausfiltern. Dafür ist ihr Laufzeitverhalten i.d.R. auf polynomiale Laufzeitkomplexität beschränkt vgl. Mackworth und Freuder, 1985, S. 66; Marriott und Stuckey, 1999, S. 89. Nur in seltenen Fällen liegt nach dem Herstellen lokaler Konsistenz eine eindeutige Lösung vor. Vielmehr sind die Wertebereiche der Constraint-Variablen auf die Werte beschränkt worden, die potentiell Teil einer Lösung sind. Für manche Anwendungen, die z.B. außer Constraints noch weitere Inferenzmechanismen nutzen, kann dies bereits ausreichend sein. Für eine Konfigurierungsaufgabe können auf diesem Weg bereits ein Großteil inkonsistenter Variablenbelegungen herausgefiltert werden. Häufig werden konsistenzbasierte Verfahren mit einem darauf folgenden Suchalgorithmus kombiniert, bzw. werden bei jedem Schritt eines Suchalgorithmus dynamisch Konsistenztests zur Verkleinerung der zu durchsuchenden Wertebereiche ausgeführt, um zu global gültigen Lösungen zu gelangen (vgl. Güsgen, 2000, S. 275 ff.).

Suchverfahren

lassen sich in systematische und stochastische Verfahren einteilen. Systematische Suchverfahren basieren i.d.R. auf einem Backtracking-Ansatz. Beim einfachen, chronologischen Backtracking werden in einer Brute-Force-Suche alle möglichen Wertekombinationen für eine globale Lösung eines FCSP durch Aufzählen ermittelt.^5.9 Bei inkonsistenten Teilbelegungen erfolgt ein Zurücksetzen zum letzten konsistenten Zustand (engl. backtracking). Dieses systematische Vorgehen nimmt im ungünstigsten Fall exponentiellen Aufwand in Kauf, da der Aufwand für das Lösen von FCSP NP-vollständig ist. Für Backtracking und seine Varianten spricht, dass die Algorithmen vollständig sind, d.h. sie können immer entscheiden, ob das FCSP Lösungen besitzt, und welche das sind (vgl. Dechter und Frost, 2002; Kumar, 1992; Marriott und Stuckey, 1999).

Stochastische Suchverfahren werden oftmals auch lokale Suchverfahren (engl. local search), (heuristische) Reparaturverfahren oder GSAT-Verfahren (Greedy SATisfiability) genannt. Im Gegensatz zu systematischen Verfahren, folgen stochastische Suchverfahren keinem ,,Pfad`` zur schrittweisen Belegung der Constraint-Variablen mit Werten durch den Suchraum, sondern bewegen sich aufgrund von lokalen Kriterien und Zufallswerten. Die Suche beginnt mit einer zufälligen Wertezuweisung an alle Variablen. Schritt für Schritt wird diese Wertezuweisung durch Auswertung der vorliegenden Relationen ,,verbessert``, bis keine bzw. möglichst nur noch wenige Konflikte vorliegen. Stochastische Verfahren finden häufig auch in sehr großen Suchräumen relativ schnell eine Lösung. Zudem liegt zu jedem Zeitpunkt eine, wenn auch suboptimale, Lösung vor, da alle Variablen mit Beginn der Suche mit einem Wert belegt sind.^5.10 Allerdings besteht die Gefahr, dass die Algorithmen bereits bei einem lokalen Minima terminieren und keine global gültige Lösung finden.^5.11 Stochastische Verfahren sind heuristische, nichtdeterministische und unvollständige Suchverfahren, d.h. sie können im Gegensatz zu systematischen Verfahren nicht garantieren, dass eine oder gar alle Lösungen eines Problems gefunden werden. Beispiele für bekannte Ansätze sind Hill Climbing, Min-Conflicts, Simulated Annealing, Tabu-Suche und Genetische Algorithmen (vgl. Barták, 1999a,b; Minton et al., 1992; Tsang, 1993; Russel und Norvig, 2002).

Für bestimmte Anwendungen, für die frühzeitig eine teilweise korrekte Lösung nützlicher ist, als eine vollständige Lösung, deren Berechnung um ein vielfaches länger dauern würde, können unvollständige Suchverfahren sinnvoll sein. Sie stehen allerdings nicht im Fokus dieser Arbeit. Für Konfigurierungsaufgaben kann eine Reduktion des Lösungsraums durch Konsistenztechniken zum Ausschließen einer Vielzahl von fehlerhaften Konfigurationen sehr sinnvoll sein, wenn es, wie in ENGCON, übergeordnete Inferenzmechanismen zur weitergehenden Konfigurierung gibt. Ebenfalls wünschenswert ist die Berechnung einer oder aller globaler Lösungen, bzw. einer möglicherweise sogar optimalen Lösung, als Ergebnis eines vollständigen Suchverfahrens. Fatal für den Konfigurierungsvorgang könnte es sich allerdings auswirken, wenn der Constraint-Solver potentiell falsche Lösungen als Ergebnis einer unvollständigen Suche liefern würde. Diese suboptimalen Lösungen, in denen nicht alle Constraints erfüllt sind, würden, wenn dem nicht durch gesonderte Mechanismen Rechnung getragen wird,^5.12 unweigerlich in Konfigurierungskonflikten münden.

Daneben gibt es noch weitere spezielle, strukturbasierte Verfahren zum Auflösen von FCSPs. Strukturbasierte Verfahren nutzen neben Such- und Konsistenzverfahren besondere Eigenschaften der Topologie des Constraint-Graphen, um effizient zu einer Lösung zu gelangen vgl. Dechter, 1999, S. 196; Van Hentenryck und Saraswat, 1996, S. 708. Bekannte Verfahren sind das Tree-Clustering (vgl. Dechter und Pearl, 1989) und die Cycle-Cutset-Methode, auch Cutset Conditioning (vgl. Dechter, 1990a, S. 292 ff.) genannt. In Abhängigkeit von der Problemstellung können mit diesen Verfahren gute Ergebnisse erzielt werden. Sie sind allerdings ebenso wie stochastische Suchverfahren stark abhängig von der Problemstellung, da die Effektivität dieser Verfahren von der Struktur des jeweiligen Constraint-Graphen und den zum Einsatz kommenden Heuristiken abhängt. Sie sind daher nicht so ,,stabil`` bzw. ,,robust`` wie systematische Suchverfahren, die durch Konsistenztechniken unterstützt werden, insbesondere wenn alle Lösungen eines Problems gesucht werden.

Auf eine genauere Betrachtung von stochastischen und strukturbasierten Verfahren wird daher in dieser Arbeit verzichtet. Konsistenzverfahren und systematische Suchverfahren zur Auflösung von FCSP, bzw. der Kombination beider, wird in den folgenden beiden Abschnitten der Vorzug gegeben. Im nachfolgenden Abschnitt 5.2.3 werden eine Reihe von lokalen Konsistenzgraden und Algorithmen zu deren Herstellung vorgestellt. In Abschnitt 5.2.4 ff. hingegen werden systematische Suchverfahren zum Auffinden von globalen Lösungen beschrieben.

Fußnoten

...^5.8

Diese simultane Zuweisung von Werten zu den entsprechenden Variablen wird von Tsang (1993, S. 6) explizit als compound label definiert. Nach dieser Auffassung kann ein Constraint auch extensional als Menge von compound labels gesehen werden.

...^5.9

Tiefensuche in einem Suchbaum.

...^5.10

Die Algorithmen, die mittels einer stochastischen Suche arbeiten, werden deshalb auch anytime-Algorithmen genannt.

...^5.11

Das heißt es sind nicht alle Constraints erfüllt. In diesem Fall, muss der Suchalgorithmus entweder neu beginnen, oder mit Hilfe einer Heuristik versuchen, das lokale Minima zu verlassen.

...^5.12

Beispielsweise durch Constraint-Hierarchien oder partielles Constraint Satisfaction (vgl. Abschnitt 4.4.3).