next up previous contents index
Nächste Seite: 4.6 Fazit Aufwärts: 4.5.4 Kooperative Ansätze Vorherige Seite: 4.5.4.1 Ad-hoc-Kooperationen   Inhalt   Index

4.5.4.2 Flexible Kooperationen

In ihrer Dissertation stellt Petra Hofstedt ein allgemeines und formales Schema für die Kombination von Constraint-Systemen und die Kooperation von Constraint-Solvern zur Behandlung von Constraints mit vermischten Wertedomänen vor (vgl. Hofstedt, 2001). Strategien werden hier in Form von frei modellierbaren Kooperationsstrategien eingesetzt. Mit diesen kann beschrieben werden, welche Constraint-Verfahren wie und in welcher Reihenfolge (sequentiell/parallel) kombiniert werden. Ebenfalls ist in diesem Ansatz ein Meta-Constraint-Solver vorgesehen, der allerdings im Wesentlichen zur Verwaltung des Constraint-Netzes und zur Koordinierung der einzelnen Constraint-Solver eingesetzt wird (vgl. Hofstedt, 2000). Das theoretische Schema von Hofstedt (2001,2000) wurde im Rahmen einer Diplomarbeit prototypisch in der Programmiersprache Java umgesetzt (vgl. Godehardt und Seifert, 2001). Als Constraint-Solver kommen der IASolver für reellwertige Intervalle (vgl. Abschnitt 4.5.2), eine Reimplementierung der C-Lib für finite Domänen (vgl. Abschnitt 4.5.2) und ein eigenimplementierter Simplex-Solver für linear-arithmetische Constraints zum Einsatz (vgl. Hofstedt et al., 2001, S. 13 ff.). Das von Hofstedt (2001,2000) vorgestellte formale Schema ist sehr flexibel, allerdings auch sehr komplex, so dass die Implementierung dagegen recht einfach gehalten ist und nur eine einzige, statische Kooperationsstrategie enthält (vgl. Hofstedt et al., 2001, S. 16). Neuere Arbeiten zielen daher darauf ab, mögliche Strategien mittels einer Beschreibungssprache (engl. strategy description language) dynamisch spezifizieren und flexibel einsetzen zu können. Ein Prototyp ist bisher allerdings ausschließlich für Common Lisp verfügbar (vgl. Frank et al., 2003a,b).

Eric Monfroy widmet sich in seiner Dissertation und in seiner Habilitation ebenfalls dem Themenbereich kooperierender Constraint-Solver (vgl. Monfroy, 2002,1996). Er entwickelt eine Sprache namens BALI zur Steuerung von Kooperationen. BALI erlaubt es, die Kooperation unterschiedlicher Constraint-Solver auf hoher Ebene durch eine eigene Sprache zu beschreiben, und auf diese Weise effizient neue Prototypen von kooperierenden Solvern zu erstellen (vgl. Monfroy, 2000,1998). Neben unterschiedlichen Kooperationsprimitiven, welche die sequentielle, die unabhängig parallele und die nebenläufige Ausführung von Constraint-Lösungsmechanismen erlauben, bietet BALI mehrere Lösungsstrategien an. Darunter befindet auch sich eine inkrementelle Variante (vgl. Monfroy, 2000, S. 215 u. S. 224). Die Implementierung der Kooperationssprache BALI wurde innerhalb des CLP-Systems ECL$^i$PS$^e$4.71 realisiert, welches dementsprechend als ,,Host-Sprache`` fungiert (vgl. Monfroy, 1996, S. 163).

Ein neuerer Ansatz besteht in der Nutzung von speziellen Koordinierungssprachen zur Steuerung der Kooperation von Constraint-Solvern. Eine Reimplementierung von BALI wurde innerhalb der Koordinierungssprache Manifold4.72 umgesetzt (vgl. Arbab und Monfroy, 1998a,b). Ein weiterer Prototyp, der ebenfalls auf Manifold aufsetzt, ist DICE (DIstributed Constraint Environment), in dem allerdings, im Gegensatz zu BALI und dem System von Hofstedt (2000), nur sehr begrenzte Möglichkeiten hinsichtlich einer flexiblen Kooperation vorhanden sind (Zoeteweij, 2003,2002). Koordinierungssprachen unterstützen die Interaktionen und das kooperative Zusammenwirken mehrerer Komponenten. Sie erlauben die saubere Trennung zwischen den eigentlichen Berechnungen eines Systems und der Koordinierung von Kooperationen (vgl. Arbab, 1998a,b). Nachteilig wirkt sich der Aufwand für die Koordinierung der Kooperation aus vgl. Zoeteweij, 2003, S. 183; Ringwelski, 2003, S. 3. Dieser zusätzliche Aufwand muss durch die gemeinsame bzw. verteilte Berechnung unterschiedlicher Constraint-Solver kompensiert werden, um trotzdem einen Effizienzgewinn zu erreichen. Derartige Systeme lassen sich folglich nur bei umfangreichen Constraint-Problemen effizient einsetzen.



Fußnoten

...4.71
http://www.icparc.ic.ac.uk/eclipse/
...4.72
http://www.cwi.nl/projects/manifold/manifold.html

next up previous contents index
Nächste Seite: 4.6 Fazit Aufwärts: 4.5.4 Kooperative Ansätze Vorherige Seite: 4.5.4.1 Ad-hoc-Kooperationen   Inhalt   Index