Computation Intelligence Seminar A
Helmut GRABNER
Multiagent Systems
Einführung: Kommunikation
Multiagent Systems: A Survey from a Machine Learning Perspective
[Peter Stone, Manuela Veloso 2000]
Übersicht


Kurze Wiederholung
Homogeneous Communication MA


Heterogeneous Communication MA


Beispiel: Reaktives Multiagentensystem
Interaktionen
Multiagent Q-Learning
Wiederholung - Einteilung
Homogeneous Communicating
Multiagent Systems
Homogeneous Communicating Multiagent Systems
Allgemein


Agenten können
direkt (!) miteinander
kommunizieren
gleicher Aufbau, nur
Input variiert
Homogeneous Communicating Multiagent Systems
Beispiel: Pursuit domain

[Stephen, Merx
1990]

Kommunikation um
sicherzustellen, dass
jeder an eine andere
„Capture-Pos.“ fährt.
(vgl. Homogeneous
no communication.)
Homogeneous Communicating Multiagent Systems
Aufgaben/Fragen

Aufgaben

Verteiltes erfassen von Informationen


Trafficopter
Fragen

Was, wann, wie und mit wem soll
kommuniziert werden?

Sensorinformationen/Ziele
Homogeneous Communicating Multiagent Systems
Reaktives Multiagentensystem
Beispiel
Communication in Reactive Multiagent Robotic Systems
[Balch, Arkin 1994]
Beispiel: Reaktives Multiagentensystem
Inhalt

Kommunikationsmethoden




Aufgaben



Futtersuche (Forage – Task)
Abgrasen (Graze – Task)
Umgebung


no communication
State communication
Goal communication
2D, Roboter, Hindernisse, Arttraktoren
Zusammenfassung
Beispiel: Reaktives Multiagentensystem - Kommunikationsmethode
No communication



Agent (Roboter) als Automat
keine direkte Kommunikation, Jeder Agent
ist auf seine Wahrnehmung der Welt
beschränkt
Unterscheidungen: andere Agenten
(Roboter), Arttraktoren, Hindernisse
Beispiel: Reaktives Multiagentensystem - Kommunikationsmethode
State Communication


Kein direktes Senden, andere können
den Zustand aber abfragen
Agenten erkennen den Status eines
anderen


Agent hat „Arbeit“ gefunden
Agent fährt zu demjenigen
Beispiel: Reaktives Multiagentensystem - Kommunikationsmethode
Goal Communication

Explizite Kommunikation




Position des Arttraktors
Sender – Übertragung – Empfänger
Biologie: Honigbiene – Tanz
Roboter fährt direkt zum Arttraktor

eventuell kürzerer Weg
Beispiel: Reaktives Multiagentensystem - Aufgabe
Forage-Task



Roboter sucht die Umgebung
nach „Futter“ (Arttraktoren)
ab und bringt diese „nach
Hause“
Hindernisse in der
Umgebung
Die Masse eines Arttraktors
bestimmt, wie schnell er
transportiert werden kann.
Mehrere Roboter gemeinsam
können dies beschleunigen.
Beispiel: Reaktives Multiagentensystem – Aufgabe Forage-Task
Kommunikationsmethoden

No communication


Automat
State und Goal
communication

Realisiert mit 1 Bit:
„Suchen“ oder
„hinbewegen“ /
„nach Hause“
Beispiel: Reaktives Multiagentensystem – Aufgabe Forage-Task
Vergleiche
5145 Schritte
4470 Schritte
3495 Schritte
Beispiel: Reaktives Multiagentensystem – Aufgabe Forage-Task
Vergleichsmaß


Roboter (1..5) x
Arttraktoren (1..7)
Steps (Zeitschritte)
Vergleich (Division)
der beiden
Messungen


(Speedup Vergleich)
Mittelwert
Beispiel: Reaktives Multiagentensystem – Aufgabe Forage-Task
Auswertung
Mittelwert
Verbesserung
beste
schlechteste
16 %
66 %
-5 %
19 %
59 %
-7 %
3%
34 %
-19 %
Forage - Task
State vs. no
Goal vs. no
Goal vs. State
Beispiel: Reaktives Multiagentensystem – Aufgabe
Graze-Task


„Abgrasen“ der
gesamten Umgebung
Hindernisse in der
Umgebung
Beispiel: Reaktives Multiagentensystem – Aufgabe Graze-Task
Kommunikationsmethoden

No communication


Automat
State und Goal
communication

Realisiert mit 1 Bit:
„Suchen“ oder
„hinbewegen“ /
„weiden“
Beispiel: Reaktives Multiagentensystem – Aufgabe Graze-Task
Auswertung
Mittelwert
Verbesserung
beste
schlechteste
1%
19 %
0%
1%
19 %
0%
0%
0%
0%
Graze - Task
State vs. no
Goal vs. no
Goal vs. State

Kommunikation bringt fasst nichts

Wenn der Roboter „grast“ hinterlässt er unvermeidlich
eine „Spur“ -> Diese Änderung der Umgebung kann als
indirekte Kommunikation verstanden werden!
Beispiel: Reaktives Multiagentensystem
Zusammenfassung



Kommunikation bringt viel, bei
Anwendungen mit wenig impliziter
Kommunikation (Forage)
Kommunikation ist nicht notwendig, bei
Anwendungen wo (viel) implizite
Information vorhanden ist.
Komplexere Kommunikationsstrategien
bringen relativ kleinen Gewinn
Heterogeneous
Communicating Multiagent
Systems
Heterogeneous Communicating Multiagent Systems
Allgemein



Verschieden auf jegliche
Art
sehr komplex und
leistungsstark
(allgemeinster Fall)
Wohlwollend vs.
Wettbewerb
Heterogeneous Communicating Multiagent Systems
Beispiel: Pursuit domain

Extremfall:
Ein „intelligenter“ Agent steuert
mehrere ausführende (single
agent)
Heterogeneous Communicating Multiagent Systems
Aufgaben/Fragen


Untereinander verstehen
Wohlwollend vs. Wettbewerb


Verhandlungen



Trainer
Temperaturkontrolle
Verpflichtungen
Ressource Management
Interaktion
Interaktion
Wozu?

Möglichkeit zur Abstimmung von
Aktionen

Alternative: vollständige wechselseitige
Modellierung


bei homogenen: Modell der internen Zustände
bei heterogenen: Komplizierter - Ziel, Aktionen,
Wissen der anderen Agenten sind
möglicherweise nicht bekannt und müssen
durch Beobachtung modelliert werden.
Interaktion
Ziele

Maximieren des Gesamtergebnisses








Sicherstellung des Bestehens und der Leistungsfähigkeit
des Gesamtsystems
Arbeitsteilung (Bestimmung gemeinsamer
Ziele/Aufgaben)
Vermeidung von Redundanzen
Abhängigkeiten der Aktionen der einzelnen Agenten
(Reihenfolge)
Behandlung von Interferenzen und Konflikten
(„widersprüchliche“ Ziele)
Vermeidung unnötiger Konflikte
Kombination unterschiedlichen Wissens
Erfüllungen von Nebenbedingungen (z.B. begrenzte
Ressourcen)
Interaktion
Wie?

Speech acts


Kommunizieren mittels Aktionen
Kommunikation „extra - Environment“
?
Interaktion
Begriffe
Interaktion: Wechselbeziehung, bes. die
Kommunikation zw. Individuen innerhalb einer
Gruppe.
Kommunikation: Prozess der Mitteilung; der
wechselseitige Austausch von Gedanken,
Meinungen, Wissen, Erfahrungen und Gefühlen
sowie die Übertragung von Nachrichten und
Informationen
Koordination: Abstimmen verschiedener Vorgänge
Kooperation: Zusammenarbeit
Konkurrenz: Wettbewerb
Interaktion
Agenteninteraktion

Kommunikation


Koordination


(coordination)
jene Kommunikation welche zur aufgabenbezogenen
Tätigkeit notwendig ist
Kooperation


(communication)
Verständigung mehrerer Agenten untereinander
(cooperation)
jene Kommunikation welche zur Koordination und
Vereinbarung gemeinsamer Ziele notwenig ist
Verhandlung

(negotiation)
jene Kommunikation für die Aushandlung der
Kompromisse
Interaktion
Kommunikationstypen


keine Kommunikation
indirekte Kommunikation


einfache Kommunikation


Austausch von Information über einen gemeinsamen
Informationsraum (Umwelt)
individueller Austausch von einfachen Nachrichten bzw.
Ereignissen
Kommunikation basierend auf Konversation


Austausch von strukturierten Nachrichten
Konversationstheorie: Äußerungen werden mit Handlung
gleichgesetzt (Sprechen ist eine Art Aktion) und wie sie
die Zukunft verändern (Ich verurteile Sie zu...)
Interaktion
Agentenkommunikation

Voraussetzungen für erfolgreiche
Kommunikation (heterogene Agenten)

Gemeinsame Ontologie




Gemeinsame Begriffsmenge (Vokabular)
Gemeinsame Semantik für diese Begriffe
Gemeinsame Kommunikationssprache in Syntax
und Semantik
Technische Voraussetzungen
(Übertragungskanäle,..)
Interaktion
Knowledge Interchange Format (KIF)



Zwischensprache zur Übersetzung einer
Wissensbasis von einer Repräsentation zu
einer anderen.
Muss mächtig genug sein, um alle in der
Sprache formierten Wissensinhalte zu
transportieren
Deklarative Semantik


Bedeutung von Ausdrücken mittels Interpretation über
Modelle (logisch verwertbar)
(Common Lisp ähnlich)
Interaktion
Knowledge Query and Manipulation
Language (KQML)

spezifiziert ein Nachrichtenformat zum
Austausch von Informationen


Nachricht wird in eine Struktur gebracht, die von jedem
Agenten verstanden wird. Die Nachricht selbst jedoch
muss nicht unbedingt verstanden werden.
3 Ebenen

Inhaltsebene


Nachrichtenebene


aktueller Nachrichteninhalt (z.B.: in KIF)
spezifiziert den Nachrichtentyp/Nachrichtenparameter
(Fragen, Mitteilen, „tu was“, Benachrichtigen,...)
Kommunikationsebene

Sender/Empfänger
Interaktion
Simple Knowledge Transfer Protocol
(SKTP)
content
message

SKTP
communication

application
presentation
session
transport
network
data link
physical
ISO/OSI

Inhaltsebene
(content Layer)
Inhalt der Nachricht. Das in
„Wörtern“ ausgedrückte „Wissen“
Nachrichteneben
(message Layer)
Nachrichtentyp, Thema der
Nachricht
Kommunikationsebene
(communication Layer)
Daten aus der KQML Nachricht für
die Datenübertragung (Adressen)
Interaktion
Beispiel: KQML
Nachrichtenebene
Kommunikationsebene
Inhaltseben
(ask-one
: sender helmut
: receiver boerse_server
: replay-with euro_kurs
: content (WERT EURO_DOLLAR ?wert)
: language Prolog
Nachrichtentypen:
: ontology Boerse)
Anfragen: ask-one, ask-all,...
(tell
: sender boerse_server
: receiver helmut
: in-replay-to euro_kurs
: content (WERT EURO_DOLLAR 1.0029)
: language Prolog
: ontology Boerse)
Antworten: replay, sorry,...
Informationsverm.: tell,...
Funktionsangebot: advertiese,...
Zustand: ready, standby,...
Interaktion
Koordination von Agenten


Welcher Agent soll was machen –
Verteilte Künstliche Intelligenz
Kooperation



Notwendig? Selbstsüchtig
Delegieren von Aufgaben (hierarchische Strukturen)
Konkurrenz

Marktmechanismus


Gegenseitige Kooperation (Abmachungen)
Manager - mehrere Anbieter


keine zentrale Kontrolle
jeder Partner evaluiert Information aus seinem Standpunkt
Interaktion
Koordinationsvarianten

direkter Nachrichtenaustausch






message parsing
Klassisch: Verbindungsarten (Client/Server), Protokolle,
Synchronisation,...
Blackboard

(point to point)
(broadcast)
Verwendung von gemeinsamen Datenstrukturen (shared
memory)
Agent entscheidet wann und was er bekannt gibt und ob
er wann und welche Informationen sucht und diese
bewertet
Synchron und Asynchron
Meeting
Multiagent Q-Learning
Beispiel für die Komplexität,
ohne Theorie
Multiagent Q-Learning
[Hu, Wellmann 2002]
Multiagent Q-Learning
Multiagent Q-Learning


Was soll in dem aktuellen Zustand
gemacht werden?
Join Action Values

Ein Agent muss n Q-Tables (eine für ihn und je
eine für die anderen Agenten - Modellierung)
erstellen
Multiagent Q-Learning
Singleagent vs. Multiagent
Singleagent
Q-Function
Optimal Q-value
Q(s, a)
aktueller Reward +
zukünftige Rewards
wenn die optimale
Strategie verwendet
wird
Multiagent
1
n
Q(s, a ,...a )
aktueller Reward +
zukünftige Rewards
wenn alle Agenten
die optimale
Strategie (NashGleichgewicht)
verwenden werden
Multiagent Q-Learning
Beispiel



Agent 1 und Agent
2 jeweils in die
diagonale Ecke
Gewinner: der als
erster angekommen
ist (oder beide
zugleich – Ziel)
kein Zusammenstoß
Beispiel: Multiagent Q-Learning
States,...

States: 9 x 9



Anfangszustand (0, 2)
Aktionen: 4
Q Table: 81 x 4 = 324
Beispiel: Multiagent Q-Learning
Ergebnis
im Zustand
(0, 2)
Agent 1

Agent 2
Links
Hinauf
Rechts
86, 87
83, 85
Hinauf
96, 91 95, 95
Spieltheorie

Nash Gleichgewicht


Wie kann Kooperation aus Handlungen von Egoisten
entstehen?
Bimatrix-game (Gefangenen Dilemma)
Multiagent Q-Learning
Komplexität




m = Anzahl der Zustände
n = Anzahl der Agenten
A = möglichen Aktionen
Ein Agent muss n Q – Functions lernen!
nm A
n

Reinforcement Learning Seminar F