next up previous contents index
Nächste Seite: 4. Constraints - Konzepte Aufwärts: 3. Wissensbasierte Konfigurierung am Vorherige Seite: 3.7.3 Zusammenfassung   Inhalt   Index

3.8 Anforderungen an einen Constraint-Solver für EngCon

Nach dieser Übersicht über das Constraint-System von ENGCON werden nun die spezifischen Anforderungen aufgezeigt, die für das Konfigurierungswerkzeug ENGCON bzgl. eines Constraint-Solvers vorliegen:

Anforderungen an die Schnittstelle

Wie bei modernen, wissensbasierten Systemen üblich, sollte eine strikte Trennung von Kontrolle und Constraint-System eingehalten werden, um die Mächtigkeit der Constraints nicht durch eingreifende Steuerung, z.B. bzgl. der Reihenfolge oder der Anzahl der zu verarbeitenden Constraints, zu gefährden (Black-Box-Prinzip). Die Steuerung des Constraint-Systems darf sich nur auf die Schnittstelle zu selbigem beziehen (z.B. welcher Solver eingesetzt werden soll), nicht jedoch inhaltlich auf die Propagationsmechanismen der Constraint-Solver (vgl. Günter, 1992, S. 77).

Die zu ersetzende bzw. neu zu entwickelnde Komponente für das Constraint-System von ENGCON ist ausschließlich der Teil, mit dem Funktions- und Prädikat-Constraints ausgewertet werden. Die vorhandenen übergeordneten Bestandteile, des Pattern-Matching-Mechanismus, die konzeptuellen Constraints, das ENGCON eigene, interne Constraint-Netz, sowie die Mechanismen zum Auflösen von Tupel- und Java-Constraints bleiben unangetastet. Es ist notwendig, dass die neue Komponente in der Lage ist, weiterhin im Kontext des bestehenden Constraint-Systems zu arbeiten. Dafür müssen die vorhandenen Schnittstellen von ENGCON eingehalten werden.

Die Übergabe der Constraints eines Konfigurierungsproblems in ENGCON zur Auswertung an den Constraint-Solver erfolgt derzeit über eine einfache stringbasierte Schnittstelle. Dies ermöglicht eine transparente und intuitive Nutzung durch den Wissensingenieur bei der Modellierung der Wissensbasis. Eine neue Komponente sollte daher vorzugsweise, unabhängig von der Syntax, ebenfalls über einen stringbasierten Zugang verfügen.

Dynamik des Constraint-Netzes

Bedingt durch den interaktiven Konfigurierungsverlauf werden in ENGCON während einer Konfigurierung durch Zerlegungen und Spezialisierungen sukzessiv neue Komponenten generiert und zur aktuellen Teilkonfiguration hinzugefügt, bis diese eine konsistente und vollständige Lösung darstellt. Das Constraint-System von ENGCON unterstützt dementsprechend das inkrementelle Anwachsen des Constraint-Netzes und die Verwaltung neu hinzugekommener Abhängigkeiten (vgl. Abschnitt 3.6 und Abschnitt 3.7.2). Ebenso sollte es der zum Einsatz kommende Constraint-Solver aus Gründen der Effizienz ermöglichen, dass bei jedem Konfigurierungszyklus nicht das vollständige Constraint-Netz erneut instantiiert und die bisherige Propagation wiederholt werden muss, sondern lediglich die neuen Abhängigkeiten dem bestehenden Constraint-Netz inkrementell hinzugefügt und die Einschränkung der Wertebereiche fortgesetzt werden kann vgl. Frühwirth und Abdennadher, 1997, S. 41 f.; Marriott und Stuckey, 1999, S. 352 ff..

Das Constraint-System sollte Unterstützung für die Zurücknahme von Konfigurierungsentscheidungen bieten. Da dies sehr aufwendig ist, sollten Fehlentscheidungen möglichst von vorne herein ausgeschlossen bzw. frühzeitig erkannt werden. Das System sollte demnach korrekt und vollständig arbeiten und ausschließlich gültige Wertebereiche liefern, die einer konsistenten Konfiguration entsprechen.3.19 Auch außerhalb des Constraint-Systems kann es durch die Komplexität des Konfigurierungsproblems und der Größe der Domäne zu Fehlentscheidungen aufgrund von Heuristiken oder Benutzereingaben im Verlauf einer Konfigurierung kommen. Häufig müssen Entscheidungen getroffen werden, ohne dass alle beeinflussenden Informationen bereits vorliegen. Für die Rücknahme von Konfigurierungsentscheidungen muss es möglich sein, den alten Zustand des Constraint-Netzes wiederherzustellen.

Zu unterstützende Domänen

Während einer Konfigurierung in ENGCON müssen sowohl Elemente aus diskreten Wertemengen ausgewählt, als auch kontinuierliche Wertebereiche eingeschränkt werden können. Ein Constraint-System, welches ebensolche Konfigurierungsschritte unterstützt, muss infolgedessen Propagations- und Lösungsmechanismen sowohl für diskrete als auch kontinuierliche (Intervall-)Domänen aufweisen.

In technischen Domänen ist es häufig erforderlich, Constraints mit hoher Genauigkeit zu berechnen. Der in ENGCON derzeit eingesetzte, externe Constraint-Solver bewerkstelligt dies, indem die Wertebereiche der Constraint-Variablen als reellwertige Intervalle repräsentiert werden. Die Wertebereiche weisen demnach kontinuierliche Intervalldomänen, d.h. eine unendlich große, nicht abzählbare Anzahl von Elementen auf. Diese Repräsentation ist sehr flexibel, so dass sich alle benötigten Berechnungen auf Funktions-Constraints durchführen lassen. Diese Lösung weist jedoch einige Nachteile auf:

Sofern diskrete Wertebereiche einen bestimmten Umfang nicht überschreiten, lassen sich Abhängigkeiten zwischen diesen effektiv durch Tupel-Constraints extensional repräsentieren und verarbeiten. Bei größeren Wertebereichen ist diese Repräsentationsform allerdings ineffektiv und wartungsintensiv. Um die Abhängigkeiten zwischen Komponenten mit umfangreichen Wertebereichen adäquat repräsentieren und verarbeiten zu können, sind eine intensionale Repräsentation und entsprechende Constraint-Solver sowohl für diskrete als auch kontinuierliche Wertebereiche erforderlich.

Eigenschaften von Lösungsverfahren

Anforderungen an die Eigenschaften der Lösungsalgorithmen lassen sich nur allgemein formulieren, da ein Problem auf unterschiedliche Art und Weise als Constraint-Problem formalisiert werden kann. Je nachdem, wie dies innerhalb der Wissensbasis von ENGCON geschieht, und welche Eigenschaften das resultierende Constraint-Netz aufweist, können sich unterschiedliche Lösungsverfahren als effektiv erweisen (vgl. Abschnitt 4.3). Um größtmögliche Flexibilität bzgl. der zu verarbeitenden Constraints bieten zu können, sollte ein Constraint-System n-äre und nichtlineare Constraints sowie zyklische Strukturen des Constraint-Netzes unterstützen. Außerdem sollte das System bzgl. diskreter Wertebereiche nicht auf numerische Werte beschränkt sein, sondern ebenfalls die Möglichkeit bieten, symbolische Domänen einzuschränken.3.20 Bezogen auf kontinuierliche Intervalldomänen muss unterschieden werden zwischen ununterbrochenen und unterbrochenen Intervallen (vgl. Abschnitt 5.3.1.4). Die Möglichkeit zur Verarbeitung von Constraints bzw. Wertebereichen ist für beide Fälle wünschenswert, wobei sich Lösungen für ununterbrochene Intervalle auf Kosten der Vollständigkeit der Lösungen effizienter realisieren lassen, als für unterbrochene Intervalle.

Präzision versus Effizienz

Dem [*] bereits genannten Erfordernis an die Präzision von Lösungen steht oftmals der Wunsch nach Effizienz bei den zum Einsatz kommenden Lösungsverfahren und die Komplexität der Problemstellung entgegen. Das Constraint-System sollte demnach einen Kompromiss zwischen Effizienz und Qualität bzgl. der zu berechnenden Lösungen erlauben. Je nach Anwendungsdomäne, den vorhandenen Constraints, der bevorzugten Präzision und der benötigten Effizienz kann es sinnvoll sein, unterschiedliche Verfahren zur Auswertung der Constraints einzusetzen. Ein solches System sollte mehrere Constraint-Solver zur Auswahl bieten, von denen je nach Anforderung einer oder eine Kombination von Solvern ausgewählt werden kann. Bei Einschränkungen bzgl. der Präzision von Lösungsverfahren ist zu beachten, dass keine möglichen Lösungen verloren gehen dürfen, da sonst die Vollständigkeit des Verfahrens nicht gewährleistet ist.3.21

Performance

Grundsätzlich ist die Ausführungsgeschwindigkeit der Propagation abhängig vom Umfang des Constraint-Netzes. Je nach Wissensbasis und der Art und Weise, wie die Abhängigkeiten bzgl. der Konfigurierung modelliert wurden, sollten Constraint-Solver für ENGCON in der Lage sein, die Relationen in Constraint-Netzen mit bis zu mehreren hundert Variablen in einer akzeptablen Zeit zu berechnen. Akzeptabel ist für den Benutzer, der interaktiv eine Konfigurierung am Rechner vornimmt, lediglich eine Zeitspanne von wenigen Sekunden.

Je komplexer die modellierten Constraints, umso aufwendiger gestaltet sich deren Auswertung und umso mehr verlängert sich die Dauer der Propagation. Die Ausführungsgeschwindigkeit ist zudem abhängig von der eingesetzten Rechnerplattform bzw. den dort vorkommenden unterschiedlichen Hardware-Ausstattungen. Für den Betrieb von ENGCON kann der Einsatz relativ aktueller ,,Standard``-Hardware vorausgesetzt werden.

Voraussetzungen der Hard- und Software-Umgebung

Der ENGCON-Konfigurator ist vorrangig für die ,,Microsoft-Windows-NT``-Plattform auf aktueller x86-Hardware implementiert worden. Eine neue Constraint-Komponente muss daher ebenfalls auf dieser Plattform lauffähig sein.3.22

Vorzugsweise, um den Integrationsaufwand möglichst gering zu halten, sollte die neue Komponente wie auch ENGCON in der objektorientierten Programmiersprache Java implementiert sein oder über eine entsprechende Schnittstelle verfügen. Eine Implementierung in Java würde zudem eine weitestgehende Plattformunabhängigkeit garantieren, da in Java geschriebene Programme grundsätzlich plattformübergreifend überall dort ausgeführt werden können, wo eine Java-Laufzeitumgebung verfügbar ist. Dies sind neben Microsoft Windows im Wesentlichen diverse Unix-Derivate (Linux, Solaris, AIX, HP-UX, OpenVMS, True64, MacOSX, FreeBSD, OpenBSD, NetBSD, etc.), die auf unterschiedlichen Hardware-Architekturen lauffähig sind.

Um auf zukünftige Anforderungen flexibel reagieren und entsprechende Erweiterungen vornehmen zu können, ist es notwendig, über den Quellcode der Constraint-Komponente zu verfügen. Dieser sollte in einer erweiterbaren, modularen Form vorliegen.

Nach dieser Einführung in die Anwendungsdomäne, der wissensbasierten Konfigurierung mit ENGCON, und den dargelegten Anforderungen an einen Constraint-Solver zur Unterstützung des Konfigurierungsprozesses, werden in dem folgenden Abschnitt die grundlegenden Formalismen und Konzepte zur Constraint-Verarbeitung dargelegt, sowie bestehende Constraint-Systeme hinsichtlich ihrer Eignung für eine Integration in das Konfigurierungswerkzeug ENGCON untersucht.



Fußnoten

...3.19
Aus Komplexitätsgründen kann dies nicht immer eingehalten werden.
...3.20
Sofern sich diese durch algebraische Ausdrücke intensional formulieren lassen.
...3.21
Ausgenommen der spezielle Fall, in dem durch Benutzerwunsch festgelegt ist, dass z.B. aus Effizienzgründen ausschließlich die erste gefundene Lösung für ein Problem zur Weiterverarbeitung übernommen werden soll.
...3.22
Die Windows-NT-Produktfamilie von Microsoft für x86-Systeme besteht derzeit aus Windows NT 4.0, Windows 2000 und Windows XP.

next up previous contents index
Nächste Seite: 4. Constraints - Konzepte Aufwärts: 3. Wissensbasierte Konfigurierung am Vorherige Seite: 3.7.3 Zusammenfassung   Inhalt   Index