1.Einleitung

Eine Vielzahl der Probleme in der modernen KI und anderen Bereichen der Informatik können als Constraint-Satisfaction-Problems (CSPs) betrachtet werden. Dazu gehören Graphenprobleme, Layout Management, Planung genetischer Experimente und viele andere Probleme. Daher gewinnen die Techniken des constraintbasierten Problemlösens immer mehr an Bedeutung. Ein CSP wird über seine Komponente definiert: Variablen, Werte und Constraints. Das Lösen des CSP besteht darin, entsprechende Belegungen für die Variablen zu finden, so daß alle Constraints erfüllt sind. Es wurde eine Vielzahl von Algorithmen zum Lösen der CSPs entwickelt, wie Backtracking, Backjumping, Backmarking usw. .

Heutzutage gewinnt das "Distributed Computing" immer mehr an Bedeutung. In der Tat ist es logisch, Probleme die verteilt vorliegen, auch verteilt zu lösen. Es gibt eine Vielzahl an Technologien, die in diesem Zusammenhang entwickelt wurden, z. B. die Middleware (DCE, RMI, CORBA) oder die mobilen Agenten. Natürlich können auch die constraintbasierten Techniken zum Problemlösen verteilter Probleme eingesetzt werden. Man spricht dabei vom "Distributed Problem Solving" (DPS). In diesem Dokument werden die Autoren versuchen, einen Überblick über die Distributed-Constraint-Satisfaction-Problems (DCSPs) zu geben. Wir werden über die Eigenschaften und Besonderheiten der DCSPs sprechen, sowie die verschiedenen Lösungsansätze diskutieren. Wir werden außerdem einige Algorithmen vorstellen, die speziell für die Lösung der DCSPs geeignet sind. Dabei werden wir uns insbesondere auf die neueren Algorithmen "Asynchronous Backtracking" und "Weak-Commitment" konzentrieren. Abschließend werden wir die vorgestellten Algorithmen vergleichen.

2.Grundstrategien

Ein Distributed-Constraint-Satisfaction-Problem ist definiert als ein Constraint-Satisfaction-Problem an dessen Lösung mehrere Agenten (Prozesse) arbeiten. Es gibt zwei Gründe warum ein CSP verteilt sein kann: erstens das CSP selbst ist logisch oder geographisch verteilt, und zweitens verteilte bzw. parallele Verarbeitung bringt erhebliche Vorteile beim Problemlösen. Es gibt drei wichtig Grundstrategien zum Lösen von DCSPs - Variablen-, Domain- und Werte-basiertes DPS. Der Einsatz einer bestimmten Strategie ist davon abhängig, welche Eigenschaften das zu lösende Problem besitzt. Im folgenden werden wir auf diese Eigenschaften eingehen, bevor wir dann zu den Strategien selbst kommen.

Zur Visualisierung der Strategien verwenden wir das n - Damen Problem. Dabei geht es darum, auf einem n*n großen Schachbrett n Damen so zu plazieren, daß keine der Damen eine andere bedroht. Wir benutzen den Sonderfall n=3, wobei zu bemerken ist, daß keine Lösung für diesen Fall existiert.

Im wesentlichen lassen sich bei den Distributed-Constraint-Satisfaction-Problems drei Eigenschaften unterscheiden [3]:

• dezentralisierte oder zentralisierte Kontrollstruktur - Ist eine globale Kontrollstruktur vorhanden, so existiert das globale Wissen über den Fortschritt des Problemlösens. D. h. daß eine globale Struktur (z.B. ein übergeordneter Agent) existiert, der alle anderen Agenten untergeordnet sind und die den Überblick über das gesamte System hat. Auf dieser Ebene fällt es leichter, Konflikte zu erkennen und ggf. zu lösen. Existiert dagegen keine globale Kontrollstruktur, so ist ein Algorithmus notwendig, der die Konflikte auflöst, ohne über den Zustand aller Agenten informiert zu sein. Es muß also eine Verhandlung stattfinden, mit deren Hilfe die betroffenen Agenten ihre Probleme unter- einander durch gezielte Kommunikation und auf Basis des lokalen Wissens lösen.

• gemeinsamer oder getrennter Suchraum - Bei vielen DCSPs ist es möglich, den Suchraum so zwischen den einzelnen Agenten aufzuteilen, daß jeder Agent einen eigenen Untersuchraum bekommt. Die Menge dieser Untersuchräume ist dann disjunkt, so daß jeder Agent das DCSP in seinem Untersuchraum zu lösen versucht, ohne auf die Mithilfe anderer Agenten angewiesen zu sein. Der Aufwand für die Kommunikation zwischen den einzelnen Agenten ist in diesem Fall sehr gering. Ist der Suchraum jedoch nicht in disjunkte Untersuchräume aufteilbar, so ist ein großer Aufwand für die Kommunikation und die Koordinierung einzelner Agenten einzuplanen.

• Kommunikationsart - message-passing oder shared memory - Es gibt grundsätzlich zwei mögliche Arten der Kommunikation: message-passing - also direkter Austausch der Nachrichten zwischen zwei Agenten, und shared memory, auch Blackboard genannt, eine Methode bei der jeder Agent an einem virtuellen schwarzen Brett seine Ergebnisse notiert, sowie die Ergebnisse anderer Agenten abliest um diese in seine Arbeit miteinzubringen. Die Wahl der Kommunikationsart ist u.a. davon abhängig, ob der Suchraum getrennt oder gemeinsam ist und welche Kontrollstrukturen verwendet werden. Bei einigen Problem ist die Anwendung einer Mischung aus beiden Kommunikationsarten möglich.