4 Drei variablenbasierte Algorithmen

Im folgenden soll der von Makoto Yokoo entwickelte Asynchronous Weak Commitment Search Algorithmus vorgestellt werden, der eine Fusion der beiden Verfahren Asynchronous Backtracking und Weak Commitment Search darstellt [1]. Zuerst soll kurz auf die beiden letzteren Verfahren eingegangen werden.

4.1 Asynchronous Backtracking

Ausgangspunkt dieses Backtrackingverfahrens ist ein verteiltes, binäres CSP, das wir als zyklenfreies, gerichtetes Netzwerk repräsentieren, bei dem die Variablen Knoten und die Constraints Kanten zwischen den Knoten sind. Jeder der Knoten ist mit einem Agenten besetzt, der exakt eine Variable verwaltet. Damit repräsentiert ein Knoten auch einen Agenten, und wir können deshalb die gleichen Bezeichner für Agenten und Variablen wählen. Es wird angenommen, daß jede Kante gerichtet ist aber das dazugehörige Constraint-Prädikat nur von einem der beiden Agenten ausgewertet wird. Der andere Agent muss seine Belegung per Nachricht mitteilen. Um Zyklen zu verhindern, weist eine Kante von einem lexikographisch niederen zu einem lexikographisch höheren Knoten, der auswertende Agent befindet sich im lexikographisch höheren Knoten.

Jeder Agent instantiiert seine Variablen mit einem Wert aus der Domain und sendet sie über alle ausgehenden Kanten an andere Agenten. Anschließend wartet der Agent auf Nachrichten. In Beispiel 1 sieht man zwei Arten von Nachrichten, die zwischen den Agenten verschickt werden, die eine ist die ok?-Nachricht, mit der einem untergeordnetem Agenten die momentane Variablenbelegung mitgeteilt wird.

Die zweite Nachricht ist die nogood-Nachricht, mit der ein Constraint auswertender Agent einem übergeordneten Agenten mitteilt, daß der gewählte Wert ein Constraint verletzt und eine andere Belegung gewählt werden muss (Beispiel 1a). Die eintreffenden Werte der ok?-Nachrichten werden in einer Liste als Paar der Form (x_i,current_value_i) verwaltet, dem agent_view. Zu jedem übergeordneten Agenten existiert genau eines dieser Paare, das nach einer eintreffenden ok?-Nachricht aktualisiert wird. Anschließend wird die eigene Belegung auf Konsistenz bezüglich diesem neuen agent_view überprüft. Eine Belegung ist nicht konsistent, wenn sie eines der Constraints verletzt, die der Agent auswertet, oder eine Verletzung von einem untergeordneten Agenten per nogood-Nachricht mitgeteilt wird.

Wenn die eigene Variablenbelegung nicht konsistent mit dem agent_view ist, wird versucht eine stimmige Belegung zu finden, und diese Änderung via ok? Nachricht an untergeordnete Agenten weitergegeben. Sollte dies scheitern, wird die unverträgliche Teilmenge des agent_view ermittelt und als nogood an den nächst übergeordneten Agenten, zu dem eine Kante existiert, gesandt. Dieser überprüft alle Namen in der nogood-Nachricht mit denen in seiner agent_view und und erweitert seine agent_view, indem zu dem bisher unbekannten Agenten eine neue Kante, ein neues Constraint, aufgebaut wird (Beispiel 1c).

Wenn das nogood eine Teilmenge der agent_view des Empfängers ist, muss dieser selbst ein nogood erzeugen und ebenso weiterleiten, hat sich aber die Belegung einer Variablen mittlerweile, asynchron gändert, wird das nogood ignoriert.

Durch diesen Mechanismus kann zu jeder Zeit Zyklenfreiheit garantiert werden und es kann gezeigt werden, daß eine existierende Lösung gefunden wird. In diesem Fall geht das System in einen Zustand über, in dem alle Belegungen konsistent sind und keine nogood-Nachrichten verschickt werden. Um diesen Zustand zu erkennen, wird wieder ein eigenes Verfahren angewandt, wie etwa (2), auf das Yokoo selbst nicht eingeht.