|
[1]
|
Wolfgang Runte.
YACS: Ein hybrides Framework für Constraint-Solver zur
Unterstützung wissensbasierter Konfigurierung.
Diploma Thesis, University of Bremen, January 27, 2006.
[ bib |
.pdf |
.pdf |
.ps.gz |
.dvi |
.html |
html.tar.gz |
www |
project ]
In wissensbasierten Konfigurierungssystemen werden
Komponenten zur Constraint-Verarbeitung für die
Verwaltung von Abhängigkeiten während des
Konfigurierungsprozesses eingesetzt. Die Effizienz
von Constraint-Lösungsverfahren ist allerdings
stark problemabhängig. Zudem kann es aufgrund
einer Vielzahl unterschiedlicher Domänen und der
Vielfältigkeit der Anwendungsszenarien notwendig
werden, an die jeweilige Domäne angepasste
Constraint-Lösungsverfahren einzusetzen. Zur
Behandlung von unterschiedlichen
Constraint-Domänen innerhalb des
strukturbasierten Konfigurierungswerkzeugs EngCon
sind Constraint-Solver sowohl für finite als
auch infinite Domänen erforderlich. Die
Steuerung muss durch eine Komponente geleistet
werden, mit der sich unterschiedliche
Constraint-Solver je nach Bedarf und
domänenspezifisch einsetzen lassen. Die
Modularität ist dabei entscheidend für die
Austauschbarkeit einzelner Komponenten. Es stellt
daher einen sinnvollen Ansatz dar, ein modulares
Constraint-Framework einzusetzen, in das je nach
Bedarf, und dem in der jeweiligen Wissensbasis
definiertem Problem, unterschiedliche
Constraint-Solver mit jeweils für das
spezifische Problem effizienten Lösungsverfahren
eingesetzt werden können. Das Framework wird
durch einen strategiebasierten Ansatz
unterstützt, der eine flexible Kooperation
unterschiedlicher Constraint-Lösungsalgorithmen
erlaubt. Die Arbeit gliedert sich in die folgenden
Abschnitte: Nach der Einleitung erfolgt in Kapitel 2
eine Einführung in die wissensbasierte
Konfigurierung und ein Überblick über
unterschiedliche Methoden zur Konfigurierung sowie
existierende Konfigurierungswerkzeuge. In Kapitel 3
wird ein detailierter Überblick über das
strukturbasierte Konfigurierungswerkzeug EngCon
gegeben. Es werden die konzeptionelle Architektur
sowie die unterschiedlichen Wissensarten
beschrieben. Daneben enthält das Kapitel eine
Übersicht und eine Diskussion zum vorhandenen
Constraint-System von EngCon sowie die Anforderungen
von EngCon bzgl. der einzusetzenden
Constraint-Lösungsverfahren. Das Kapitel 4
enthält eine Einführung in den
Constraint-Formalismus und Übersichten sowohl zu
den Eigenschaften von Constraints als auch zu den
bestehenden Konzepten zur Constraint-Verarbeitung.
Auserdem beinhaltet dieses Kapitel eine
ausführliche Evaluierung und Bewertung
existierender Constraint-Systeme hinsichtlich ihrer
Eignung für eine Integration in das
Konfigurierungswerkzeug EngCon. Das Kapitel 5
unterteilt sich in zwei Bereiche: Im ersten Teil des
Kapitels werden Konsistenz- und Suchverfahren zum
Propagieren und Lösen von klassischen
Constraint-Problemen mit finiten Domänen
behandelt. Dies beinhaltet Heuristiken zur
Optimierung der Lösungssuche. Neben den
Lösungsverfahren für binäre
Constraint-Probleme werden auserdem Verfahren
für n-stellige Probleme
vorgestellt. Im zweiten Teil des Kapitels wird ein
Überblick über Lösungsverfahren für
intervallwertige Constraint-Probleme gegeben. Neben
intervallarithmetischen Grundlagen beinhaltet dies
Splitting-Techniken und Konsistenzalgorithmen,
angewendet auf Intervalldomänen. In Kapitel 6
wird das Konzept für ein hybrides
Constraint-System entwickelt. Eingebettet in eine
modulare und wiederverwendbare Framework-Architektur
ist es strategiebasiert, wodurch sich
Lösungsverfahren flexibel einsetzen und
austauschen lassen. Zur Verarbeitung von hybriden
Constraint-Problemen wird die Funktion eines
Meta-Constraint-Solvers zum Lösen von
heterogenen Constraints spezifiziert sowie mehrere
Szenarien zur Umsetzung des Systems aufgezeigt. In
Kapitel 7 wird die Implementierung des
YACS-Frameworks dargelegt. Es werden der Reihe nach
die enthaltenen Komponenten aufgezählt und
dokumentiert. Abschliesend erfolgt die
Beschreibung der Integration von YACS in das
Konfigurierungswerkzeug EngCon. In Kapitel 8 folgt
eine Validierung der Umsetzung von YACS anhand der
realisierten Funktionalität und der zuvor
benannten Anforderungen. Neben synthetischen
Problemstellungen wird die Integration des
YACS-Frameworks in das strukturbasierte
Konfigurierungswerkzeug EngCon
validiert. Auserdem erfolgt eine Positionierung
im Vergleich mit weiterführenden Arbeiten. In
Kapitel 9 erfolgt eine Zusammenfassung sowie ein
kurzer Ausblick hinsichtlich der
Erweiterungsmöglichkeiten der Konzeption und des
entwickelten Prototypen. Neben den genannten
Kapiteln enthält die Arbeit eine Reihe von
ergänzenden Anhängen.
|