Kommunikation in Multi Agenten Systemen - Informatik

Universität Paderborn
Fakultät für
Elektrotechnik, Mathematik und Informatik
Seminarausarbeitung
Kommunikation in Multi Agenten Systemen
Melanie Kirchner
vorgelegt bei
Prof. Dr. Hans Kleine Büning
1
Inhaltsverzeichnis
1. Einleitung _____________________________________________________________4
1.1 Grundlagen der Kommunikation ________________________________________ 4
1.2 Sprechakttheorie ______________________________________________________ 5
2. Indirekte Kommunikation ________________________________________________6
2.1 Blackboard __________________________________________________________ 6
2.2 Stigmergy ___________________________________________________________ 8
3. Direkte Kommunikation _________________________________________________9
3.1 Einführung in ACLs (Agent Communication Language) ____________________ 9
3.2 FIPA (Foundation for Intelligent Physical Agents) _________________________ 9
3.3 KSE (Knowledge Sharing Effort) ________________________________________ 9
3.4 Ontologien __________________________________________________________ 10
3.5 KIF (Knowledge Interchange Format) ___________________________________ 11
3.5.1 Allgemeines______________________________________________________ 11
3.5.2 Syntax __________________________________________________________ 11
3.6 KQML _____________________________________________________________ 13
3.6.1 Allgemeines______________________________________________________ 13
3.6.2 Semantik ________________________________________________________ 14
3.6.3 Syntax __________________________________________________________ 14
4. Adressaten ___________________________________________________________17
4.1 Singlecast ___________________________________________________________ 17
4.2 Multicast____________________________________________________________ 17
4.3 Broadcast ___________________________________________________________ 17
4.4 Vor – und Nachteile___________________________________________________ 18
4.5 Reichweite __________________________________________________________ 18
5. Bezug zur Projektgruppe KIMAS _________________________________________19
6. Quellenverzeichnis_____________________________________________________20
2
Abbildungsverzeichnis
Abbildung 1 Kommunikationsmodell ____________________________________________ 4
Abbildung 2 Blackboardmodell mit Kontrolleinheit _________________________________ 7
Abbildung 3 Nest der Papierwespe ______________________________________________ 8
Abbildung 4 Aufbau des KSE _________________________________________________ 10
Abbildung 5 KQML - Schichten _______________________________________________ 13
3
1. Einleitung
In dieser Arbeit geht es um die Kommunikation in Multi Agenten Systemen. Ich werde
mit einigen allgemeinen Grundlagen der Kommunikation beginnen. Danach werde ich auf
die unterschiedlichen Arten der Kommunikation, zum einen die indirekte, zum anderen
die direkte, eingehen. Bei der indirekten Kommunikation werde ich mich mit Blackboard
- Systemen und Stigmergy auseinandersetzen, bei der direkten Kommunikation genauer
auf einige Standards der Kommunikationsprotokolle eingehen und die Sprachen KIF und
KQML vorstellen. Am Ende werde ich noch auf die verschiedenen Adressaten eingehen
und als Fazit einen Bezug zur Projektgruppe KIMAS herstellen.
1.1 Grundlagen der Kommunikation
Kommunikation ist die Grundlage für Interaktion und soziale Organisation. Dadurch ist es
möglich gemeinsam an Aufgaben zu arbeiten und sich dabei zu koordinieren. Oft ist es
einfacher seine Ziele zu erreichen, wenn man auf den Wissensbestand anderer zugreifen
kann, und ihn sich nicht erst selbstständig aneignen muss. Vorraussetzung für eine
gelungene Kommunikation ist eine gemeinsame Sprache. Des weiteren sollten einige
Basisregeln eingehalten werden, wie Ehrlichkeit, Hilfsbereitschaft und die Angewohnheit,
auf gestellte Fragen auch zu antworten.
Kommunikation erfolgt über Signale. Diese Signale haben an sich keine Bedeutung. Erst
wenn jemand dieses Signal empfängt und auch ein System zur Interpretation besitzt, oder
daraufhin sein Verhalten ändert erlangt es Bedeutung. Wenn dieses Signal nur ein
Verhalten erzeugt, wird es Stimulus oder Reiz genannt. Wird es andernfalls nur in ein
kognitives System aufgenommen, welches es interpretieren kann, wird das Signal als
Bedeutungsträger bezeichnet.[1]
Laut der Kommunikationstheorie von Shannon und Weaver besteht Kommunikation aus
einem Sender, der eine Information an einen Empfänger sendet. Die Information wird mit
Hilfe einer Sprache beim Sender verschlüsselt, durch einen Kanal gesendet und vom
Empfänger wieder entschlüsselt.
Abbildung 1 Kommunikationsmodell
4
1.2 Sprechakttheorie
Es ist wichtig, kurz auf die Theorie der Sprechakte einzugehen, da sich einige der weiter
unten vorgestellten Sprachen auf diese Theorie beziehen.
Laut Ferber besteht ein Sprechakt aus 3 Komponenten[1]
• Lokutionäre Komponente
• Illokutionäre Komponente
• Perlokutionäre Komponente
Unter lokutionäre Komponente versteht man die materielle Erzeugung von Äußerungen,
wie z.B. das Schreiben von Buchstaben
Die illokutionäre Komponente bezieht sich auf die Ausführung des Sprechakts. Sie
werden durch eine illokutionäre Kraft (z.B. bitten, fragen) und den Inhalt einer Aussage
definiert.
Formal wird das folgendermaßen ausgedrückt:
<Performativ> (<Inhalt>)
Wobei Performativ ein Schlüsselwort ist, welches den gerade verwendeten Sprechakt
angibt:
„Frage (es regnet)“ bedeutet also: Regnet es?
Schließlich gibt es noch die perlokutionäre Komponente. Diese bezeichnet die Effekte,
die illokutionäre Sprechakte auf den Zustand des Adressaten haben. So ist z.B. die Bitte
an John eine Tasse Kaffee zu holen illokutionär, wenn er dann losgeht um die Tasse
Kaffee zu holen, ist auch die perlokutionäre Komponente erfüllt.
5
2. Indirekte Kommunikation
Bei der indirekten Kommunikation tauschen sich die Agenten in einem System nicht
direkt miteinander aus. Einer der Vorteile liegt darin, dass keine komplizierten
Kommunikationsprotokolle gebraucht werden und sie somit einfach zu implementieren
ist.
2.1 Blackboard
Die Grundidee des Blackboard Systems ist, dass mehrere verschiedene Agenten
zusammen an einem Problem arbeiten und zur Kommunikation das Blackboard benutzen.
Dieses System besteht im allgemeinen aus 3 verschiedenen Komponenten[1], wobei bei
der klassischen Variante keine Kontrolleinheit vorhanden ist.
•
•
•
Agenten, auch Knowledge Sources oder Wissensquelle genannt
Blackboard
Kontrolleinheit
Die Agenten des Systems haben die Aufgabe, bestimmte Probleme zu lösen. Dies
geschieht, indem sie zur Lösung relevante Beiträge auf das Blackboard schreiben, die
wiederum dazu dienen können, weitere Teillösungen des Problems zu finden. Solange die
entgültige Lösung des Problems noch nicht gefunden wurde, bzw. mit Hilfe der
Informationen des Blackboards noch nicht konstruiert werden konnte, wird diese Prozedur
fortgesetzt. Wichtig ist, dass jeder Agenten des Systems über alle für ihn wichtigen
Einträge des Blackboards Bescheid weiß, damit er effizient an der Lösung des Problems
arbeiten können. Der Agent kann dabei selber entscheiden, welche Art von Informationen
er für Wichtig erachtet. Damit die Agenten nicht ständig das Blackboard nach neuen
Einträgen durchsuchen müssen wird, wann immer etwas Neues hinzukommt, sich eine
Information ändert oder ein Beitrag gelöscht wird, ein Event ausgelöst. Daraufhin können
die Agenten entscheiden, ob sie sich die Änderung ansehen wollen, oder nicht. Die
Agenten des Systems müssen nicht alle dieselben Fähigkeiten haben, die einzige
Vorraussetzung, die sie erfüllen müssen, um an der Lösung des Problems mitarbeiten zu
können, ist die Einhaltung der Schnittstelle des Blackboards und das Verständnis der
benutzten Sprache.
Das Blackboard ist eine gemeinsame Datenstruktur, die alle wichtigen Informationen zur
Lösung des Problems enthält. Oft weist das Blackboard eine hierarchische Struktur auf[1],
dies ist aber nicht zwingend notwendig. Es wäre z.B. möglich, dass auf verschiedenen
Ebenen das Problem in unterschiedlichen Repräsentationsformen und
Abstraktionsformen dargestellt wird. Die Agenten arbeiten auf unterschiedlichen Ebenen
und sehen jeweils nur die eigene Ebene, wobei es ihnen dann nur möglich ist Daten an
eine Ebene höher weiterzugeben oder die Agenten einer Ebene tiefer zu kontrollieren.
Die Kontrolleinheit ist unabhängig von den Agenten und dient zur Steuerung und
Koordination der Agenten. Sie entscheidet welcher von ihnen den nächsten Schritt im
Lösungsprozess machen darf. Die Agenten melden sich bei der Komponente an, wenn sie
einen Beitrag leisten möchten, und teilen dazu die Kosten und die Qualität des Beitrags
6
mit. Falls sich mehrere Agenten anmelden, entscheidet die Kontrolleinheit anhand der
erhaltenen Informationen, welcher als nächstes handeln darf.[2] Die Implementierung
dieser Kontrolleinheit kann sich als sehr anspruchsvoll erweisen, da sie leicht zum
Flaschenhals werden kann, wenn sich viele Agenten in einem System befinden, die alle
viele Beiträge leisten möchten. So wurde z.B. die Kontrollkomponente in der ersten
Version von Hearsay II, ein Spracherkennungssystem, prozedural umgesetzt, bei den BB1
– Systemen von B. Haynes-Roth (1985) wurde diese Einheit selbst als Blackboard
organisiert. [1]
Abbildung 2 Blackboardmodell mit Kontrolleinheit
Zu den Vorteilen des Blackboard Systems zählt ihre universelle Anwendbarkeit. Es gibt
keine festgeschriebene Art von Problemen, die zu lösen sind. Es lassen sich die
unterschiedlichsten Arten von Problemen lösen. Ein weiterer Vorteil ist die
Unabhängigkeit der Agenten untereinander. Da sie nicht aufeinander angewiesen sind, ist
es leicht möglich einen Agenten zu entfernen oder auszutauschen.
Zu den Nachteilen gehört die Ineffizienz, die durch umfangreiches Kontrollregime
entstehen kann[1]. Wenn sich zu viele Agenten im System befinden, und die
Kontrolleinheit nur langsam die Informationen verarbeiten kann, dann kommt es hier zu
einem Engpass, und die Lösung des Problems dauert länger.
7
2.2 Stigmergy
Der Begriff Stigmergy wurde erstmals von dem Biologen Grassé eingeführt. Das Wort
stammt aus dem griechischem und ist zusammengesetzt aus stigma (Zeichen) und
ergon(Arbeit). Die Kommunikation erfolgt hierbei über Veränderungen in der Umwelt.
An bestimmten Stellen der Umwelt werden bestimmt Dinge verändert, und alle im System
befindlichen Agenten können diese Änderung deuten und darauf reagieren. Somit dient
die Umwelt als Kommunikationsmedium. Es gibt zwei unterschiedliche Arten von
Stigmergy[3]
•
•
qualitative Stigmergy
quantitative Stigmergy
Quantitative Stigmergy bedeutet, dass durch Erhöhung des Reizes auch die Erhöhung
einer Reaktion darauf steigt. Ein Beispiel hierfür sind Ameisen, die auf Futtersuche
gehen. Die Ameisen laufen anfangs ziellos durch die Gegend und hinterlassen dabei
Pheromonspuren. Hat eine Ameise eine Futterstelle gefunden, sammelt sie etwas Futter
und bringt es auf dem gleichen Weg zurück zum Nest. Dabei hinterlässt sie wieder eine
Pheromonspur, wodurch die erste verstärkt wird. Treffen andere Ameisen auf diese Spur,
so haben sie den Drang dieser Spur zu folgen. Da diese Spur mit der Zeit verdampft,
werden die weniger benutzten Wege mit der Zeit schwächer im Geruch. So kommt es,
dass sich mit der Zeit der kürzeste Weg zur Futterquelle bei allen Ameisen durchsetzt, da
auf diesem Weg die Spur am deutlichsten ist.
Bei qualitativer Stigmergy wird die Reaktion durch die Art der Reizung gesteuert. So ist
es hier wichtig, welche Art von Pheromon ausgestoßen wird, nicht aber wie viel davon.
Ein bekanntes Beispiel hierfür ist die Nestbildung der Papierwespen.
In der Natur ist häufig eine Mischung beider Formen zu finden.
Ein Nachteil bei Stigmergy ist sicherlich, dass es oft länger dauern kann, bis eine
Veränderung bemerkt wird und somit die Reaktionszeiten langsamer ausfallen können als
bei anderen Verfahren.
Ein Beispiel für qualitative Stigmergy:
Abbildung 3 Nest der Papierwespe [10]
8
3. Direkte Kommunikation
Unter direkter Kommunikation versteht man, wenn sich 2 oder mehrere Agenten
austauschen, ohne dabei auf andere Hilfsmittel wie z.B. ein Blackboard oder die Umwelt
zurückgreifen zu müssen.
3.1 Einführung in ACLs (Agent Communication Language)
Unter ACL versteht man Sprachen, die es verschiedenen Agenten ermöglichen, Wissen
und Informationen auszutauschen. Damit der Austausch überhaupt möglich ist, müssen
die Agenten über eine gemeinsame Sprache und evtl. ein gleiches Verständnis des
Wissens verfügen. Des weiteren sollten einige Eigenschaften von den Agenten erfüllt
werden, damit eine „vernünftige“ Kommunikation zustande kommt. So sollte
gewährleistet sein, das die Agenten immer die Wahrheit sagen. Auf den folgenden Seiten
werde ich einige ACLs vorstellen.
3.2 FIPA (Foundation for Intelligent Physical Agents)
Eine Organisation ist die FIPA. Sie wurde 1996 gegründet und macht es sich zum Ziel,
Software Standards für Agenten und Agenten Systeme festzulegen[5]. Von ihr wurde die
FIPA-ACL entwickelt, die auf der Theorie der Sprechakte basiert.(siehe 1.2) Sie ist vom
Grundkonzept und auch von der Syntax ähnlich wie KQML, auf das später noch genauer
eingegangen wird. Die Semantik ist völlig mit mathematischen Formeln definiert.
Nun ein Beispiel zum Aufbau der FIPA-ACL[8]:
(inform
:sender
:receiver
:content
:in-reply-to
:language
:ontology
:protocol
)
bt-agent
customer-agent
(Line_quote(bt_cusomer,123)300)
round-4
prolog
bt-auctions
fipa-contract-net
3.3 KSE (Knowledge Sharing Effort)
Das KSE-Projekt wurde im Jahre 1990 gestartet und ist ein Konsortium von
verschiedenen Universitäten und anderen Forschungseinrichtungen. Es wird finanziert
von der DARPA (Defense Advanced Research Projects Agency) . Innerhalb dieses
Projekts wurden verschiedene Arbeitsgruppen gebildet, die es sich zum Ziel gemacht
haben, standarisierte Strukturen festzulegen, mit Hilfe derer es Möglich ist, mit großen
Wissensbasen umzugehen. Eine Arbeitsgruppe des KSE ist Interlingua, die sich mit der
Übersetzung verschiedener Repräsentationssprachen beschäftigt. Eine weitere ist KRSS
9
(Knowledge Representation System Specification), welches sich mit der Definition
gemeinsamer Konstrukte von Repräsentationssprachen beschäftigt. Dann gibt es noch die
External Interface Working Group, die sich die Interaktion zwischen Wissensbasen und
die Entwicklung von Kommunikationsprotokollen, wie z.B. KQML (siehe 3.6 KQML) zur
Aufgabe gemacht hat. Die SRKB (Shared, Reusable Knowledge Bases) kümmert sich um
den Inhalt der Wissensbasen.
Abbildung 4 Aufbau des KSE
Die ACL des KSE besteht aus 3 verschiedenen Teilen[4]
•
•
•
Vokabular
Innere Sprache
Äußere Sprache
Das Vokabular, auch als Ontologie bezeichnet, ist ein großen, nicht abgeschlossenes
Wörterbuch.
Die innere Sprache, z.B. KIF, dient zum Wissensaustausch zwischen den Agenten
Die äußere Sprache, z.B. KQML, regelt die Kommunikation zwischen den Agenten.
Diese Elemente werden im Folgenden vorgestellt.
3.4 Ontologien
Der Begriff Ontologie kommt aus dem Griechischen und geht auf den Philosophen
Aristoteles zurück. In der Philosophie bedeutet Ontologie die Lehre vom Sein und
Seienden. Eine Ontologie im technischen Sinne ist eine Spezifikation von Objekten,
Konzepten und Beziehungen. Bei dem Beispiel „(AND(Block A) (Block B) (On A B)“
repräsentiert „Block“ ein Konzept, „A“ und „B“ ein Objekt und „On“ eine Beziehung.
Man schafft sich mit Hilfe dieser Beziehungen eine gemeinsame Basis für eine
einheitliche Weltanschauung, indem die Gegenstände in der Welt eindeutig definiert
werden.[9]
Um nun selber eine Ontologie zu definieren, solle man nach [9] möglichst 4 Schritte
einhalten:
10
1. Sammeln von Begriffen und Relationen, die wichtig zur Beschreibung der Welt
sind
2. Festlegen der Struktur des Begriffes und dessen Funktion
3. Begriffe und Relationen exakt definieren, dabei redundante Begriffe entfernen
4. Fehler entfernen
Es gibt auch schon viele vorgefertigte Ontologien, die man für seine Zwecke einsetzen
kann.
3.5 KIF (Knowledge Interchange Format)
3.5.1 Allgemeines
KIF wurde von der Interlingua Gruppe des KSE entwickelt und stellt den Inhalt von
Wissensbeständen dar. Es basiert auf dem Prädikatenkalkül der ersten Ordnung. Die
Beschreibung der Sprache enthält sowohl eine Spezifikation für ihre Syntax als auch für
ihre Semantik. Es ist möglich, einfache Daten, Beschränkungen, Negationen,
Disjunktionen, Meta-Wissen und Regeln darzustellen. Ebenso kann man Objekte,
Funktionen und Relationen definieren.[2] Es gibt eine Reihe von Objekten, die
vordefiniert sind, wie z.B. die realen Zahlen [6]. Der Vorteil von KIF gegenüber anderen
Sprachen wie PROLOG, die auch Wissen speichern, ist, dass KIF keinen Interpreter
braucht, um Ausdrücke zu manipulieren. Des weiteren besteht die Möglichkeit MetaWissen darzustellen, was bei PROLOG nicht der Fall ist.
Ausdrücke können in KIF in zwei verschiedenen Formen vorliegen: linear KIF und
structured KIF. Bei linear KIF liegen alle Ausdrücke als Strings vor, während bei
structured KIF die Ausdrücke in Form von strukturierten Objekten vorliegen. Der Vorteil
beim letzteren liegt darin, dass so gespeichertes Wissen besser im Arbeitsspeicher eines
Agenten verwaltet werden kann.
3.5.2 Syntax
Um Fakten auszudrücken, bedient man sich in KIF folgender Schreibweise:
(gesinnung bot1 freund)
(gesinnung bot2 feind)
Das erste Wort hierbei steht für das Fakt, welches beschrieben werden soll. Das letzte
Wort beschreibt den Wert des Faktes. Dazwischen ist das Objekt beschrieben, auf das sich
das Fakt bezieht, wobei das Objekt nur durch ein Wort beschrieben werden kann oder
auch durch mehrere. Wichtig dabei ist, dass es eindeutig beschrieben wird.
Des weiteren gibt es viele Funktionen, die einem zur Verfügung stehen.
(+ 1 2)
11
Zu Beginn des Terms steht die Art der Funktion, die aufgerufen wird, in diesem Fall also
die Addition. Danach folgen eine Reihe von Konstanten, die an die Funktion übergeben
werden, wobei beliebig viele übergeben werden können. Der Rückgabewert ist in diesem
Fall 3. Es ist auch möglich mehrere Funktionen ineinander zu schachteln:
(>
(+ (munition weapon1) (reservemunition weapon1))
(+ (munition weapon2) (reservemunition weapon2))
)
Die Funktionen werden von innen nach außen aufgelöst. Zuerst wird also die gesamte
Munition von der 1. Waffe und der 2. Waffe berechnet, danach werden die vorhandenen
Munitionsmengen verglichen. Der Rückgabewert ist true, wenn Weapon 1 mehr Munition
hat als Weapon 2, sonst ist er false.
Weitere vordefinierte Funktionen sind nachzulesen unter [7]. Es ist auch möglich
Funktionen selbst zu definieren, darauf wird hier aber nicht näher eingegangen, da es den
Rahmen dieser Ausarbeitung sprengen würde.
Auch Folgerungen sind bei KIF möglich.
(=>
(and (real-number ?x) (even-number ?n))
(> (expt ?x ?n) 0)
)
Wenn gilt, das x eine Zahl ist, und n eine grade Zahle, dann folgt daraus, das x potenziert
mit n größer 0 ist.
Eine weitere Möglichkeit von KIF sind die Fallunterscheidungen.
(if (>= ?x 0) ?x (- ?x) )
Falls die Zahl x größer oder gleich 0 ist, liefert die Funktion x zurück, andernfalls wird auf
x die Minus-Funktion angewandt und dann das Ergebnis zurückgeliefert.
In KIF kann man auch den Glauben oder das Interesse an bestimmten Dingen
ausdrücken, was gerade für intelligente Systeme wichtig sein kann.
(believes mybot ‘(gesinnung bot1 feind))
Dies drückt aus, dass mybot glaubt, dass bot1 ein Feind ist.
(interested joe ’(tokill, ?x, ?y, ?z))
Dieses bedeutet, dass Joe daran interessiert ist, Tripel aus der tokill-Relation zu
empfangen.
12
Wichtig zu erwähnen ist auch, dass in KIF Prozeduren geschrieben werden können.
Diese Prozeduren können andere Agenten dazu bringen, bestimmte Anweisungen
auszuführen.
(progn
(fresh-line t)
(print "Hallo")
(fresh-line t)
)
Dieses Stück Programmcode bringt einen Agenten dazu, „Hallo“ zwischen zwei
Zeilenvorschüben auszugeben.
3.6 KQML
3.6.1 Allgemeines
Die KQML-Gruppe wurde 1992 gegründet und ist ein Teil des KSE. KQML ist ein
Protokoll für den Austausch von Informationen und Wissen und basiert auf der
Sprechakttheorie. Es erlaubt beliebige Sprachen zur Darstellung des Nachrichteninhaltes
und unterstützt sowohl synchrone als auch asynchrone Kommunikation. KQML hat eine
Schichtenstruktur, die aus 3 Schichten besteht.
Die innerste Schicht ist der Inhalt der Nachricht. Hierbei sind verschiedene Sprachen zur
Darstellung des Inhalts möglich, wie z.B. KIF oder PROLOG. KQML ignoriert diese
Schicht fast vollständig, es werden nur relevante Informationen zur Darstellung der
Nachricht gesucht, wie das Ende des Inhalts.
Die mittlere Schicht ist die Nachrichten Schicht. Sie beschreibt die Logik der
Kommunikation. Hier wird die Nachricht selbst kodiert. Der Nachrichtentyp wird
spezifiziert und es werden die möglichen Interaktionen bestimmt, die mit dem Agenten
möglich sind.
Die äußere Schicht, Kommunikationsschicht, beschreibt die Mechanik der
Kommunikation. Sie enthält Daten wie Absender und Empfänger.
Abbildung 5 KQML - Schichten
13
3.6.2 Semantik
In KQML wird davon ausgegangen, dass jeder Agent eine virtuelle Wissensbasis
verwaltet. Die Einträge in dieser sind unterteilt in Fakten (beliefs) und Ziele (goals). Die
Fakten kodieren Informationen, die ein Agent über sich und seine Umwelt besitzt, Ziele
zeigen den Zustand der Umwelt, den der Agent erreichen möchte. Die Agenten benutzen
KQML, um über den Inhalt ihrer eigenen und anderen Wissensbasen zu
kommunizieren.[7]
3.6.3 Syntax
Die Syntax von KQML ist Lisp-ähnlich und das Basisprotokoll ist folgendermaßen
definiert:
(KQML-performative
:sender
:receiver
:language
:ontology
:content
...)
<word>
<word>
<word>
<word>
<expression>
Die KQML-Performative sind festgeschriebene Ausdrücke und basieren auf den
Sprechakt Performativen. Hiermit wird der Verwendungszweck der Nachricht
ausgedrückt und festgelegt, welches Verhalten vom Empfänger der Nachricht erwartet
wird. Man kann sie in 7 verschiedene Kategorien einteilen[2]:
1. Basis Query:
2. Multiresponse Query:
3. Response:
4. Generic informational:
5. Generator:
6. Capability-definition:
7. Networking:
(evaluate, ask-one, ask-all,...)
(stream-in, stream-all,…)
(reply, sorry,…)
(tell, achieve, cancel, untell,…)
(standby, ready, next,…)
(advertise, subscribe,…)
(register, forward,…)
Ich stelle nun 2 wichtige Performative vor:
ask if:
tell:
Der Absender fragt, ob der Inhalt des content Feldes für den Empfänder
wahr ist
Der Sender teilt mit, dass der Inhalt des content Feldes in seinen
Wissensbasis vorhanden ist
Weitere können unter[7] nachgelesen werden.
Im Schlüsselwort :content ist die eigentlich zu übermittelnde Nachricht gekapselt, die in
der Sprache geschrieben ist, die in :language angegeben ist, wie z.B. KIF oder PROLOG
und die Vokabeln benutzt, die in dem in :ontology angegebenen Vokabular definiert sind.
14
Zusätzlich zu den im Basisprotokoll beschriebenen Schlüsselwörtern, gibt es noch weitere
mögliche Argumente, die zum Protokoll hinzugefügt werden können. Hier einige
Beispiele:
Encoding
reply-to
reply-by
Gibt an, wie der Inhalt der Nachricht codiert wurde
Gibt den Empfänger der Antwort an
Deadline, bis wann der Empfänger geantwortet haben
soll
Eine einfache Information wird folgendermaßen weitergegeben:
(inform
: sender
: receiver
: language
: ontology
: content
)
Bot1
Bot2
KIF
Quake-World
(AND (Feind A) (Feind B) )
Bot2 wird von Bot1 informiert, dass A und B Feinde sind.
Betrachten wir nun ein Beispiel eines Dialogs:
(ask-one
: sender
Melanie
: receiver
Sparkasse
: language
KIF
: ontology
money
: content
(interested melanie ’(money, kontonr, ?money,))
)
Eine Antwort auf diese Anfrage könne so aussehen:
(tell
: sender
: receiver
: language
: ontogogy
: content
Sparkasse
Melanie
KIF
money
(money kontonr 0)
)
Es ist auch möglich, KQML Statements zu schachteln. In folgendem Beispiel kann Agent
1 Agent 2 nicht direkt erreichen, und kommuniziert über Agent 3 mit Agent 2:
(tell
:sender
:receiver
Agent1
Agent3
15
:language
:ontology
:content
KQML
KQML-Ontology
(inform
:sender
:receiver
:language
:ontology
:content
)
Agent1
Agent2
KIF
Blocks-World
(AND (Block A) (Block B) (On A B)
)
KQML ist also ein sehr flexibles Kommunikationsprotokoll, da man hierbei nicht an eine
bestimmte Sprache zur Übermittlung von Wissen gebunden ist.
16
4. Adressaten
In einem System mit vielen verschiedenen Agenten ist es wichtig sich über die
unterschiedlichen Adressaten der Kommunikation klar zu werden. Es gibt 3 verschiedene
Möglichkeiten der Kommunikation:
• Singlecast
• Multicast
• Broadcast
Im Folgenden werde ich Näher auf diese Möglichkeiten eingehen und sie erklären.
4.1 Singlecast
Es gibt die Möglichkeit einer one to one communication. Hierbei spricht ein Agent genau
einen anderen an. Ein weiterer Fall ist die many to one communication, bei der eine
Gruppe von Agenten einem einzelnen eine Nachricht schickt. Dieser muss evtl. die
empfangenen Nachrichten dann noch in die richtige Reihenfolge bringen. Besteht in
diesem Fall die Gruppe aus allen Agenten des Systems, so war dies eine all to one
communication.
Anders ausgedrückt wird bei Singlecast ein Agent direkt adressiert.
4.2 Multicast
Von einer one to many communication spicht man, wenn ein Agent eine Gruppe von
anderen Agenten anspricht. Es kann auch eine Gruppe von Agenten eine andere Gruppe
ansprechen, das nennt man dann many to many communication. Wenn alle Agenten an
eine bestimmte Gruppe eine Nachricht versenden, so heißt das all to many
communication.
Bei Multicast wird also immer eine bestimmte Empfängergruppe angesprochen, die an
einer bestimmten Adresse den Kanal abhören
4.3 Broadcast
Spricht ein Agent alle anderen Agenten im System an, so nennt man das auch one to all
communication. Auch hier besteht wieder die Möglichkeit, das nicht nur einer alle
anspricht, sondern auch eine Gruppe von Agenten allen anderen eine Nachricht
zukommen lässt, many to all communication, oder alle Agenten an alle Nachrichten
schicken, all to all communication.
In diesen Fällen spricht man von Broadcast. Es werden also alle Agenten im System
angesprochen, die den Kommunikationskanal abhören.
17
4.4 Vor – und Nachteile
Broadcast ist für die Agenten die einfachste Möglichkeit zu kommunizieren, da sie dabei
die Adresse des Kommunikationspartner nicht kennen müssen. Allerdings ist in diesem
Verfahren auch die Auslastung des Kommunikationskanals am größten, da jeder alle
Nachrichten bekommt. Außerdem müssen die Agenten hierbei die für sie relevanten
Nachrichten selber herausfiltern.
Der Vorteil von Singlecast liegt darin, dass jeder Agent sicher sein kann, dass die
bekommene Information auch wirklich für ihn gedacht ist, will man allerdings per
Singlecast mehreren Agenten die gleiche Nachricht schicken, bedeutet das mehr
Zeitaufwand die Nachricht jedes Mal wieder an nur einen zu schicken.
Multicast ist also ein guter Mittelweg, da hierbei nur bestimmte Gruppen adressiert
werden und es auch nicht ausgeschlossen ist, dass Agenten zu mehreren Gruppen gehören.
Ein Beispiel, wo Multicast angewendet werden kann, und das sich auch auf die Aufgabe
unserer Projektgruppe bezieht, ist die Modellierung eines Spiels, in dem 2 Mannschaften
von Agenten gegeneinander antreten, wobei jede Mannschaft über ein Headset die
Möglichkeit zur Kommunikation besitzt. Da man nicht möchte, dass die gegnerische
Gruppe die eigenen Pläne mitbekommt, schickt man die Nachricht nur an Mitglieder der
eigenen Gruppe. Diese kann man dann falls nötig noch mal in Untergruppen wie
Angreifer und Verteidiger unterteilen, so dass man noch mal exakter mit den gewünschten
Gruppenmitgliedern kommunizieren kann.
4.5 Reichweite
Manchmal ist es auch sinnvoll, die Adressatengruppe daraufhin zu beschränken, in
welcher Entfernung sich die Agenten zueinander befinden. So erreicht man mittels
globaler Kommunikation alle Agenten im System, sei es durch Broad-, Multi-, oder
Singlecast, während man bei der lokalen Kommunikation nur eine bestimmte Gruppe von
Agenten erreichen kann, die sich in der Umgebung befinden, wobei die Umgebung noch
definiert werden muss. So ist es je nach System sinnvoll einen lokalen Broadcast
durchzuführen oder die nächsten x Nachbarn mit in die Kommunikation einzubeziehen.
Ersteres ist sinnvoll, wenn z.B. möglichst real ein Haus modelliert wurde, in dem sich
verschiedene Personen (Agenten) in verschiedenen Räumen befinden. Hier ist es
zweckmäßig einen lokalen Broadcast durchzuführen, wenn eine Person etwas mitzuteilen
hat, da alle im Raum anwesenden verstehen was gesagt wird, aber alle nicht im Raum
befindlichen Personen das auch im realen Leben nicht verstehen können. Nur die nächsten
x Nachbarn zu informieren macht dann Sinn, wenn z.B. die Kommunikation darin besteht
eine vorgegebene Anzahl wie z.B. 3 Agenten für seine eigene Gruppe zu rekrutieren und
am eigenen Standort zu versammeln. Bei diesem Beispiel ist es am besten, wenn man an
die nächsten 3 Agenten eine Nachricht schickt mit der Aufforderung herzukommen.
18
5. Bezug zur Projektgruppe KIMAS
Innerhalb der Projektgruppe besteht die Aufgabe, ein Multiagenten System zu entwickeln,
in dem die Agenten ein Gebäude errichten, und Capture the Flag spielen, wobei auch die
Umgebung kartographiert werden soll. Dabei ist es unerlässlich, dass die Agenten
untereinander kommunizieren. So können sie sich beim Gebäudebau und innerhalb der
eigenen Mannschaft beim Erobern der Flagge koordinieren.
Zuerst muss entschieden werden, ob unsere Agenten auf direktem oder indirektem Wege
miteinander kommunizieren sollen, wobei meiner Meinung nach bei der indirekten
Kommunikation nur das Blackboard in Frage kommt, da Stigmergy für Capture the flag in
einigen Fällen zu langsam sein kann, d.h. es kann möglich sein, dass nicht alle Agenten
sofort auf eine wichtige Situation reagieren. So bleibt also von der indirekten
Kommunikation noch das Blackboard Modell, wobei dabei entschieden werden muss,
welche Struktur das Modell genau haben soll. Der Erfolg des Blackboard Modells hängt
meiner Meinung nach von der Qualität der Kontrolleinheit ab, da diese die Informationen
verwaltet.
Wird die direkte Kommunikation gewählt, so muss man sich für eines der
Kommunikationsprotokolle entscheiden. Würden wir hier mit KQML arbeiten, so müssen
wir noch eine Sprache zum Wissensaustausch wählen. Hierbei kommen unter anderem
PROLOG und KIF in Frage. KIF hat den Vorteil, dass wir Prozeduren schreiben können,
und auch Glauben ausdrücken können, was in PROLOG nicht der Fall ist. Dann müssen
wir uns auf ein Vokabular einigen, was alle Agenten im System verstehen und zuletzt ist
noch wichtig, sich über die Reichweite und die Adressaten der Kommunikation klar zu
werden. Es würde sich eine globale Reichweite für den Wissensaustausch anbieten, da die
Agenten im realen Leben wahrscheinlich auch mit Funkgeräten o.ä. ausgestattet wären.
Da bei Capture the Flag 2 Gruppen existieren ist es sinnvoll keinen Broadcast
durchzuführen, da sonst auch die gegnerische Mannschaft an die eigenen Informationen
kommen könnte. Also besteht hier die Möglichkeit für Multicast.
19
6. Quellenverzeichnis
[1]
Jaques Ferber: Multiagenten-Systeme, Eine Einführung in die Verteilte künstliche
Ingelligenz, Addison Wesley, 1997
[2]
Gerhard Weiss: Multiagent Systems - A Modern Approach to Distributed
Artificial Intelligence, 1999 Massachusetts Institute of Technology
[3]
Andreas Goebels: Strukturbildung durch koordinierte und evolutionäre
Partikelschwärme
http://www.uni-paderborn.de/cs/agklbue/staff/labeo/work/publications/Diplom.pdf
[4]
Prof. U. Borghoff: Vorlesung Verteiltes Informationsmanagement 1998
http://www2-data.informatik.unibwmuenchen.de/People/borghoff/slides/vim1998/sld042.htm
[5]
FIPA Homepage
http://www.fipa.org
[6]
Spezifikation von KIF
http://www.fipa.org/specs/fipa00010/XC00010C.html
[7]
Spezifikation von KQML
http://www.csee.umbc.edu/kqml/kqmlspec/spec.html
[8]
Beispiel zu FIPA-ACL
www.igd.fhg.de/~busch/vorlesung/mas_ausarbeitungen/SemayKommunikation.pdf
[9]
Definition Ontologie
http://www.informatik.huberlin.de/~bien/ontologie.html#Was%20ist%20eine%20Ontologie?
[10]
Abbildung des Nestes der Papierwespe
http://www.cnse.caltech.edu/Research02/reports/easton1full.html
20