4.3 Asynchronous Weak Commitment Search

Der Asynchronous Weak Commitment Search Algorithmus vereinigt nun das Verhalten des Asynchronous Backtracking Algorithmus mit den beiden characteristischen Punkten des Weak Commitment Search Algorithmus. Der erste Punkt ist relativ leicht zu integrieren. Wurde bisher beim Asynchronous Backtracking bei der Wahl einer Belegung lediglich auf Konsistenz bezüglich des agent_view, und damit gegenüber den übergeordneten Agenten, geachtet, werden die Kandidaten zusätzlich auf ihre Verträglichkeit gegenüber den untergeordneten Agenten überprüft, und derjenige Wert gewählt, der die wenigsten Konflikte verursacht (min-conflict Heuristik). Im Gegensatz dazu ist es weitaus schwieriger, den zweiten Aspekt zu berücksichtigen. Durch das parallele und asynchrone Handeln der Agenten, hat kein Agent exakte Informationen über die partielle Lösung. Im folgenden soll gezeigt werden, wie eine schwache Bindung an eine partielle Lösung durch dynamische Änderung der Hierarchie erreicht werden kann. Dazu wird eine sogenannte Rangfolge eingeführt, die folgenden Regeln gehorcht:

• für jeden Agenten/Variable wird eine nicht-negative Ganzzahl definiert, die die Rangfolge unter den Agenten repräsentiert. Diese Zahl wird Rang genannt

• die Ordnung über den Agenten ist so definiert, daß ein höherer Wert auch einen höheren Rang bedeutet.

• Haben zwei Agenten den gleichen Rang, gilt eine Folge anhand der lexikographischen Ordnung der beiden Agentenbezeichner

• Jeder Agent erhält initial den Rang Null

• Wenn für den Bezeichner/Variable x_i keine konsistente Lösung existiert, ändert sich der Rang zu k+1, wobei k der höchste Rang unter den benachbarten Agenten ist.

Wie bei dem Asynchronous Backtracking Verfahren werden auch hier alle Variablen mit beliebigen Werten aus den jeweiligen Basismengen initialisiert. Der Unterschied ist, daß mit jeder ok? Nachricht auch der Rang des jeweiligen Agenten übertragen wird, und zwar an alle, zu denen eine Kante existiert, den Nachbarn. Anhand der übermittelten Ränge kann jeder Agent seine Rangposition ermitteln und übernimmt die Belegungen der übergeordneten in seinen agent_view. Die Wahl einer konsistenten Belegung wird weiterhin bezüglich des agent_view getroffen und zusätzlich nach der min-conflict Heuristik bezüglich der untergeordneten Agenten. Falls kein Wert aus der Domain eine konsistente Lösung realisiert, wird der nogood errechnet, gespeichert und per nogood Nachricht an alle Nachbarn verschickt. Danach wird eine dynamische Rangänderung wie oben beschrieben vollzogen, ein Putsch, so daß dieser Agent zukünftig anderen Agenten seinen Vorschlag diktieren kann. Eine Ausnahme gilt, wenn dieser nogood bereits vorkam. In diesem Fall geschieht keine Rangänderung, sondern der Agent wartet ab, was zukünftig passieren wird.

Wie Yokoo in seinem Papier zeigt, ist der Algorithmus vollständig. Da sich der Rang eines Agenten nur ändert, wenn ein neues nogood gefunden wurde und die Anzahl der nogoods endlich ist, ist bewiesen, daß nach einer gewissen Zeit die Ränge stabil werden. Deshalb muss nur gezeigt werden, daß folgende Fälle nicht eintreten können:

1. Es existieren Agenten, die einige Constraints nicht erfüllen, und alle Agenten warten auf Nachrichten.

2. Nachrichten werden wiederholt gesendet und empfangen, und der Algorithmus wird keinen stabilen Zustand erreichen.

Sollte die Situation i) eintreten, existieren wenigstens zwei Agenten zwischen denen ein Constraint nicht erfüllt wird. Angenommen diese beiden Agenten haben die Ränge j und k mit j<k, und alle Agenten mit einem Rang größer k haben konsistente Belegungen, dann kann das nur bedeuten, daß der Agent mit dem Rang k ein nogood gesendet hat. Da dies aber ein Widerspruch zu der Annahme ist, daß alle übergeordneten Agenten konsistente Belegungen haben, kann der Fall i) nie eintreten.

Die Frage ii) lässt sich ebenso schnell klären. Es wurde bereits gezeigt, daß nach einer gewissen Zeit der Rang jedes Agenten stabil werden muss, also die Rechnung seine Dynamik verliert und identisch zum Asynchronous Backtracking Algorithmus wird. Da dieser wiederum terminiert, muss also auch der Asynchronous Weak Commitment Search Algorithmus einen stabilen Zustand erreichen und terminieren.

Da weder Situation i) noch ii) eintreten können, kann garantiert werden, daß der Algorithmus immer eine Lösung finden wird, oder den Fakt herausfindet, daß keine Lösung existiert. Nur baut die Aussage darauf auf, daß die Anzahl der nogoods endlich ist, und sich jeder Agent eine vollständige Liste aller aufgetretenen nogood anlegt. Da deren Anzahl aber exponentiell mit der Anzahl der Variablen ansteigt, schlägt Yokoo vor, nur N der zuletzt aufgetretenen nogoods (z.B. N=10) zu vermerken. Damit geht allerdings die Vollständigkeit verloren.

Beispiel 2: Vier-Damen-Problem, gelöst mit dem Asynchronous Weak Commitment Search Algor., die Zahlen in Klammern repräsentieren die Rangnummer, die Zahlen in den Kreisen, den Rang unter Beachtung der lexikographischen Ordnung.