PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-07-15 sbosse@uni-bremen.de |
In Multiagentensystemen gibt es in der Regel Organisationsstrukturen
In diesen Strukturen sollen gemeinsame Ziele entweder vorgegeben und umgesetzt oder verhandelt werden.
Dabei können Gruppenentscheidungen und Verhandlungen auf Basis von Nützlichkeitsfunktionen geführt werden
Es sei eine Gruppe von Agenten (Prozessen) G={ag1,ag2,..,agm }
Es gibt nun verschiedene Stufen der Verhandlung:
Nachteil des Mehrheitsentscheids: Das Volk ist dumm! D.h. es könnte eine besseres Ergebnis für ein MAS erzielt werden, wenn Fraktionen in den Stimmabgaben berücksichtigt werden würden (differenziertes und gewichtetes Ergebnis) …
Verhandlung in Gruppen und Abstimmung über ein gemeinsames Ergebnis (Konsens) ist ein weiteres wichtiges Beispiel für verteiltes Gruppenverhalten → Kommunikation!
Ein Verhandlungsproblem ist ein Problem, bei dem mehrere Agenten versuchen, zu einer Vereinbarung oder einem Deal zu kommen.
Es wird angenommen, dass jeder Agent gegenüber allen möglichen Deals eine Präferenz hat.
Die Agenten senden sich Nachrichten in der Hoffnung, einen Deal zu finden, auf den sich alle Agenten einigen können.
Diese Agenten stehen vor dem Problem:
Automatisierte Aushandlung kann in Multiagentensystemen sehr nützlich sein, da sie eine verteilte Methode zur Aggregation von verteiltem Wissen bietet.
Verschiedene Protokolle existieren, z.B.,
Häufig in der Form (Monotone Konzession, Vidal,2010)
0. δi <- arg maxδ ui(δ)
1. Propse δi
2. Receive δj proposal
3. if ui(δj) > ui(δi)
4. then Accept δj
5. else δi <- δi' such that uj(δi') >= e+uj(δi)
6. loop 2.
Ein verteilter Konsensalgorithmus hat das Ziel in einer Gruppe von Prozessen oder Agenten eine gemeinsame Entscheidung zu treffen
Zentrale Eigenschaften:
Beim Konsens kann ein Master-Slave Konzept oder ein Gruppenkonzept mit Leader/Commander und Workern verwendet werden.
Durch Störung (Fehler oder Absicht) kann es zu fehlerhaften bis hin zu fehlgeschlagenen Konsens kommen.
Jeder Worker der Nachrichten empfängt ordnet diese nach direkten und indirekten (von Nachbarn)
Fall (a): Prozess 2 versendet fehlerhafte Nachricht mit Anweisung 0, Prozess 1 empfängt eine direkte Nachricht mit Anweisung 1 und eine indirekte mit (falschen) Inhalt Anweisung 0
Fall (b): Prozess 0 (Leader) versendet an Prozess 1 richtige Nachricht mit Anweisung 1 und falsche Nachricht mit Anweisung 0 an Prozess 1
Das nicht-signierte Nachrichtenmodell erfüllt die Bedingungen:
Definition 1.
Algorithmus OM(m)
Leader i sendet einen Wert v ∈ {0, 1} an jeden Worker j ≠ i.
Wenn m > 0, dann beginnt jeder Worker j, der einen Wert vom Leader erhält, eine neue Phase, indem er ihn mit OM(m-1) an die verbleibenden Worker sendet.
Jeder Worker wählt die Mehrheit der (n-1) Werte, die er erhält, als Anweisung vom Leader i.