Multiagentensysteme: Modelle, Programmierung, Plattformen

Kommunikation und Interaktion

Agent-Agent und Agent-Welt Kommunikation

Shared Memory

• Agenten sind parallele und verteilte Systeme!

• Eine der einfachsten Kommunikationsmodelle und Architekturen für parallele Systeme ist der geteilte Speicher.

• Das Shared-Memory-Modell ist ein häufig verwendetes Interprozesskommunikationsparadigma für parallele, weniger für verteilte Systeme. Es ist eng verwandt mit dem Parallelregister und Random-Access-Maschine (PRAM),

• Das PRAM-Modell nimmt n identische Verarbeitungseinheiten (PU) an, die mit einer Shared-Memory-Ressource über Direktzugriff (SRAM) verbunden sind.

  • Speicherzellen haben gleiche Breite, die durch eine numerische Adresse referenziert werden.
  • Das SRAM-Modell unterstützt konkurrierende Lese- und Schreiboperationen.
  • Lesen ist i.A. konfliktfrei, Schreiben kann zu Konflikte führen.

Shared Memory

• Agenten können über den geteilten Speicher Daten austauschen!
• Aber: Es gibt Datenaustausch ohne explizite Synchronisation zwischen den Agenten.
• Und: Das SRAM Modell ‘verletzt’ das Autonomieparadigma von Agenten!

Tupelräume

• Tupel-Räume stellen ein assoziiertes Shared-Memory-Modell dar, wobei die gemeinsam genutzten Daten als Objekte mit einer Reihe von Operationen betrachtet werden, die den Zugriff der Datenobjekte unterstützen

• Tupel sind in Räumen organisiert, die als abstrakte Berechnungsumgebungen betrachtet werden können.

• Ein Tupelraum verbindet verschiedene Programme, die verteilt werden können, wenn der Tupel-Space oder zumindest sein operativer Zugriff verteilt ist.

  • Oder: Mobile Agenten als Tupel Verteiler!

• Das Tupelraum Organisations- und Zugangsmodell bietet generative Kommunikation, d.h. Datenobjekte können in einem Raum durch Prozesse mit einer Lebensdauer über das Ende des Erzeugungsprozesses hinaus gespeichert werden.

• Ein bekanntes Tupelraum-Organisations- und Koordinationsparadigma ist Linda [GEL85].

Tupelräume

Tupelräume

• Kommunikation von Agenten über Tupelräume ist eine Koordinationssprache.

Tupelräume - Datenmodell

• Die Daten sind mit Tupeln organisiert.

• Ein Tupel ist eine lose gekoppelte Verbindung einer beliebigen Anzahl von Werten beliebiger Art /Typ/

• Ein Tupel ist ein Wert und sobald es in einem Tupelraum gespeichert ist, ist es persistent.

• Tupeltypen ähneln den Datenstrukturtypen, sie sind jedoch dynamisch und können zur Laufzeit ohne statische Beschränkungen erstellt werden.

• Auf die Elemente von Tupeln kann nicht direkt zugegriffen werden, was üblicherweise Mustererkennung und musterbasierte Dekomposition erfordert, im Gegensatz zu Datenstrukturtypen, die einen benannten Zugriff auf Feldelemente bieten, obwohl die Behandlung von Tupeln als Arrays oder Listen diese Beschränkung lösen kann.

• Ein Tupel mit n Feldern heißt n-stellig und wird in der Notation <v₁, v₂, ..> angegeben.

Tupelräume - Datenmodell

Beispiele

<'SENSOR',1000>
<'SENSOR2',[10,100,2]>
<1,3,5,7,11>
<'SLEEPMODE',True,2500.34>
<0,'OFF'>
<1,'ON'>

• Formal werden Tupel als Vektoren durch die folgende Generierungsregel mit Werten v, Ausdrücken ε und Variablen x definiert, die als tatsächliche Parameter betrachtet werden (d.h. Variablen x, die mit Wertesemantik verwendet werden):

Tupelräume - Datenmodell

• Tupelwerte erfordern einen Mustervergleich basierend auf dem Vorlagenmuster mit der folgenden Generierungsregel, bestehend aus tatsächlichen (v, ε, x) und formalen Parametern (x?, Variablen, die mit Referenzsemantik verwendet werden):

• Ein Suchmuster kann ein Wildcard (⊥) anstelle von formalen Parametern verwenden.

• Jedes Tupel t hat eine Typsignatur Sig (t) = S_t = <T₁; T₂; …; T_n>, ein Tupel mit der gleichen Stelligkeit wie t, das den Typ jedes Tupelfeldes angibt.

• Ein Tupel kann nur durch seine Verknüpfung mit Templates p angesprochen werden.

Tupel Räume - Datenmodell

• Üblicherweise wird das erste Feld eines Tupels als symbolischer Schlüssel behandelt, der eine Tupelunterklasse identifiziert, indem Textzeichenfolgen oder aufgezählte symbolische Konstantenwerte verwendet werden.

Mustersuche

Tupelräume - Operationale Semantik

• Es gibt eine Reihe von Operationen, die von Prozessen angewendet werden können, bestehend aus
  • einer Reihe reiner Datenzugriffsoperationen, die Tupel als passive Datenobjekte behandeln,
  • und Operationen, die Tupel als eine Art von aktiven Rechenobjekten behandeln (genauer gesagt, zu berechnende Daten).
  • RPC-Semantik (Remote Procedure Call).

out(t)

Die Ausführung der Ausgabeoperation fügt das Tupel t in den Tupelraum ein. Mehrere Kopien desselben Tupelwerts können eingefügt werden, indem die Ausgabeoperation iterativ angewendet wird. Die gleichen Tupel können nach dem Einfügen in den Tupelraum nicht unterschieden werden.

Beispiel: out("Sensor",1,100); out("Sensor",2,121);

Tupelräume - Operationale Semantik

inp(p)

Die Ausführung der Eingabeoperation entfernt ein Tupel t aus dem Tupelraum, der der Mustervorlage p entspricht. Wenn kein passendes Tupel gefunden wird führt das zu einer Blockierung des aufrufenden Prozesses bis ein passendes Tupel eingestellt wird.

Beispiel: inp("Sensor",1,s1?); inp("Sensor",i?,s?);

rd(p)

Die Ausführung der Leseoperation gibt eine Kopie eines Tupels t zurück, dass der Vorlage p entspricht, entfernt sie jedoch nicht. Wenn kein passendes Tupel gefunden wird führt das zu einer Blockierung des aufrufenden Prozesses bis ein passendes Tupel eingestellt wird.

Beispiele: rd("Sensor",1,s1?); rd("Sensor",i?,s?);

Tupelräume - Operationale Semantik

inp?(p), rd?(p)

Nichtblockierende Version von inp/rd. Wird kein passendes Tupel gefunden wird die Operation ergebnislos terminiert.

Beispiel: res:=inp?('SENSOR',a?,b?);

inpw?(tmo,p), rdw?(tmo,p)

Teilblockierende Version von inp/rd, Wird einer Zeit von tmo kein passendes Tupel gefunden wird die Operation abgebrochen.

Beispiel: res:=inpw?(1000,'SENSOR',a?,b?);

• Die Verwendung von zeitlich unbegrenzt blockierenden Operationen kann unter Betrachtung der Lebendigkeit von Agenten nachteilig sein. Daher sollte immer eine zeitliche Begrenzung und anschließende Abfrage des Operationsstatus erfolgen (abgebrochen?)

Tupelräume - Operationale Semantik

test(t), testandset(p,function (t)→t)

Nicht blockierender Test eines Tupels und atomare Veränderung eines Tupels, dass der Vorlage p entspricht. Das zweite Argument ist eine Abbildungsfunktion. Das Ergebnistupel ersetzt das ursprüngliche.

Markierungen

• Tupel sind persistent und können für immer in einem Tupelraum verbleiben!
• Daher ist die Verwendung von Markierungen häufig sinnvoll.
• Eine Markierung ist ein Tupel mit einer Lebenszeit τ
• Nach Ablauf der Lebenszeit wird das Tupel - sofern es nicht entfernt wurde - durch einen Garbagecollector entfernt.

mark(tmo,t)

Ausgabe eines Tupels t mit einer Lebenszeit τ (im Tupelraum).

Tupelräume - Operationale Semantik

eval(p)

Diese Operation ermöglicht die Injektion von aktiven Tupeln, die derzeit nicht vollständig ausgewertet sind, indem ein erweitertes funktionales Tupel t verwendet wird (mit erweitertem dt :: = v | ε | x | f (x) mit einem Funktionsargument). Das Tupel wird erst bei Bedarf in einem eigenen Prozess ausgewertet (durch inp oder rd Operation initiiert)

Diese Operation nimmt eine Funktion f (x) an, die in den Prozessen vorhanden ist, die am Tupleraum teilnehmen und die für die vollständige Berechnung dieser Tupel verwendet werden kann.

Alternative Implementierung mit eval (Klientenseite) und listen und reply Operationen (Serverseite):

P1: eval("square",2,y?)
P2: def sq = fun x -> x*x;
    listen("square",x?,?);
    y=sq(x);
    reply("square",x,y);

Tupelräume - Synchronisationsmodell

• Es gibt Produzenten- (Generator) und Verbraucherprozesse.

1. Ein Produzent erzeugt ein Tupel, das von einem Konsumentenprozess entfernt werden kann.

   • Die Tupelausgabeoperation endet unmittelbar (asynchron), alternativ nachdem das Tupel im Tupelraum gespeichert wurde (synchron).

2. Ein Verbraucher-Prozess wird blockiert, wenn die Anfrage nicht bearbeitet werden kann, wenn im Tupel-Bereich tatsächlich kein passendes Tupel vorhanden ist.

3. Nachdem ein übereinstimmendes Tupel im Tupelraum gespeichert wurde, wird es sofort einen der wartenden Verbraucherprozesse zugewiesen.

• Daher ist die Eingabeoperation immer synchron. Einzige Ausnahme sind die nicht permanent blockierenden Versionen, die das Warten auf eine obere Zeitgrenze begrenzen (Timeout).

• Es gibt keine anfängliche zeitliche Anordnung von Erzeuger- und Verbraucheroperationen.

Tupelräume - Beispiele

Verteilte Tupelräume

• Die Verteilung von Tupel-Räumen auf verschiedenen Rechnerknoten impliziert Synchronisationsprobleme und erfordert normalerweise eine zuverlässige Gruppenkommunikation, die in Rechnernetzwerken nicht erwartet werden kann.

• Die Verteilung von Tupel-Räumen bedeutet die Verteilung und asynchrone Ausführung einer Menge von Tupelraum-Servern anstelle eines einzelnen Servers.

• Ein Tupelraum-Server bietet die notwendige Koordination für gleichzeitige oder verschachtelte In / Out-Anfragen.

  • Die Verteilung der Server führt zu einer Verteilung der Koordination.
  • Dieses Problem kann jedoch gelöst werden, indem der Tupelraum in Unterräume partitioniert wird und jeder Unterraum auf einem anderen Knoten von einem Server bedient wird.
  • Problem: Tupel sind nicht gleichmäßig verteilt → schlechtes Load Balancing!

Verteilte Tupelräume

Kommunikationssignale

• Signale sind einfache Nachrichten die

  • An einen bestimmten Prozess oder Agenten gerichtet sein kann → Unicast;
  • An eine bestimmte Gruppe von Prozessen oder Agenten → Multicast;
  • Oder an unbestimmte Gruppe von Prozessen oder Agenten in der Umgebung → Broadcast

• Ein Signal besteht aus einem Signaltyp (Nummer, Zeichenkette usw.) und einem (optionalen) Datenteil (Signalargument)

• Ein Signal kann gesendet und empfangen werden.

• Häufig wird auf den Empfang eines Signals nicht aktiv gewartet sondern mittels Signalhandlern, die eingehende Signale asynchron verarbeiten.

• Ein Agent kann verschiedene Signale aus einer Menge S=[Sig₁,Sig₂,..} verarbeiten

• Für jedes Signal muss ein Signalhandler installiert werden!

Kommunikationssignale

Verarbeitung von Signalen

signal SIGNAL1,SIGNAl2;
Ag1: 
  on(SIGNAL1, function (arg,from) { 
   do process signal SIGNAL1 from sender });
  on(SIGNAL2, function (arg,from) { 
   do process signal SIGNAL2 from sender });
Ag2: 
  send(Ag1,SIGNAL,ε;

• Signale sind gekennzeichnet durch das Tupel
  <Absender,Empfänger,Name,Wert>

• Nachteil gegenüber Tupeln: Der Agent kann die eingehenden Nachrichten nicht filtern bezüglich

  • Inhalt
  • Relevanz und Interesse
  • Absender

Kommunikationssignale

Kommunikationssignale

• Anders als bei Tupeln muss der Empfänger (Agent) dem Absender (Agent) bekannt sein (Agentenreferenz)
  • Eltern-Kind Beziehungen werden daher häufig für Unicast Signale verwendet
  • Gruppenbeziehungen können durch Agentenklassen und räumliche Bereiche entstehen

Routing

• Signale adressieren mobile Agenten die ihren Standort, d.h. die Plattform, wechseln können

• Der Vermittlung (Routing) der Signalnachrichten kommt daher besondere Bedeutung zu.

• Eine Möglichkeit eine Signalnachricht zwischen zwei Agenten A und B zu vermitteln ist die Vermittlung entlang des Pfades von A und B (Spuren)

  • Wenn die Spuren von A und B sich irgendwo kreuzen (Kreuzungspunkte sind die Plattformen) so kann die Nachricht über den Kreuzungspunkt zugestellt werden

Kommunikationssignale

Kommunikationssignale

Höhere Kommunikation: Interaktion

• Tupelräume und Signalnachrichten sind nur ein Werkzeug um höhere Ebenen der Kommunikation zu erreichen → Interaktion von Agenten.

Sprache und Aktionen

• Kommunikation als Sprache kann aktionsorientiert und wissensbasiert sein!

• Nachrichten verfolgen Absichten und sollen beim Empfänger Aktionen auslösen.

Speech Act Theory

Die Sprechakttheorie behandelt Kommunikation als Aktion. Es basiert auf der Annahme, dass Sprachhandlungen von Agenten genauso wie andere Aktionen ausgeführt werden, um ihre Absichten zu fördern.

• Das Ziel einer Anfrage/Ersuchens (Request) eines Sprechers ist die Ausführung einer Aktion des Zuhörers.

• Das Erreichen der Ziele über Sprachkommunikation hängt von Wissen und Planung des Sprechers und des Zuhörers ab.

• Agentenkommunikationssprachen spielen daher eine wesentliche Rolle bei der Planung und Aktionsausführung wissensbasierte Agenten (deduktive)

Agentenkommunikationssprachen

• Wichtige Vertreter der sprachorientieren Kommunikation von Agenten sind:

KQML

KQML ist eine nachrichtenbasierte Sprache für die Agentenkommunikation. Daher definiert KQML ein allgemeines Format für Nachrichten. Eine KQML-Nachricht kann grob als Objekt betrachtet werden (im Sinne objektorientierter Programmierung): Jede Nachricht hat eine Performative (Zusammenhang zwischen Sprechen und Handeln, die man sich als die Klasse der Nachricht vorstellen kann) und eine Anzahl von Parametern (Attribut / Wert Paare, die man sich als Instanzvariablen vorstellen kann).

FIPA-ACL

Diese Sprache ähnelt oberflächlich KQML: Sie definiert eine “äußere” Sprache für Nachrichten, definiert 20 Performativen (wie z.B. inform), um die beabsichtigte Interpretation von Nachrichten zu definieren, und es ist keine spezifische Sprache für den Nachrichteninhalt vorgegeben. Darüber hinaus ähnelt die konkrete Syntax für FIPA-ACL-Nachrichten weitgehend der von KQML.

KQML

KQML

KQML

• KQML Nachrichten besitzen Parameter, die u.A. eine Sprache des Inhaltes und eine Ontologie festlegen → gemeinsames Verständnis!

• Eine Ontologie ist eine formale Definition eines Wissenskörpers. Die typischste Art von Ontologie beinhaltet strukturelle Komponenten. Im Wesentlichen eine Taxonomie der Klassen- und Unterklassenbeziehungen gekoppelt mit Definitionen der Relationen zwischen diesen Dingen.

KQML

Beispiele für Dialoge

(evaluate
 :sender A :receiver B 
 :language KIF :onto1ogy motors 
 : reply-with q1 :content (val (torque ml)))
(reply
 :sender B :receiver A 
 :language KIF :ontology motors 
 :in-reply-to ql :content (= (torque ml) (scalar 12 kgf)))
 
(stream-about 
 :sender A :receiver B 
 :language KIF :ontology motors 
 :reply-with q1 :content m1)
(tell
 :sender B :receiver A 
 :in-reply-to q1 :content (= (torque ml) (scalar 12 kgf)))
(tell
 :sender B :receiver A 
 :in-rep1y-to q1 :content (= (status ml) normal))
(eos
 :sender B :receiver A :in-reply-to q1)

FIPA-ACL

FIPA-ACL

Implementierung

• Weit verbreitet ist die JADE Plattform in der Agenten als Java Threads ausgeführt werden.

Ontologien

• Neben einer gemeinsamen Sprache bei der Kommunikation ist
  • Die richtige Interpretation der Inhalte, Informationen, und Wissensrepräsentation;
  • Und das Erkennen und Verstehen von Zusammenhängen (Strukturen)

wichtig für ein zielgerichtete Emergenzverhalten von Agenten.

• Ontologien können die Informationen und Inhalte die ausgetauscht werden beschreiben und klassifizieren sowie Strukturen (Zusammenhänge) zwischen Elementen beschreiben.

• Auch Ontologien benötigen eine geeignete Beschreibungssprache, z.B. im XML/JSON Format, oder die OWL– The web ontology language

• Ontologien beschreiben u.A. bzw. bestehen aus:

  • Klassen
  • Formale “ist-ein” Taxonomien, d.h., die Einordnung von Klassen
  • Attribute von Klassen
  • Wertebeschränkungen
  • Logische Randbedingungen

Ontologien

• Ontologien können sehr spezielle Beschreibungen von Elementen und Strukturen besitzen oder sehr allgemein sein.

Ontologien

Applikationsontologie

Eine Anwendungsontologie definiert Konzepte, die von einer bestimmten Anwendung verwendet werden. Es wird typischerweise auf einer Domain-Ontologie und wiederum auf einer oberen Ontologie aufbauen.

Konzepte aus einer Anwendungsontologie werden normalerweise nicht wiederverwendbar sein: Sie sind typischerweise nur in der Anwendung relevant, für die sie definiert wurden.

Domainontologie

Eine Domain-Ontologie definiert Konzepte, die für eine bestimmte Anwendungsdomäne geeignet sind.

Domain-Ontologien sind in der Regel auf Konzepten einer übergeordneten Ontologie aufbaut → Wiederverwendung von Ontologien ist sehr wichtig, da je mehr Anwendungen eine bestimmte Ontologie verwenden, desto mehr Übereinstimmung herrscht über Terme.

Ontologien

• Ontologien besitzen unterschiedliche Ausdrucksstärke, je nachdem ob sie eher informal oder formal sind.