Multiagentensysteme: Modelle, Programmierung, Plattformen

Verteiltes Verhalten und Gruppen

Gruppenentscheidung und Verhandlung

• In Multiagentensystemen gibt es in der Regel Organisationsstrukturen

• In diesen Strukturen sollen gemeinsame Ziele entweder vorgegeben und umgesetzt oder verhandelt werden.

Gruppenentscheidung und Verhandlung

• Dabei können Gruppenentscheidungen und Verhandlungen auf Basis von Nützlichkeitsfunktionen geführt werden

• Es sei eine Gruppe von Agenten (Prozessen) G={ag₁,ag₂,..,ag_m }

• Es gibt nun verschiedene Stufen der Verhandlung:

  • Wahl eines Gruppenführers (Leader) oder Mediators
  • Abgabe von Stimmen / Absichten
  • Bestimmung eines gemeinsamen Ergebnisses mittels Konsensalgorithmus bzw.
  • Wahl: Über Pluralität, z.B. mit einer Mehrheitsentscheidung
  • Benachrichtigung der Gruppenteilnehmer über Ergebnis

• 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 und Abstimmung

• 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:

  • Sie wollen ihren eigenen Nutzen maximieren, sehen sich aber auch der Gefahr eines Zusammenbruchs der Verhandlungen oder des Ablaufs einer Frist für die Vereinbarung gegenüber.
  • Daher muss jeder Agent sorgfältig verhandeln und jeden Nutzen abwägen, den er aus einem Versuch gegen einen möglicherweise besseren Abschluss oder das Risiko eines Ausfalls bei den Verhandlungen zieht.

Verhandlung und Abstimmung

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.,

  • Monotone Konzession
  • Monotone Konzession mit zusätzlicher Risikobewertung
  • Schrittweise Verhandlung

• 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.

• mit u_i(δ): Nützlichkeitsfunktion eines Deals δ des i-ten Agenten

Verteilter Konsens

• Ein verteilter Konsensalgorithmus hat das Ziel in einer Gruppe von Prozessen oder Agenten eine gemeinsame Entscheidung zu treffen

• Zentrale Eigenschaften:

  • Zustimmung/Übereinstimmung
  • Terminierung; Lebendigkeit und Deadlockfreiheit
  • Gültigkeit; Robustheit gegenüber Störungen wie fehlerhaften Nachrichten oder Ausfälle von Gruppenteilnehmern

• Beim Konsens kann ein Master-Slave Konzept oder ein Gruppenkonzept mit Leader/Commander und Workern verwendet werden.

  • Beim Master-Slave Konzept kommunizieren nur Slaves mit dem Master
  • Bei Gruppenkonzept (i.A. mit einem Leader) kommunizieren auch alle Gruppenteilnehmer untereinander

• Durch Störung (Fehler oder Absicht) kann es zu fehlerhaften bis hin zu fehlgeschlagenen Konsens kommen.

Verteilter Konsens

• Bedingungen für Interaktive Konsistenz:
  • IC1: Jeder Worker empfängt die gleiche Anweisung vom Leader!
  • IC2: Wenn der Leader fehlerfrei arbeitet, dann empfängt jeder fehlerfreie Worker die Anweisung die der Leader sendete!

Byzantinisches Generalproblem

• Beispiel: In einer Gruppe aus drei Prozessen/Agenten ist einer fehlerhaft bzw. versendet fehlerhafte Nachrichten (durch Störung oder Absicht) mit Anweisungen 0/1 (schließlich ein Konsensergebnis) [E]

Verteilter Konsens

• 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

  • Bedingung IC1 ist erfüllt. Um Bedingung IC2 zu erfüllen wird Worker 1 die direkte Anweisung 1 von Prozess 0 (Leader) auswählen → Konsens wurde gefunden

• Fall (b): Prozess 0 (Leader) versendet an Prozess 1 richtige Nachricht mit Anweisung 1 und falsche Nachricht mit Anweisung 0 an Prozess 1

  • Würde Prozess 1 wieder zur Erfüllung von IC2 eine Entscheidung treffen (Anweisung 1 auswählen), dann wäre IC1 verletzt. Wie auch immer Prozess 1 entscheidet ist entweder IC1 oder IC2 verletzt → Unentscheidbarkeit → Kein Konsens möglich

Verteilter Konsens

Das nicht-signierte Nachrichtenmodell erfüllt die Bedingungen:

1. Nachrichten werden während der Übertragung nicht verändert (aber keine harte Bedingung).
2. Nachrichten können verloren gehen, aber die Abwesenheit von Nachrichten kann erkannt werden.
3. Wenn eine Nachricht empfangen wird (oder ihre Abwesenheit erkannt wird), kennt der Empfänger die Identität des Absenders (oder des vermeintlichen Absenders bei Verlust).

• Algorithmen zur Lösung des Konsensproblems müssen m fehlerhafte Prozesse annehmen (bzw. fehlerhafte Nachrichten)

Der OM(m) Algorithmus

• Ein Algorithmus der einen Konsens erreicht bei Erfüllung der Bedingungen IC1 und IC2 mit bis zu m fehlerhaften Prozesse bei insgesamt n ≥ 3m+1 Prozessen mit nicht signierten (“mündlichen”) Nachrichten.
  1. Leader i sendet einen Wert v ∈ {0, 1} an jeden Worker j ≠ i.
  2. Jeder Worker j akzeptiert den Wert von i als Befehl vom Leader i.

Verteilter Konsens

Verteilter Konsens