next up previous contents index
Nächste Seite: 4.5 Verfügbare Constraint-Systeme Aufwärts: 4.4 Ansätze zur Constraint-Verarbeitung Vorherige Seite: 4.4.3 Überbestimmte Constraint-Probleme   Inhalt   Index

4.4.4 Weiterführende Konzepte

Eine gewisse Ähnlichkeit mit dem DCSP bzw. dem CompCSP weist das Structural Constraint Satisfaction Problem (SCSP) auf. Das SCSP erlaubt dynamisch die Struktur des Constraint-Netzes eines Problems zu verändern. Dies geschieht allerdings in diesem Fall auf der Basis von Regeln einer Graph-Grammatik (vgl. Nareyek, 1999b). Dadurch lässt sich z.B. die automatische Ablaufplanung für Workflows realisieren. In einem SCSP, welches entsprechend die Generierung alternativer Pläne formalisiert, ist die Suche nach der Struktur des Constraint-Netzes demnach explizit Teil der Lösungssuche des Constraint-Erfüllungsprozesses (vgl. Nareyek, 1999a).

Ein ebenfalls dynamisches Konzept, welches für offene und verteilte Umgebungen konzipiert wurde, ist das Open Constraint Satisfaction Problem (OCSP). Während der klassischen Definition eines Constraint-Problems die closed world assumption (CWA) zugrunde liegt, d.h. es sind zu Beginn der Lösungsermittlung sämtliche Komponenten eines Problems bekannt, lassen sich durch das OCSP open-world-Szenarien behandeln (vgl. Faltings und Macho-Gonzalez, 2002).4.19 Diese treten z.B. dort auf, wo offene Informationssysteme wie das Internet genutzt werden.4.20 In diesem Fall werden die benötigten Informationen aus unterschiedlichen Quellen durch Mediatoren gebündelt bzw. übersetzt. Der Lösungsvorgang für ein OCSP gestattet es, zusätzliche Informationen, die (zusätzliche) Lösungen ermöglichen, nach und nach zu integrieren. Auf diesem Wege können Teilprobleme kombiniert werden, um eine Lösung für ein bestimmtes Problem zu erhalten. Lösungsalgorithmen für OCSPs, die mit einem Brute-Force-Ansatz die Informationen aller Quellen einsammeln und anschließend ein übliches (statisches) Lösungsverfahren anwenden, können sehr aufwendig werden und sind daher nur bedingt geeignet. Ein stabileres Laufzeitverhalten wird erreicht, wenn nur benötigte Informationen eingesammelt und die erste gefundene Lösung ausgeben wird. Wird festgestellt, dass mehr Informationen zur Generierung einer Lösung notwendig sind, können diese inkrementell hinzugefügt und der Lösungsprozess erneut angestoßen werden. Eine weitere Verbesserung stellt das Vorgehen dar, ausschließlich zusätzliche Informationen für bestimmte Variablen zu sammeln, die an minimalen, unlösbaren Teilproblemen partizipieren. Eine optimierte Lösung für ein OCSP wird durch ,,gewichtete`` Constraints erreicht, indem versucht wird, diese Gewichtungen innerhalb einer Lösung zu minimieren (vgl. Faltings und Macho-Gonzalez, 2003).4.21

Ein CSP kann verteilt sein, weil (1) das CSP selbst logisch oder physikalisch verteilt ist, oder weil (2) die verteilte bzw. parallele Verarbeitung erhebliche Vorteile bzgl. der Effizienz mit sich bringt. Ein Konzept, bei dem der Aspekt der Verteiltheit im Vordergrund steht, ist das Distributed Constraint Satisfaction Problem (DisCSP). Es wurde für die Behandlung von verteilten Abhängigkeiten in Multi-Agenten-Systemen (MAS) entwickelt. Die Variablen und Constraints eines Problems sind in einem DisCSP auf eine Vielzahl automatisierter Agenten bzw. Prozesse verteilt (engl. inter-agent constraints). Um Konsistenz für diese Abhängigkeiten zu gewährleisten, werden entsprechende verteilte bzw. asynchrone Lösungsverfahren auf das als DisCSP formalisierte MAS angewendet (vgl. Yokoo und Hirayama, 2000).

Die nebenläufige Behandlung von Constraint-Problemen hat im Concurrent Constraint Programming (CCP) eine besondere Ausprägung gefunden. Das CCP ist ein Konzept für eine einfache Sprache zur effizienten und parallelen Constraint-Verarbeitung. Im Kern besteht das Konzept aus einer zentralen Kontrollinstanz zur Koordinierung, mit der eine Vielzahl Agenten bzw. Prozesse bzgl. der Problemlösung kommuniziert. Das Ziel von nebenläufiger Constraint-Verarbeitung ist es, bestehende Constraint-Probleme durch den effizienten Einsatz parallel-arbeitender Verfahren zu lösen vgl. Frühwirth und Abdennadher, 1997, S. 65 ff.; Van Hentenryck und Saraswat, 1996, S. 705 f.. Nebenläufige Constraint-Behandlung nach dem CCP-Schema unterscheidet sich damit grundsätzlich im Anwendungszweck vom DisCSP und dessen Anwendung inerhalb von MAS (vgl. Yokoo und Hirayama, 2000, S. 189).

Weiterhin existiert ein Konzept für die Zusammenführung von verteilter und dynamischer Constraint-Erfüllung, genannt Asynchronous Constraint Solving (ACS). Das Konzept für ACS ist im Rahmen einer Dissertation von Georg Ringwelski als sog. ,,Ausführungsmodell`` entwickelt worden und wird auch kurz DynDCSP genannt (vgl. Ringwelski, 2003). Neben verteilten und dynamischen Aspekten unterstützt es darüber hinaus die inkrementelle Verarbeitung von Constraints, sowohl bzgl. anwachsender Constraint-Netze, als auch bezogen auf das inkrementelle Zurücknehmen von Constraints (vgl. Ringwelski, 2001a; Ringwelski und Schlenker, 2002).4.22

Anstatt zur Problemlösung lediglich ein einziges Lösungsverfahren zu nutzen, bietet es sich aus Effizienzgründen an, je nach Art der Problemstellung unterschiedliche Verfahren einzusetzen. Ein Konzept, welches dieses Vorgehen automatisiert, und den Constraint-Solver während des Lösungsprozesses auf das jeweilige Problem anpasst, wird durch das Adaptive Constraint Satisfaction Problem (ACSP) bereitgestellt (vgl. Borrett et al., 1996a,1995,1996b). Mit dem ACSP wird es möglich, dynamisch während der Lösungssuche zwischen unterschiedlichen Lösungsalgorithmen zu wechseln, bis ein für das jeweilige Problem geeignetes Verfahren gefunden wird. Die Realisierung sieht vor, dass aus einer Menge vorgegebener Lösungsverfahren der Reihe nach jeweils eines ausgewählt wird. Zu Beginn kommt ein ,,einfaches`` Lösungsverfahren zum Einsatz, d.h. ein Verfahren, welches für einfache Problemstellungen mit durchschnittlich guter Effizienz eingesetzt werden kann. Stellt sich während der Lösungssuche heraus, dass ein Verfahren ineffizient arbeitet, wird selbiges durch ein weiteres, komplexeres Verfahren ersetzt, welches für schwieriger zu lösende bzw. härtere Problemstellungen geeignet ist. Dieses Vorgehen ermöglicht es, einfache Probleme ohne viel Overhead zu lösen, und gleichzeitig bei harten Problem die entsprechenden effizienten Verfahren nutzen zu können.

Nachteilig wirkt sich beim ACSP aus, dass der beschriebene Anpassungsprozess, bis ein für das jeweilige Problem geeigneter Algorithmus gefunden wird, u.U. relativ lange dauern kann. Zudem ist bei einem Wechsel der Suchstrategie nicht gewährleistet, dass die bisherigen Suchergebnisse übernommen werden können. Lediglich geringfügige Änderungen an der Strategie (z.B. eine Heuristik betreffend) ermöglichen i.A. die Erhaltung der bisherigen Ergebnisse. Alternativ bietet es sich daher an, die Auswahl des Lösungsverfahrens bereits zu Beginn der Lösungssuche vorzunehmen. Eine Möglichkeit, auch diesen Prozess zu automatisieren, bietet der von Kwan (1997) vorgestellte Mapping-Ansatz. Basierend auf der Problemstellung (zufällig erzeugte CSPs, Graph-Färbeprobleme), dem Abstand des Problems zur Phasenübergangsregion und einiger einfacher, struktureller Eigenschaften des Constraint-Netzes werden unterschiedliche Constraint-Lösungsverfahren automatisch dem jeweiligen Problem anhand von Entscheidungsbäumen, die durch ein ,,Maschinelles Lernverfahren`` basierend auf Fuzzy-Technologie erzeugt werden, zugeordnet.

Die Zusammenführung von finiten und infiniten Domänen innerhalb eines Problems ermöglichen Gelle und Faltings (2003) durch das Mixed Constraint Satisfaction Problem (Mixed CSP). Das Konzept für Mixed CSPs kann für Problemstellungen eingesetzt werden, zu deren Behandlung es notwendig ist Constraints zu verarbeiten, die gleichzeitig Variablen mit finiten und infiniten Wertebereichen in Relation setzen (engl. mixed constraints). Derartige Constraints werden auch heterogene Constraints genannt (vgl. Benhamou, 1996). Im Gegensatz zu Benhamou (1996), der den Konsistenzbegriff derart erweitert, dass sich diskrete und kontinuierliche Domänen gleichzeitig behandeln lassen, integrieren Gelle und Faltings (2003) bzw. Gelle (1998) unterschiedliche Lösungsalgorithmen - sowohl für diskrete Wertebereiche als auch für reellwertige Intervalldomänen - innerhalb eines Suchverfahrens zum Auffinden von Lösungen für derartig ,,gemischte`` Constraint-Erfüllungsprobleme. Sie definieren verschiedene Constraint-Typen für Mixed-Constraints, die z.T. unterschiedliche Möglichkeiten zur Diskretisierung von Intervalldomänen vorsehen, oder diskrete Variablen von Mixed-Constraints bevorzugt propagieren. Dies geschieht nach Möglichkeit in der Form, dass die verbleibenden, intervallwertigen Variablen ebenfalls konsistent belegt werden können. Die Autoren weisen darauf hin, dass insbesondere im Bereich der Konfigurierung Problemstellungen auftauchen können, welche die Verarbeitung von Mixed-Constraints erforderlich machen. Gelle und Faltings (2003) zeigen dafür mehrere Anwendungsbeispiele auf und erweitern das Mixed CSP durch Aktivitäts-Constraints zum mixed CondCSP.

Nach dieser Übersicht über bestehende Konzepte zur Constraint-Verarbeitung werden nachfolgend verfügbare Constraint-Systeme untersucht und auf ihre Eignung zur Integration in den ENGCON-Konfigurator bewertet.



Fußnoten

...4.19
In Bezug auf die Konfigurierung wird dies auch innovatives Konfigurieren genannt.
...4.20
,,Offen`` in dem Sinne, dass die Informationen und deren Menge, die theoretisch unbegrenzt sein kann, im Vorfeld nicht bekannt sind. Derartige Informationssysteme werden durch Technologien wie Web Services und Semantic Web weiter an Bedeutung zunehmen.
...4.21
Eine Gewichtung wird erreicht, indem jede mögliche Kombination von Variablenbelegungen eines Constraints mit bestimmten ,,Kosten`` markiert wird.
...4.22
Das inkrementelle Zurücknehmen von Constraints wird von Ringwelski (2003) engl. constraint retraction genannt und unter dem Oberbegriff ,,Adaptivität`` geführt.

next up previous contents index
Nächste Seite: 4.5 Verfügbare Constraint-Systeme Aufwärts: 4.4 Ansätze zur Constraint-Verarbeitung Vorherige Seite: 4.4.3 Überbestimmte Constraint-Probleme   Inhalt   Index