Für klassische Constraint Satisfaction Probleme mit finiten Domänen stehen eine Vielzahl an Constraint-Lösungsmethoden und Heuristiken zur Verfügung. Grundsätzlich wird zwischen Konsistenz- und (systematischen) Suchverfahren unterschieden. Durch die ausschließliche Anwendung von Konsistenzverfahren ist es außer in Ausnahmefällen nicht möglich, Lösungen für CSPs zu bestimmen. Stattdessen werden Konsistenzverfahren häufig als Preprozessing bzw. während eines Suchverfahrens, durch dessen Ausführung die eigentlichen Lösungen generiert werden, als look-ahead-Mechanismus eingesetzt. Um eine weitere Optimierung des Laufzeitverhaltens zu erreichen, können Suchverfahren durch Heuristiken zur Variablen- und Werteauswahl unterstützt werden.
Eine besondere Stellung nehmen binäre CSPs ein, da viele der existierenden Lösungsalgorithmen auf binäre Constraints beschränkt sind. Verbunden wird dies häufig mit dem Hinweis, dass sich die Verfahren grundsätzlich auf n-äre CSPs verallgemeinern lassen. Aufgrund der hohen Komplexität n-ärer Constraints sind tatsächlich nur wenige Algorithmen verallgemeinert worden. Die Möglichkeit zur Binärisierung n-ärer Constraint-Netze verbessert die Situation nicht wirklich, da durch die Umwandlung in eine extensionale Repräsentation in Form von ,,umfassenden Variablen`` ein sehr hoher Platzbedarf verbunden mit relativ hohem Berechnungsaufwand entsteht. Die Binärisierung n-ärer CSPs, um anschließend binäre Lösungsalgorithmen verwenden zu können, ist daher nur für überschaubare Problemstellungen zu empfehlen.
Im Rahmen dieser Arbeit soll als Grundausstattung für ein
Constraint-Framework eine Basis an soliden Lösungsverfahren
entstehen, die ein stabiles Laufzeitverhalten für möglichst viele
Problemstellungen bieten. Verfahren zur Berechnung globaler Konsistenz
sind i.A. zu aufwendig und zu ineffizient.
Kantenkonsistenz dagegen ist ein weit verbreitetes
Verfahren, welches einen angemessenen Kompromiss zwischen
Berechnungsaufwand und der Menge der gefilterten Werte darstellt.
Aufgrund der notwendigen extensionalen
Repräsentation für den AC-4-Algorithmus und
höher (durch support-Einträge), sowie
aufgrund des durchschnittlich besseren Laufzeitverhaltens
(vgl. Wallace, 1993) sollte dem
AC-3-Algorithmus bzw. einer der
weiterentwickelten Varianten (AC-8,
AC-2000, AC-2001,
AC-3.1, AC-
)
der Vorzug gegeben werden. Pfadkonsistenz ist für viele
Problemstellungen zu aufwendig. Für die vorhandenen Algorithmen ist
zudem eine Matrix-Repräsentation der Constraints erforderlich, was
das Verfahren aufgrund des entstehenden Ressourcenbedarfs ungeeignet
für umfangreiche Problemstellungen macht. Durch die
Matrix-Repräsentation sind Algorithmen zur Herstellung von
Pfadkonsistenz überdies auf binäre Constraints beschränkt.
Ausgeschlossen werden soll ein derartiger Constraint-Solver
allerdings nicht, denn u.U. ist ein Konsistenzgrad größer als
Kantenkonsistenz für bestimmte, überschaubare Problemstellungen
durchaus sinnvoll in Form einer Effizienzverbesserung.5.114 Weitere
Konsistenzarten sind Verallgemeinerungen (inverse Konsistenz,
(i,j)-Konsistenz) oder spezialisierte Varianten, die
bspw. dazu dienen, möglichst frühzeitig Inkonsistenzen festzustellen
(LAC) oder geringfügig höhere bzw. niedrigere
Konsistenzgrade anbieten als die Standardverfahren (DAC,
DPC, RPC, SAC,
SRPC, adaptive
Konsistenz). Diese Konsistenzen können bei speziellen
Problemstellungen sinnvoll sein, sie werden allerdings nicht
schwerpunktmäßig in dieser Arbeit behandelt.
Neben Filter- bzw. Konsistenzalgorithmen müssen durch die Constraint-Komponente verschiedene Suchverfahren angeboten werden, durch die Lösungen ermittelt werden können, sofern diese existieren. Für einfache Problemstellungen sollte, um unnötigen Overhead zu vermeiden, einfaches, chronologisches Backtracking nutzbar sein. Außerdem sollte für die Verarbeitung komplexer Constraint-Netze eine (konfliktbasierte) Backjumping-Variante angeboten werden, denn Backjumping ist, im Gegensatz zu anderen Suchverfahren mit look-back-Strategie wie Backchecking und Backmarking, mit dynamischen und damit leistungsfähigen Heuristiken zur Variablenordnung einsetzbar. Diese Suchverfahren sollten außerdem mit Filteralgorithmen als look-ahead-Mechanismus kombiniert angeboten werden (FC, MAC). Zur Variablenordnung sollte eine Kombination des fail-first-Prinzips und der maximum-degree-ordering-Heuristik ein stabiles Laufzeitverhalten bieten. Heuristiken zur Werteauswahl bringen, begründet durch den hohen Aufwand jeden einzelnen Wert zu betrachten, im Schnitt weniger Gewinn und müssen daher nicht vorrangig behandelt werden. Die Gefahr, durch derartige Ordnungsheuristiken unnötigen Overhead zu produzieren, ist ungleich größer. Werteordnungsheuristiken erhöhen die Effizienz von Suchverfahren zudem ausschließlich dann, wenn nicht alle Lösungen eines Problems benötigt werden.
Grundsätzlich sollten die oben genannten Verfahren auch für n-äre Constraint-Netze anwendbar sein, auch wenn der Einsatz aufgrund der hohen Komplexität derartig formulierter Problemstellungen nicht zu empfehlen ist.
Die Domänen reellwertiger algebraischer Constraints innerhalb von Intervall Constraint Satisfaction Problemen werden in Form von Intervallen mit oberer und unterer Grenze definiert. Kombinatorische Verfahren zur Aufzählung möglicher Lösungen versagen hier. Allerdings lassen sich, basierend auf intervallarithmetischen Grundlagen, Konsistenzalgorithmen wie aus Abschnitt 5.2 ff. bekannt in abgewandelter Form effizient anwenden. Die Wertebereiche der Constraint-Variablen werden hierbei möglichst weit eingeschränkt, ohne mögliche Lösungen des Problems zu verlieren. Durch ein Splitting der Wertebereiche können in einem weiterführenden Suchvorgang punktgenaue Lösungen ermittelt werden. Aufgrund einer Vielzahl von Splitting-Möglichkeiten führt dieses Verfahren bei umfangreicheren Problemen allerdings schnell zu einer kombinatorischen Explosion.
Basierend auf dem Waltz-Filteralgorithmus zur Herstellung von Kantenkonsistenz wurde von Davis (1987) das sog. Label Inference zur Einschränkung von Intervallgrenzen entwickelt. Weiterentwicklungen davon, die eine Zerlegung von Constraints in primitive Constraints vornehmen und dadurch eine generelle Anwendbarkeit ermöglichen, sind die Toleranzpropagation von Hyvönen (1992) und Hull-Konsistenz bzw. 2B-Konsistenz von Lhomme (1993).5.115 Während im Rahmen der Toleranzpropagation von Hyvönen (1992) Möglichkeiten aufgezeigt werden, mit denen durch (dynamic) Splitting und der Eliminierung von Zyklen im Constraint-Netz ggf. globale Konsistenz erreicht werden kann, werden von Lhomme (1993) im Rahmen der Hull-Konsistenz höhere Konsistenzgrade durch 3B- bzw. kB-Konsistenz definiert.
Eine weiterführende Methode von Benhamou et al. (1994a) zur Herstellung von Box-Konsistenz setzt numerisch-mathematische Verfahren ein. Eingebettet in einen Waltz-ähnlichen Filteralgorithmus wird das Newton-Intervallverfahren, zur Einschränkung der Intervallgrenzen genutzt. Auch hier lassen sich ggf. durch Splitting kanonische Lösungen generieren.
Ein weiterer Ansatz, die
-Baum-Methode von
Haroud und Faltings (1994), ist in der Lage, für ununterbrochene
Intervalle bzw. für Intervalle, die speziellen
Konvexitätsbedingungen genügen,
effizient globale Konsistenz sicherzustellen. Im Gegensatz zu
Waltz-basierten Verfahren garantiert
die -Baum-Methode durch ein
binäres Suchverfahren Konvergenz. Sie hat
allerdings im Gegensatz zu anderen numerischen Verfahren nicht die
Berechnung eines einzigen, optimalen Fixpunktes zum Ziel, sondern ist
eher dazu geeignet Lösungsräume zu berechnen, die von aus
Ungleichungen bestehenden Constraint-Problemen gebildet werden. Für
diese Fälle lässt sich eine kompakte Repräsentation des Lösungsraums
berechnen.5.116
Für die zu entwickelnde Komponente zur Verarbeitung von Constraints
mit infiniten Domänen in ENGCON ist es vorrangig erforderlich,
Algorithmen zum Einschränken der Intervallgrenzen zur Verfügung zu
stellen. Berechnungsverfahren explizit für kanonische Lösungen stehen
weniger im Fokus. Die Wertebereichseinschränkungen dagegen sollten so
weit wie möglich vorgenommen, d.h. die Lösungen so dicht wie
möglich umschlossen, werden. Dies lässt sich für eine Vielzahl an
Problemstellungen effizient mit Verfahren ähnlich dem
Waltz-Filteralgorithmus erreichen.
Die (lokale) Toleranzpropagation und die Algorithmen zur
Herstellung von Hull-Konsistenz
(2B-Konsistenz,
3B-Konsistenz) implementieren dies für
Intervalldomänen. Während für die Toleranzpropagation
bzw. für Hull-Konsistenz lediglich eine
Zerlegung der Constraints vorgenommen werden muss, ist für die
Herstellung von Box-Konsistenz die
Implementierung komplexer mathematischer Operationen und ein
automatischer Gleichungsumformer erforderlich, durch den die
Constraints in ein durch das
Newton-Intervallverfahren
verarbeitbares Format gebracht werden müssen. Für die
-Baum-Methode ist eine komplexe
Datenrepräsentation und eine aufwendige Projektion zu implementieren.
Im Gegensatz zu diesen Verfahren, die in ihrer Umsetzung sehr
aufwendig sind, ist eine Implementierung der
Toleranzpropagation bzw. von Algorithmen zur Herstellung
von Hull-Konsistenz innerhalb eines
vertretbaren Zeitaufwands möglich.
Aus Gründen der Komplexität sollten die in dieser Arbeit umgesetzten Verfahren ausschließlich konvexe Intervalldomänen verarbeiten. Zum einen steigt bei der Berechnung mit diskontinuierlichen Intervallen, d.h. mit Vereinigungsmengen einzelner Teilintervalle, der Berechnungsaufwand stark an, und zum anderen existieren für Berechnungen mit ununterbrochenen Intervallen bereits Werkzeuge, insbesondere für die Programmiersprache Java (z.B. IAMath, vgl. Abschnitt 4.5.2).
Im folgenden Kapitel wird ein Konzept vorgestellt, mit dem sich die unterschiedlichen, hier dargelegten Constraint-Lösungsverfahren für finite und infinite Domänen innerhalb eines hybriden Frameworks flexibel austauschen und kombinieren lassen.
-Baum approximiert
werden. Dies ist durch die der
-Baum-Methode eigenen
Repräsentation des Lösungsraums intuitiv weniger effizient
durchführbar, als mit anderen Verfahren.