2.4 Variablenbasiertes DPS

Bei den variablenbasierten DPS Strategien ist das Problem über die Variablen verteilt. D.h. jeder Agent bekommt eine oder mehrere Variablen (eine Variable kann nur von einem Agenten kontrolliert werden) und versucht für diese eine Lösung zu finden. Die Lösung des gesamten Problems wird durch die Kommunikation zwischen den Agenten erreicht. Nachdem ein Agent eine Lösung für sein lokales Problem gefunden hat, versucht er sich mit benachbarten Agenten (also solchen mit denen Constraints bestehen) so zu koordinieren, daß alle Constraints erfüllt werden. Tritt der Fall ein, daß alle Variablen belegt und alle Constraints erfüllt sind, so ist das Problem gelöst. Es sind sowohl zentralisierte, als auch dezentralisierte Kontrollstrukturen möglich.

Die Schwierigkeiten bei diesem Ansatz bestehen darin, daß die Agenten sich in der Regel asynchron verhalten. Es müssen Synchronizationsmethoden eingesetzt werden, damit die Agenten nicht mit ungültigen oder veralteten Werten anderer Agenten operieren. Zum anderen erfordert das variablenbasierte DPS einen großen Mehraufwand für die Kommunikation, da es keinen globalen Speicher gibt, und die Kommunikation über den direkten Nachrichtenaustausch abgewickelt wird. Um diesen Overhead zu verkleinern, werden oft mehrere Variablen von einem Agenten verwaltet, so daß möglichst viele Constraints lokal geprüft werden können. Es ist klar, daß bei diesem Ansatz der Einsatz von globalen Heuristiken enorm schwierig ist (kein globales Wissen).

Das variablenbasierte DPS ist in der Regel die am meisten geeignete der drei vorgestellten Methoden, um geographisch verteilte DCSPs zu lösen.

3. Algorithmen zum Lösen von DCSPs

Nachdem wir die verschiedenen Strategien zum verteilten Problemlösen kennengelernt haben, wollen wir nun die typischen Vertreter für jeden Ansatz präsentieren. Bei allen Algorithmen, die wir vorstellen werden, handelt es um Algorithmen für die sogenannten Binary Constraint Satisfaction Problems. Der Unterschied zu einem "normalen" CSP besteht darin, daß nur binäre Constraints zugelassen sind, d.h. Constraints die jeweils nur zwei Variablen adressieren. Die Algorithmen verfolgen die sogenannte success first Strategy, d.h. es wird versucht möglich schnell eine Lösung zu finden und entsprechend den vielversprechendsten Pfaden zu folgen; im Gegensatz zu der fail first Strategy, bei der zuerst versucht wird alle ungültigen Belegungen zu finden, um anschließend alle möglichen Lösungen zu finden.

Wir haben für jede der drei Grundstrategien Vertreter ausgesucht, wobei unser Hauptinteresse den neueren variablenbasierten Algorithmen Asynchronous Backtracking und Weak-Commitment gilt. Die Vertreter der domain- und funktionsbasierten Algorithmen Parallel Search und Parallel Check Forwards werden vollständigkeitshalber kurz skizziert. Die beiden letzteren werden im nachfolgen Text behandelt, den variablenbasierten Algorithmen ist der nächste Abschnitt gewidmet.