Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) ::

Verteiltes Rechnen mit JAM Agenten (ABC)

Zusammenfassung der JAM Plattform und Anwendung im Mobilen Crowdsensing

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Motivation

Motivation

• Crowdsensing ist verteilte Datenverarbeitung

• Verteilte Datenverarbeitung bedeutet verteilte Kommunikation zwischen Prozessen

• Traditionelle verteilte Netzwerke wie das Internet der Dinge (IoT) müssen mit einer Vielzahl von Kommunikationsprotokollen und Netzwerkstrukturen umgehen können → Stark heterogene Systeme

• Datenrepräsentation ist eine weitere Hürde in solchen verteilten Systemen

• Häufig HTTP basierte Klienten-Server Kommunikation (zentrale Serverinstanz)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Datengetriebene Kommunikation

Datengetriebene Kommunikation

Bellifemine, Developing multi-agent systems with a FIPA-compliant agent framework Große Diversität an IoT Protokollen und Datenrepräsentation für die Kommunikation → nicht einheitlich

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agenten

Agenten

Agenten besitzen eine Vielzahl von Fähigkeiten, die sie von klassischen Programmen unterscheiden - obwohl Agenten auch Programme sein können!

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agenten

Agentenmodell

• Ein Agent in seiner Umgebung nimmt sensorische Eingaben aus der Umgebung auf und produziert Ausgabe-Aktionen, die ihn und die Umgebung beeinflussen.

• Die Interaktion ist gewöhnlich fortlaufend und nicht-terminierend!

Umgebung: Raum in Gebäude
Sensor: Temperatur T
Aktor:  Heizung
Verhalten:
(1) Temperatur zu niedrig  ⟼ Heizung an
(2) Temperatur angenehem   ⟼ Heizung aus

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agenten und Weltumgebung

Agenten und Weltumgebung

Reaktive und Zustandsbasierte Agenten

• Reaktive und zustandsbasierte Agenten führen einen Zyklus durch:
  • Perzeption ⇒ Verabeitung ⇒ Zustandsänderung ⇒ Entscheidung ⇒ Aktion

(Links) Interaktion eines Agenten mit der Umwelt: Perzeption, Aktion (Rechts) Lernender Agent (Reinforcement Agent)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: ATG Modell

ATG Modell

Zustandsbasierter Agent

• Besteht aus: (1) Körpervariablen (2) Kontrollzustand und Verhalten

Aktivität und Zustand

• Das Verhalten eines aktivitätsbasierten Agenten ist durch einen Agentenzustand gekennzeichnet, der durch Aktivitäten verändert wird.

• Aktivitäten verarbeiten Wahrnehmungen, planen Aktionen und führen Aktionen aus, die den Steuerungs- und Datenzustand des Agenten ändern.

• Aktivitäten und Übergänge zwischen Aktivitäten werden durch einen Aktivitätsübergangsgraphen (Activity Transition Graph, ATG) dargestellt.

• Die Übergänge starten Aktivitäten in der Regel abhängig von der Auswertung von Agentendaten (Körpervariablen), die den Datenzustand des Agenten repräsentieren.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: ATG Modell

ATG Modell

(Links) Agentenverhalten, das von einem Aktivitätsübergangsgraphen vorgegeben ist, und die Interaktion mit der Umgebung, die durch Aktionen erfolgt, die in Aktivitäten ausgeführt werden (Rechts) Agentenmerkmale

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: ATG Modell

ATG Modell

• Ein Aktivitätsübergangsgraph, der mit Agentenklassen assoziiert ist, besteht aus einer Menge von Aktivitäten 𝔸 = {A₁, A₂, ..} und einer Menge von Übergängen 𝕋 = {T₁ (C₁), T₂ (C₂), ..}, die die Kanten des gerichteten Graphen darstellen.

• Die Ausführung einer Aktivität, die selbst aus einer Folge von Aktionen und Berechnungen besteht, ist mit dem Erreichen eines Unterzieles oder das Erfüllen einer Voraussetzung verknüpft, um ein bestimmtes Ziel zu erreichen, z. B. Sensordatenverarbeitung und Verteilung von Informationen.

• Normalerweise werden Agenten verwendet, um komplexe Aufgaben zu zerlegen basierend auf der Zerlegung durch MAS.

• Agenten können ihr Verhalten basierend auf Lern- und Umgebungsänderungen oder durch Ausführen einer bestimmten Unteraufgabe mit nur einer Untermenge des ursprünglichen Agentenverhaltens ändern → Dynamische ATG.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: ATG Modell

ATG Modell

• Das ATG-Verhaltensmodell ist eng mit der Interaktion von Agenten mit deren Umgebung verbunden, hier hauptsächlich durch
  • Den Austausch von Daten unter Verwendung einer Tupelraum-Datenbank;
  • Durch Migration; und durch
  • Die Weitergabe von Nachrichten zwischen Agenten mittels Signalen.
  • Replikation und Instantiierung von Agenten

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: DATG Modell

DATG Modell

• Ein ATG beschreibt das vollständige Agentenverhalten.

• Jedes Unterdiagramm und jeder Teil des ATG kann einem Unterklasseverhalten eines Agenten zugeordnet werden.

• Daher führt das Modifizieren der Menge von Aktivitäten 𝔸 und Übergängen 𝕋 des ursprünglichen ATG zu mehreren Unter- und Oberverhaltensweisen, die Algorithmen implementieren, um verschiedene unterschiedliche Ziele zu erfüllen.

• Die Rekonfiguration der Aktivitäten führt zu einer Menge von Aktivitätsmengen 𝔸^* = {𝔸_i ⊂ 𝔸, 𝔸_j ⊂ 𝔸, 𝔸_k ⊃ 𝔸, ..}, die von der ursprünglichen Menge 𝔸 abgeleitet sind, und die Modifikation oder Rekonfiguration von Übergängen 𝕋^* = {𝕋₁ ⊂ 𝕋, 𝕋₂ ⊂ 𝕋, ..} ermöglicht die dynamische ATG-Zusammensetzung (Komposition) und Agentenunterklassifizierung zur Laufzeit,

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: DATG Modell

DATG Modell

Dynamischer ATG: Transformation und Komposition

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Beispiel eines Agenten

Beispiel eines Agenten

ATG eines einfachen Umfrageagenten mit Unterklassen (master, requester, worker)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Eine Agentenklasse beschreibt ein bestimmtes Verhalten eines Agenten mittels eines ATG und einer Menge von Körpervariablen.

• Von einer Klasse können zur Laufzeit Agenten instantiiert (erzeugt) werden.

Verhalten

Eine bestimmte Agentenklasse AC_i bezieht sich auf das zuvor eingeführte ATG Modell, dass das Laufzeitverhalten und die von Agenten ausgeführten Aktion definiert.

Wahrnehmung

Ein Agent interagiert mit seiner Umgebung, indem er eine Datenübertragung unter Verwendung eines einheitlichen Tupelraums mit einer koordinierten datenbankähnlichen Schnittstelle durchführt.
Daten aus der Umgebung beeinflussen das folgende Verhalten und die Aktion eines Agenten. Daten, die an die Umgebung (z.B. die Datenbank) weitergegeben werden, beeinflussen das Verhalten anderer Agenten.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Speicher

Zustandsbasierte Agenten führen Berechnungen durch, indem sie Daten ändern. Da Agenten als autonome Datenverarbeitungseinheiten betrachtet werden können, werden sie hauptsächlich private Daten modifizieren, und ein Berechnungsergebnis, dass diese Daten verwendet, in die Umgebung übertragen.
Daher enthält jeder Agent und jede Agentenklasse eine Menge von Körpervariablen 𝕍 = {v₁:typ₁, v₂: typ₂, ..}, die durch Aktionen in Aktivitäten modifiziert und in Aktivitäten und Übergangsausdrücken gelesen werden.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Parameter

Agenten können zur Laufzeit von einer bestimmten Agentenklasse instantiiert werden, die Agenten mit gleichen anfänglichen Steuerungs- und Datenzuständen erstellt.
Um einzelne Agenten zu unterscheiden (Individuen zu erzeugen), wird eine externe sichtbare Parametermenge ℙ = {p₁: typ₁, p₂: typ₂, ..} hinzugefügt, die die Erstellung verschiedener Agenten bezüglich des Datenzustands ermöglicht. Innerhalb einer Agentenklasse werden Parameter wie Variablen behandelt.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Eine Agentenklasse AC_i ist daher zunächst definiert durch das folgende Mengentupel:

$$\begin{gathered} AC_i = \left\langle {\mathbb{A}_i,\mathbb{T}_i,\mathbb{V}_i,\mathbb{P}_i} \right\rangle \hfill \\ \mathbb{A} = \{ {a_1},{a_2},..,{a_n}\} \hfill \\ \mathbb{T} = \{ {t_{ij}} = {t_{ij}}({a_i},{a_j},cond)|{a_i}\xrightarrow{{cond}}{a_j};i,j \in \{ 1,2,..,n\} \} \hfill \\ {a_i} = \{ {i_1},{i_2},..|{i_u} \in ST\} \hfill \\ \mathbb{V} = \{ {v_1},{v_2},..,{v_m}\} \hfill \\ \mathbb{P} = \{ {p_1},{p_2},..,{p_i}\} \hfill \ \end{gathered}$$

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Multiagentensysteme

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agentenklassen

Agentenklassen

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Agenteninterkation

Agenteninterkation

Multiagentensystem interagieren miteinander, z.B. durch

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume

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

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume

Tupelräume

Ein Schnappschuss eines Tupelraumes mit Tupeln und Tupeloperationen

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume

Tupelräume

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

Direkter Nachrichtenaustausch (a), z.B. durch Signale, im Vergleich zu generativer Kommunikation (b) und virtuelle verteilte Räume (c) durch mobile Prozesse (Agenten)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume - Datenmodell

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.

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume - Operationale Semantik

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

function (t:tuple)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume - Operationale Semantik

Tupelräume - Operationale Semantik

inp

function (p:pattern, callback: function (tuple|tuple[]|null),all?:boolean)

rd

function (p:pattern, cb:function (tuple|tuple[]|null),all?:boolean)

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume - Operationale Semantik

Tupelräume - Operationale Semantik

Beispiele

out(["Sensor",1,100]); 
out(["Sensor",2,121]);
inp(["Sensor",1,_], function (t) { if (t) v=t[2]; }); 
inp(["Sensor",_,_], function (t) { if (t) n=t[1],v=t[2] });`
rd(["Sensor",_,_], function (t) { if (t) n=t[1],v=t[2] });`

Stefan Bosse - MAS - Modul C Verteiltes Rechnen mit JAM Agenten (ABC) :: Tupelräume - Operationale Semantik

Tupelräume - Operationale Semantik

try_inp, try_rd

function (0,p:pattern,callback?:function,all?:boolean) ⟼ tuple|tuple[]|null

try_inp, try_rd

`function (tmo:number,p:pattern,callback:function,all?:boolean)

.indent2[

• Teilblockierende Version von try_inp/try_rd, Wird innerhalb einer Zeit von tmo kein passendes Tupel gefunden wird die Operation ergebnislos abgebrochen. ]

• 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

function (pattern) ⟼ boolean

.indent2[

• Nicht blockierender Test eines Tupels. ]

ts (testandset)

function (pattern,function (tuple) ⟼ tuple)

.indent2[

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

rm

function (p:pattern,all?:boolean)

.indent2[

• Entfernung eines oder aller passenden Tupel. ]

Tupelräume - Operationale Semantik

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.

$$m = \left\langle {\tau ,\overrightarrow d } \right\rangle {\text{, with }}\overrightarrow d :: = d|d,\overrightarrow d {\text{ and }}d:: = v|\varepsilon |x,{\text{ }}\tau :{\text{timeout}}$$

mark

function (tmo:number,t:tuple)

.indent2[

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

Tupelräume - Operationale Semantik

alt

function (pattern [], function (tuple|tuple[]|null),all?:boolean)

.indent2[

• Gleichzeitige Mehrfachabfrage (mit inp Semantik) von einer Menge von Mustern. Das erste Tupel welches einem der Muster entspricht wird an die Rückruffunktion übergeben. Es gibt auch eine nicht- oder partiell blockierende Variante try_alt. ]

Tupelräume - Produzenten und Konsumenten

.col1[ .invert[Produzent]

this.act = {
 percept : function () {
   out(["SENSORNODE"]);
   mark(1000,["SENSOR","CLOCK",time()])
   mark(1000,["SENSOR","GPS",
              {lati:x,long:y}])
 }
}

] .col2[ .invert[Konsument]

this.act = {
 process : function () {
  if (test(["SENSORNODE"])
   inp(["SENSOR","CLOCK",_], function (t) {
    if (t) log('It is time '+t[2]);
   })
 }
}

]