Multiagentensysteme: Modelle, Programmierung, Plattformen

Agentenmodelle und Architekturen

Agentenbasiertes Modellieren (ABM)

Eine wichtige Eigenschaft des agentenbasierten Modellierens ist die Möglichkeit Zufälligkeit in die Modelle mit einzubeziehen (Monte Carlo Simulation)

• Viele numerische (funktionssbasierte) Ansätze erfordern das Entscheidungen im Modell deterministisch ausgeführt werden sollen (wie allg. Softwareentwurf)

• In agentenbasierten Ansätzen können Entscheidungen auf Wahrscheinlichkeiten und Zufall beruhen

Beispiel: Im Ameisenmodell ist die Bewegung der Ameisen nicht vollständig vorherbestimmt und deterministisch. Jede Ameise wird auf ihrem Weg immer wieder zufällig eine kleine Richtungsänderung vornehmen.

Verhaltensmodelle

Man unterscheidet zwei grundsätzliche Methoden der Modellierung von Agenten:

Top-down Ansatz → Strukturen bilden sich nach unten

Ein globaler Ansatz wo die Systemebene und das Verhalten des Ensembles (bekannt) modelliert und das Verhalten von Individuen und deren Wechselwirkung untersucht (unbekannt) wird.

Bottom-up Ansatz → Strukturen bilden sich nach oben

Ein lokaler Ansatz wo die Individualebene und das Verhalten einzelner Agenten (bekannt) modelliert und das Systemverhalten (Emergenz, unbekannt) untersucht wird.

Verhaltensmodelle

Beispiel Ameisen

Ein einfaches Verhaltensmodell für Ameisen in einer Kolonie könnte textuell wie folgt beschrieben werden:

Verhalten einer Ameise

1. Wenn die Ameise kein Futter trägt dann

   • überprüft sie ob an ihrem momentanen Ort Futter zu finden ist,
   • wenn Futter gefunden wurde wird es aufgenommen; wenn nicht
   • dann sucht sie in der Umgebung nach einem Pheromon und
   • geht entlang der Pheromonspur (Gradient) bis zur stärksten Quelle

2. Wenn die Ameise Futter trägt dann geht sie zurück zum Nest und hinterlässt Pheromone entlang der Spur

3. Es wird zufällig eine Richtungsabweichung ausgewählt und einen Schritt in diese Richtung gegangen (Random walk)

Verhaltensmodelle

Man unterscheidet bei ABM und ABS folgenden Entitäten:

Aktive Agenten

Agenten die durch eine Menge privater Daten, einem veränderlichen Ort, Eigenschaften, und einem Verhaltensmodell gekennzeichnet sind. Diese Agenten interagieren (kommunizieren) aktiv mit anderen Agenten und verändern die Welt (Daten)

Passive Agenten

Agenten die optional durch eine Menge privater Daten, i.A. Ortsgebundenheit, und Eigenschaften gekennzeichnet sind. Diese Agenten sind Ressourcen die nicht aktiv mit anderen Entiäten interagieren.

Verbindungen

Es gibt Verbindungen (links) zwischen den Agenten die eine Interaktion (Kommunikation) ermöglichen

Welt

Eine i.A. diskrete Welt mit Koordinaten, Eigenschaften, die mit einer Menge von Agenten besetzt ist.

Verhaltensmodelle

NetLogo Beschreibung

• NetLogo ist eine Modellierungssprache auf Systemebene und eine Simulationsumgebung

;; if not carrying food, look for it
If not carrying-food? [ look-for-food ] 
;; if carrying food turn back towards the nest
if carrying-food? [ move-towards-nest ] 
;; turn a small random amount and move forward
wander  

• NetLogo beschreibt das Verhalten eines Multiagentensystems anhand von Berechnungen und Anweisungen als ganzes:
  • Modellierung der gesamten Simulationswelt in einem Modell

NetLogo - Einführung

Prozeduren

• Die programmatische Modellierung von Agenten in NetLogo ist prozedural. Die Definition einer Prozedur oder Funktion (mit Rückgabewert) erfolgt mit dem to Schlüsselwort.

to procedure-name
  Anweisung
  Anweisung
  ..
end

NetLogo - Einführung

Die Welt und Patches

• Die Simulationswelt (zweidimensional) ist in NetLogo in patches unterteilt

• Ein Patch hat eine Koordinate (x,y) und kann eine Ressource sein (passiver Agent)

• Ein Patch besteht aus einer Visualisierung (Farbe) und optional Datenvariablen (Eigenschaften)

  • Die Datenvariablen entsprechen im Modell der Zellulären Automaten den Zellvariablen

• Patches sind nicht mobil

• Patches ermöglichen die Diskretisierung der analogen Welt

  • Vor- und Nachteil zugleich. Warum?

NetLogo - Einführung

NetLogo - Einführung

Patches

• Patches können einen Satz von Variablen besitzen die mit der patches-own Anweisung definiert werden und mit der set Anweisung verändert werden können.

• Vordefinierte Variablen (Parameter): pcolor

patches-own [
  var1
  var2
  .. ]
..
[ set var1 ε ]

NetLogo - Einführung

Anweisungen

[ set var ε ]
if cond [
  Anweisung
  Anweisung
]
ifelse cond
  Anweisung cond=True
  Anweisung cond=False

NetLogo - Einführung

Agenten

• In NetLogo werden Agenten durch Turtles implementiert

• Ein Agent ist gekennzeichnet durch seine aktuelle Patchposition, die initial gesetzt werden kann mit der Anweisung setxy x y

• Agenten werden durch die create-turtles Anweisung erzeugt. Agenten können private Variablen haben die mit der turtles-own Anweisung deklariert werden.

turtles-own [var]
create-turtles num [
  Anweisung
  Anweisung
  [ setxy xpos ypos ]
  [ set var ε ]
  .. ]

NetLogo - Einführung

Dynamische Erzeugung von Agenten

sprout num
sprout-class num 
sprout num [ statements ]
sprout-class num [ statements ]

NetLogo - Einführung

Aufgabe

1. Öffne NetLogo und das Simulationsmodell Sample Models → Biology → Ant Lines und stelle folgende Liste zusammen:

   • Arten von Agenten (Turtles), Unterteilung in passive und aktive Agenten
   • Visualisierung der Agenten (shape)
   • Globale Variablen
   • Agentenvariablen
   • Prozeduren

2. Wo werden die Patches erzeugt/verändert?

3. Wo wird die Simulationswelt erzeugt?

4. Wie werden die Agenten in der Welt bewegt?

5. Welche Sensoren verwenden die Agenten?

6. Wie kommunizieren die Agenten?

NetLogo - Einführung

Setup

• Ein Setup der Simulation besteht i.A. aus folgenden Schritten und wird am Anfang durch Aufruf einer Prozedur durchgeführt:

1. Welt löschen → clear-all
2. Agenten erzeugen und initialisieren → create-turtles
3. Simulationszähler zurücksetzen → reset-ticks

Beispiel

to setup
  clear-all
  create-turtles 100 [ setxy random-xcor random-ycor ]
  reset-ticks
end

NetLogo - Einführung

Simulationsschritt

• In jedem Simulationsschritt wird im Simulationsmodell eine Prozedur ausgeführt die die Agenten und die Welt verändert.

• Die Simulationszeit wird um den Wert eins erhöht indem die tick Anweisung ausgeführt wird.

  Beispiel

to go
  ask wolfes
    [
       if (hungry > 100)
        [ forward 10 ]
    ]
  tick
end

NetLogo - Einführung

Aktionen

• In jedem Simulationsschritt (tick) können Aktionen auf Patches und Agenten (Turtles) angewendet werden

• Die Auswahl der Agenten (oder Patches) erfolgt mit der ask Anweisung die eine Menge von Anweisungen auf die ausgewählten Menge von Agenten anwendet → Iterator

ask agentset  [
  Anweisung
  Anweisung
  .. ]

• Vordefinierte Mengen: turtles, patches, turtle num

• Alle Anweisung in der ask Anweisung wie z.B. das Verändern von Agentenvariablen werden auf den jeweiligen Agenten aus der zu iterierenden Menge angewendet!

NetLogo - Einführung

Beispiele

ask turtles [ fd 1 ]
  ;; all turtles move forward one step
ask patches [ set pcolor red ]
  ;; all patches turn red
ask turtle 4 [ rt 90 ]
  ;; only the turtle with id 4 turns right

Mobilität

• Agenten (Turtles) können auf dem Patchfeld verschoben werden. Dazu gibt es zwei Parameter: Richtung und Anzahl der Schritte (Felder)

forward num    fd num
right degree   rt degree   
left degree    lt degree

NetLogo - Einführung

Simulationsschleife

• Die Simulation wird in Schritten ausgeführt und durch die tick Anweisung wird ein Simulationszähler erhöht.

• Der Schrittzähler kann mit ticks abgefragt und mit reset-ticks zurück gesetzt werden.

to go             to move-turtles
  move-turtles      ask turtles [
  tick              right random 360
end                 forward 1
                   ]
                  end

Agenten löschen

• Ein Agent kann aus der Simulationswelt durch die die Anweisung entfernt werden.

• Ist nur im Zusammenhang mit und innerhalb einer ask Anweisung anwendbar!

Soziologische Modelle und Simulation

• Neben biologischen Modellen werden soziologische Modelle durch ABM/ABS behandelt

• Häufige soziologische Themen:

  • Soziale Netzwerk- und Gruppenbildung
  • Segregation (räumliche Gruppenbildung)
  • Migration

Soziologische Modelle und Simulation

Soziales Sakoda Interaktionsmodell

• Das ursprüngliche Sakoda-Verhaltensmodell besteht aus sozialen Interaktionen zwischen zwei Gruppen von Individuen, die sich in einem Netzwerk nach spezifischen Einstellungen hinsichtlich Anziehung, Abstoßung und Neutralität entwickeln.

• Ein Individuum bewertet seine gesellschaftliche Erwartung an allen möglichen verfügbaren Standorten (beginnend am aktuellen Standort),

  • bevorzugt Nähe zu Personen, die mit attraktiven (positiven) Einstellungen verbunden sind, und
  • vermeidet Nähe zu Personen, die mit abstoßenden (negativen) Einstellungen assoziiert sind.

Soziologische Modelle und Simulation

• Dieses Verfahren wird unter allen möglichen Individuen zufällig wiederholt;

  • Von nun an wird der Algorithmus von Sakoda wiederholt iteriert, wobei ein räumlich verteiltes soziales System zu einem organisierten räumlichen Muster entwickelt wird.

• Dies hängt jedoch vom Parametersatz des Modells, der Personendichte und der Individualisierung ab.

• Der Einfachheit halber gibt es eine zweidimensionale Gitterwelt, die aus diskreten Orten (x, y) besteht.
• Ein Agent nimmt eine Stelle des Gitters ein.
• Maximal ein Agent kann einen Ort besetzen.
• Die Agenten können sich auf dem Gitter bewegen und ihre Position ändern.

Soziologische Modelle und Simulation

• Es wird angenommen, dass es zwei Gruppen gibt, die sich auf die Klassen a und b von Individuen beziehen.

• Die soziale Interaktion ist gekennzeichnet durch unterschiedliche Einstellungen eines Individuums zwischen verschiedenen und zwischen gleichen Gruppen, die durch vier Parameter gegeben werden:

• Das Weltmodell besteht aus N Stellen x_i.
• Jeder Platz kann von keinem oder einem Agenten belegt werden, entweder von Gruppe α oder β, ausgedrückt durch die Variable x_i = {0, -1,1}
• Die gesellschaftliche Erwartung eines Agenten i am Ort x_i ist gegeben durch:

Soziologische Modelle und Simulation

• Der Parameter J_ik ist ein Maß für die soziale Entfernung (gleich eins für die Moore-Nachbarschaft mit Entfernung eins) und nimmt für längere Entfernungen ab.

• Der Parameter δ drückt die Einstellung zu einem Nachbarort aus, gegeben durch:

• Ein einzelner Agent ag_i einer Gruppe α (Klasse aus der Gruppe von Gruppen) kann seine Position ändern, indem er vom aktuellen Ort x_i an einen anderen Ort x_m wandert,
  • wenn dieser Platz nicht belegt ist (x_m = 0) und
  • wenn f_i(x_m) > f_i(x_i).

Soziologische Modelle und Simulation

Aufgabe

1. Implementiere Agenten mit dem Sakoda Verhalten

2. Die Welt soll parametrisierbar mit einer Anzahl a/b Agenten bevölkert werden

3. Der S Parametersatz soll auch parametrisierbar sein

4. Führe exemplarisch Simulationen durch. Welche Strukturen ergeben sich für die folgenden S Vektoren: (1,-1,-1,1), (1,1,1,1) (-1,1,1,-1)

Agenten und Weltumgebung

• Agenten interagieren mit der Weltumgebung (dem Environment) mittels:

  • Sensoren (Daten)
  • Aktoren (Daten)

• Sensoren und Aktoren sind über den Zyklus Wahrnehmung → (Planung →) Entscheidung → Aktion verbunden

Agenten und Weltumgebung

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 angenehm →  Heizung aus

Klassen von Verhaltensweisen

Das Verhalten von Agenten und ihre Modellierung wird maßgeblich durch diese Interaktion und den Zyklus bestimmt!

Verhaltensweisen

Reaktiv

Ein reaktives System ist eines, das eine fortlaufende Interaktion mit seiner Umgebung aufrecht erhält und auf Änderungen reagiert, die darin auftreten (rechtzeitig, damit die Antwort nützlich ist).

• Auf ein Ereignis zu reagieren ist einfach: Stimulus → Antwort
• Aber nützlicher (für UNS) ist ein zielgerichtetes Verhalten …

Proaktiv

Proaktivität ist die Schaffung und der Versuch Ziele zu erreichen; nicht nur von Ereignissen getrieben; die Initiative ergreifen.

• Chancen erkennen!

Klassen von Verhaltensweisen

Sozial

Die reale Welt ist eine Umgebung mit einem Ensemble aus Agenten: Sie werden nur erfolgreich sein Ziele zu erreichen wenn sie andere berücksichtigen.

• Einige Ziele können nur durch Interaktion mit anderen erreicht werden.

Soziale Fähigkeit in Agenten ist die Fähigkeit, mit anderen Agenten (und möglicherweise Menschen) durch Kooperation, Koordination und Verhandlung zu interagieren.

• Zumindest bedeutet es die Fähigkeit zu kommunizieren …

Soziale Fähigkeit: Kooperation

• Kooperation arbeitet als Team zusammen, um ein gemeinsames Ziel zu erreichen.

• Häufig entweder durch die Tatsache, dass kein Agent das Ziel alleine erreichen kann, oder dass die Kooperation ein besseres Ergebnis erzielt (z.B. schnelleres Ergebnis).

⇒ Emergentes Verhalten ⇒

Arten

• Zufällig, nicht beabsichtigt
• Einseitig beabsichtigt, ein Agent hilft beabsichtigt dem anderen zur Zielerfüllung
• Gegenseitig beabsichtigt, mehrere Agenten helfen sich beabsichtigt gegenseitig

Soziale Fähigkeit: Koordination

Wettbewerb

• Koordination behandelt die Abhängigkeiten zwischen Aktivitäten.

• Wenn es beispielsweise eine nicht gemeinsam teilbare Ressource gibt (geteilt aber nicht teilbar), die zwei Agenten verwenden möchten, müssen sie koordinieren.

Mutualer Ausschluss

Auflösung des Wettbewerbskonflikts durch entweder oder (EXOR) Entscheidung.

• Koordination in verteilten asynchronen Systemen ist nicht einfach.
• Invariante des mutualen Ausschlusses: Eine geteilte Ressource darf niemals von mehr als einem Agenten gleichzeitig verwendet werden!
• Sichere und robuste Gruppenkommunikation ist erforderlich

Soziale Fähigkeit: Koordination

Architekturen

Zentralisiert und hierarchisch

Es gibt ausgewiesene (oder gewählte) zentrale Koordinatoren die Entscheidungen treffen

Dezentralisiert

Es gibt eine Selbstorganisation ohne ausgewiesene zentrale Koordination

Soziale Fähigkeit: Verhandlung

• Verhandlung ist die Fähigkeit, Vereinbarungen über Angelegenheiten von einem gemeinsamen Interesse zu treffen.

• Zum Beispiel: Sie haben einen Fernseher in Ihrem Haus; Sie wollen einen Film sehen, Ihr Mitbewohner möchte Fußball schauen.

  • Ein möglicher Deal: Schau heute Fußball und morgen einen Film.
  • Mein bevorzugter Deal: Es wird immer nur ein Film geschaut (Ego als Motivation ;-)!

• Beinhaltet in der Regel Angebot und Gegenangebot mit Kompromissen der Teilnehmer.

Formales Modell von Agenten

Umgebung (Welt)

• Die Welt soll aus einer endlichen Menge von Zuständen bestehen:

• Die reale Welt ist kontinuierlich → aber jede Welt kann mit hinreichender Genauigkeit diskretisiert werden
• Weiterhin betrachten wir ohnehin hier digitale Welten
• Die Umgebung hat eine Historie und ist i.A. nicht deterministisch

Aktionen

• Jeder Agent kann eine Aktion a (Aktivität) aus einer endlichen Menge von Aktionen A ausführen:

Formales Modell von Agenten

Durchlauf

• Eine Ausführung eines Agenten mit einer iterativen Ausführung von Aktionen wird die Welt in ihrem Zustand schrittweise verändern (Durchlauf oder run):

Agenten

• Ein Agent Ag ist eine Abbildungsfunktion die jede Durchführung r ∈ R mit einem Endzustand e ∈ E der Welt auf eine Aktion a ∈ Ac abbildet:

• Agenten wählen Aktionen in Abhängigkeit vom Weltzustand aus.
• Die Welt ist undeterministisch; aber ein Agent soll sich deterministisch verhalten (Ziele erfüllen)!

Reaktive Agenten

Modell

• Das allgemeine Wahrnehmung-Aktions Modell kann in Subsysteme unterteilt werden:
  • Eine Funktion see
  • Eine Prozedur action die auf den Ergebnissen der Funktion see Aktionen auswählt

Reaktive Agenten

• Rein reaktive Agenten werden eine Aktion a nur auf dem aktuellen Zustand e(t) ∈ E basierend auswählen:

• Die Historie der Welt wird nicht in Betracht gezogen

Beispiel: Heizungsagent

Reaktive Agenten

Wahrnehmung

• Die Wahrnehmung kann mit einer Funktion see modelliert werden:

• Per ist die Menge aller Wahrnehmungen (Perzeption) die der Agent durch seine Sensoren erhält, und see bildet Weltzustände auf Perzeptionen ab.

Aktion/Ausführung

• Die Aktionen die ein Agent auswählt basieren auf der Perzeption:

Reaktive Agenten

Beispiel Heizungsagent 2.0

• Zwei Sensoren:

  1. Temperatur mit S_T={Hoch=1 , Niedrig=0}
  2. Luftfeuchtigkeit mit S_H={Hoch=1 , Niedrig=0}

• Die Perzeptions- und Aktionsfunktion lauten dann:

Weltzustand und Perzeption

• Problem: Ein Agent sieht immer nur einen Ausschnitt des Weltzustandes über seine Perzeption!

Reaktive Zustandsbasierte Agenten

Modell

• Das Wahrnehmung-Aktions Modell kann durch einen Zustandsspeicher erweitert werden und besteht dann aus:
  • Einer Wahrnehmungsfunktion see
  • Einem Zustandsspeicher state
  • Einer Zustandsübergangsfunktion next die den nächsten Zustand berechnet (aus Ergebnissen von see und state)
  • Einer Prozedur action die Aktionen nach dem aktuellen Zustand auswählt

Reaktive Zustandsbasierte Agenten

Interne Zustände

• Aktionen werden nicht direkt aus Perzeptionen abgeleitet. Stattdessen werden interne Zustände I={i₁,i₂,..} verwendet.

Zustandsübergang

• Neben der see und action Funktion gibt es eine next Funktion die die internen Zustände und die aktuellen Zustand auf interne Zustände abbildet:

Reaktive Zustandsbasierte Agenten

Verhalten

• Das Verhalten eines zustandsbasierten reaktiven Agenten ist wie folgt:

  1. Der Agent startet in einem Anfangszustand e₀

  2. Nachdem der aktuelle Weltzustand e aufgenommen wurde berechnet er p=see(e)

  3. Der nächste interne Zustand des Agenten wird bestimmt: i_n+1 := next(i_n,p)

  4. Der Agent wählt eine Aktion aus: action(next(i_n, p))

  5. Schleife nach 2.

Verhaltensäquivalenz

• Zustandsbasierte Agenten sind nicht ausdrucksstärker als Standardagenten (ohne Zustand) (Wooldridge) !?

Nützlichkeitsfunktion

• Wie soll ein Agent bewerten dass seine Aktionen sinnvoll und nützlich sind?

• Eine Nützlichkeitsfunktion u kann verwendet werden um die Aktionsauswahl und die Konvergenz des Agenten seine Ziele zu erreichen zu verbessern.

• Mögliche Nützlichkeitsfunktionen u ∈ U können Weltzuständen (zu den der Agent auch gehört) oder Durchläufen eine reelle Bewertungszahl (i.A. [0,1]) zuordnen:

• Letztere kann die Historie einbeziehen, wohingegen die erste Funktion immer nur den aktuellen Zustand bewertet.

Nützlichkeitsfunktion

Fliesenwelt ist ein Beispiel für eine dynamische Welt!

1. Ein Agent detektiert ein Loch und beginnt mit der Aktion Verschiebung einer Fliese
2. Das Loch verschwindet bevor der Agent mit seiner Tätigkeit fertig ist. Der Agent muss auf die veränderte Umgebung reagieren und neue Aktionen planen.

Nützlichkeitsfunktion

3. Es taucht während der Aktion Verschiebung einer Fliese ein weiteres Loch auf. Der Agent sollte auf die veränderte Situation reagieren indem er z.B. erst eine Fliese nach rechts schiebt (näher dran)

• Veränderte Weltumgebungen führen bestenfalls zu eine Reorganisation von Aktionen.

• Kann mit rückgekoppelten Lernen kombiniert werden, d.h. die Verbesserung der Aktionsplanung durch “Belohnung” (wenn mehr Löcher gefüllt)

• Eine mögliche Nützlichkeitsfunktion könnte das Verhältnis der aufgetauchten Löcher zu den erfolgreich während eines Durchlaufs r gefüllten in Relation stellen und das Agentenverhalten beeinflussen:

• Dieses Funktion u(r) liefert eine normalisierte Performanzmessung der Aktionen und Aktionsplanung des Agenten.

Deduktive Agenten

• Deduktion oder deduktiver Schluss: Ableitung aus Wissen und Logiken

• Dabei spielen Logik und formale Systeme eine wesentliche Rolle:

p         (Prämisse 1)
p → q     (Prämisse 2)
———     
q         (Konklusion) 

• D.h., sind p und p → q (sprich: wenn p, dann q) wahre Aussagen, so ist auch q eine wahre Aussage.

Deduktive Agenten

• Traditionell werden künstliche intelligente Systeme mit symbolischer KI umgesetzt.

• Intelligentes Verhalten entsteht bei diesem Ansatz durch:

  • Symbolische Repräsentation der Umgebung mit dem gewünschten Verhalten
  • Syntaktische Veränderung dieser symbolischen Repräsentation

• Deduktive Schlussfolgerung bedeutet: Agenten als Theorembeweiser!

• Häufig sind symbolische Repräsentationen logische Formulierungen

Sei die Menge der Sätze der klassischen Logik erster Ordnung und sei der Satz von L-Datenbanken, d. h. die Menge von Mengen von L-Formeln. Der innere Zustand eines Agenten ist dann ein Element von . Der Entscheidungsprozess eines Agenten wird durch eine Reihe von Deduktionsregeln modelliert, . Dies sind einfache Schlussfolgerungsregeln (Inferenz) für die Logik.

Deduktive Agenten

Deduktive Agenten

Deduktive Agenten sind Kognitive Systeme

• Am Anfang steht wieder die Perzeption über Sensoren und Interpretation

• Die Information des Agenten über die Welt ist in einer Datenbank enthalten → Wissensbasis

• Die Wissensbasis enthält Aussagen die entweder schon vorhanden sind oder aktuell/kürzlich aufgrund der Wahrnehmung erworben wurden und veränderlich sind (wie z.B. Abstand Roboter-Tür)

• Die Wissensbasis wird benutzt um einen Plan auszuwählen → Planung

• Schließlich werden nach der Planung geeignete Aktionen ausgeführt

Deduktive Agenten

• Es gibt bei der Implementierung eines solchen Agenten folgende Probleme:

Transduktion

Das Problem, die reale Welt in eine genaue, adäquate symbolische Beschreibung der Welt zu übersetzen, damit diese Beschreibung für den Agenten verwendbar und nützlich ist.

Repräsentation/Schlussfolgerung

Das Problem, Informationen symbolisch darzustellen und Agenten dazu zu bringen, damit zu manipulieren / zu argumentieren, damit die Ergebnisse nützlich sind.

• Das Transduktionsproblem beschäftigt sich im wesentlichen mit Vision, Spracherkennung, Lernen, usw.

• Das Repräsentationsproblem behandelt Wissensrepräsentation (Ontologien!), Automatisches Schlussfolgern, Automatisches Planen usw.

Deduktive Agenten

• Das Agentenmodell erweitert sich durch die Datenbank zu:

• Die next Funktion verändert jetzt die Wissensdatenbank durch Perzeption!

• Wenn es eine Formel Do(α) für Aktionen α ∈ Ac mittels einer Deduktionsregel driekt aus der Datenbank abgeleitet werden kann, dann wähle diese Aktion als beste aus

• Wenn das nicht möglich ist (keine Aktion gefunden) und wenn es eine Formel ¬Do(α) gibt die sich derzeit nicht aus der Datenbank ableiten lässt (d.h. es ist nicht verboten es zu tun), dann wähle diese Aktion aus.

Deduktive Agenten

Deduktive Agenten

Beispiel: Staubsaugeragent

Deduktive Agenten

• Es gibt folgende Bereichsprädikate (Attribute):

In(x, y)   → Agent ist bei (x, y),
Dirt(x, y) → Dreck bei (x, y), 
Facing (d) → Ausrichtung des Agenten

• Es gibt folgende Aktionen: A={forwärts,saugen,drehen}

• Nun werden alte Informationen der Datenbank old(Δ) identifiziert und mittels einer new Funktion durch die next Funktion aktualisiert:

Deduktive Agenten

• Regeln in der Wissensdatenbank (Auswahl):

• Problem: Wenn sich zwischen zwei Zeitpunkten t₁ und t₂ die Welt ändert und eine bei t₁ ausgewählte Aktion nicht mehr aktuell und optimal ist!

• Agenten die strikt auf Logiken basieren sind nicht besonders performant und optimal (bzw. können völlig versagen)

Temporallogik

Agentenorientiertes Programmieren: AGENT0

• In AGENT0 (eine Programmiersprache) wird eine Agent beschrieben durch:

  • Fähigkeiten (Capabilities, Aktionen)
  • Eine Menge von Wissen über ihre Umwelt (Beliefs)
  • Eine Menge initialer Verpflichtungen und Bindungen (Commitments)
  • Eine Menge Verpflichtungsregeln (Commitment Rules)
  • Nachrichtenaustausch

• Die Schlüsselkomponente, die bestimmt, wie der Agent handelt, ist der Commitment-Regelsatz.

  • Jede Commitment-Regel enthält eine Nachrichtenbedingung, eine mentale Bedingung und eine Aktion.
  • Die Nachrichtenbedingung wird mit den Nachrichten abgeglichen, die der Agent empfangen hat.
  • Der mentale Zustand wird mit den Überzeugungen des Agenten verglichen. Wenn die Regel ausgelöst wird, wird der Agent an die Aktion gebunden.

Agentenorientiertes Programmieren: AGENT0

Eigenschaften

• Agent0 ist eine einfache Multiagenten Programmiersprache mit einer dazugehörigen Agentenarchitektur und einem integrierten Kommunikationsmodell zwischen Agenten

• Die Agentenumgebung ist verteilt und partitioniert.

• Jeder Agent verfügt über einen lokalen Nachrichtenpuffer und eine jeweils andere lokale Umgebung.

• Agenten arbeiten synchron - ihre Wahrnehmungs- und Aktions-Zyklen sind synchronisiert. Zeit ist nur die Zyklusnummer bestimmt.

• Jeder Agent kann nur Nachrichten sehen, die von anderen Agenten im vorherigen Zyklus an ihn gesendet wurden.

Agentenorientiertes Programmieren: AGENT0

Aktionen und Nachrichten

• Aktionen können privat/intern oder kommunikativ sein → Nachrichten

• Nachrichtentypen:

  • Anfragen (REQUEST, eine Aktion zukünftig durchzuführen)
  • Abbruch von Anfragen (UNREQUEST)
  • Informativ (INFORM, Wissensübertragung)

• Die Anfragen verändern i.A. die Commitments (Ziele) des Agenten,

• Die informativen Nachrichten verändern das Wissen (Beliefs)

• Für jede Kommunikationsaktion muss der empfangende Agent angegeben werden.

• Die REQUEST-Nachricht kann sich auf eine der sechs Agentenaktionen beziehen (folgend)

Agentenorientiertes Programmieren: AGENT0

Regeln für Zusagen (Commitments)

• Zusagen werden als Paare (agent, action) gehalten, wobei die Zusage an Agent agent gebunden ist.

• Es gibt eine Reihe von Regeln der Form:

COMMIT (Nachrichtenmuster, Mentalcond, Agent, Aktion)

• Die Aktion kann eine der sechs zulässigen Aktionsformen haben oder eine Folge davon sein [a]:

DO(time,privateaction)
INFORM(time,agent,fact)
REQUEST(time,agent,action)
UNREQUEST(time,agent,action) - removes commitment
REFRAIN(action) - will not enter a commitment to action
IF mentalcondition THEN action

Agentenorientiertes Programmieren: AGENT0

COMMIT( (Ag, REQUEST(Act)),
        (_,condition(Ag),
        Ag,
        Act)

Agentenorientiertes Programmieren: AGENT0

COMMIT(
  ( agent, REQUEST, DO(time, action)
  ), ;;; msg condition
  ( B,
    [now, Friend agent] AND
     CAN(se1f , action) AND
     NOT [time, CMT(se1f , anyaction)]
  ), ;;; mental condition self,
  DO(time, action) )

Agentenorientiertes Programmieren: AGENT0

Agentenorientiertes Programmieren: AGENT0 Zyklus

See Funktion

• Testet jede eingehende Nachricht M gegen jede commitment Regel [a]

COMMIT(messagepattern,mentalcond,agent,action)

Nachrichten erzeugen ein Commitment (agent,action)

wenn

• M ist in messagepattern enthalten, und
• mentalcond ist momentan wahr, und
• (unter Benutzung der Capabilityfakten wenn erforderlich)
• der Agent nimmt momentan an er ist fähig action auszuführen, und
• der Agent ist nicht verpflichtet (REFRAIN) die Aktion zu unterlassen.

oder

• action ist in der Form REFRAIN(act), und
• der Agent ist momentan nicht für act verpflichtet.

Agentenorientiertes Programmieren: AGENT0 Zyklus

Revision

Algorithm 1.

Agentenorientiertes Programmieren: AGENT0 Zyklus

Action Funktion

• Durchsucht eine Reihe von Zusagen mit einer Aktion für die aktuellen Zykluszeit

Algorithm 2.

Agentenorientiertes Programmieren: AGENT0 Zyklus

Das konzeptuale Agentenmodell

Ein Agent wird durch drei interagierende Kontroll- und Wissensebenen definiert:

• Eine verhaltensbasierte Ebene, die Reaktivität und Verfahrenswissen für Routineaufgaben enthält.

• Eine lokale Planungsebene, die die Möglichkeit bietet, über Mittel und Ziele nachzudenken, um lokale Aufgaben zu erfüllen und zielgerichtetes Verhalten zu erzeugen.

• Eine kooperative Planungsebene, die es Agenten ermöglicht, über andere Agenten zu schlussfolgern, und die koordinierte Aktion mit anderen Agenten unterstützt.

Das konzeptuale Agentenmodell

Das konzeptuale Agentenmodell

Mentale Kategorien

Der mentale Zustand eines Agenten setzt sich aus verschiedenen Komponenten zusammen:

• Die aktuelle Wahrnehmung des Agenten.

• Eine Reihe von Überzeugungen, die den Informationszustand beschreiben.

• Eine Reihe von Situationen, die relevante strukturierte Teile der Überzeugungen des Agenten beschreiben.

• Eine Reihe von (kontextunabhängigen) Zielen, die der Agent möglicherweise hat.

Das konzeptuale Agentenmodell

• Eine Reihe von Optionen, die den Motivationszustand (motivational state) des Agenten darstellen.

  • Basierend auf der aktuellen Situation wird eine Reihe von kontextabhängigen Optionen aus der Reihe der möglichen Ziele ausgewählt.
  • Daher sind Optionen Ziele, die der Agent unter bestimmten Umgebungsbedingungen verfolgen kann

• Eine Reihe von Absichten, die den Überlegungszustand (deliberative state) des Agenten definieren, d.h. die Optionen, mit denen der Agent sich selbst verändert hat, und die Definition der nächsten Aktion, die der Agent ausführen wird.

• Eine Reihe von operativen Primitiven, die den Motivationszustand aller Agenten mit ihrem Überlegungszustand verbinden.

Das konzeptuale Agentenmodell

Funktionen

Annahmenbildung und Annahmenprüfung

erklären die Beziehung zwischen den Überzeugungen eines Agenten und seiner aktuellen Wahrnehmung. Sie beschäftigen sich mit der Frage, wie Wahrnehmung in Überzeugungen umgewandelt wird (Annahmenbildung) und wie sich bestehende Überzeugungen auf der Grundlage von Wahrnehmung ändern (Annahmenrevision).

Situationserkennung

extrahiert (strukturierte) Situationen aus den (unstrukturierten) Überzeugungen eines Agenten.

Zielaktivierung

beschreibt, welche der möglichen Ziele eines Agenten in einer Reihe von Situationen derzeit Optionen sind.

Das konzeptuale Agentenmodell

Zielplanung

ordnet die aktuellen Ziele des Agenten operativen Grundelementen zu, um sie zu erreichen, d.h. lokale Pläne oder Verhandlungsprotokolle und gemeinsamen Pläne. Planen bedeutet zu entscheiden, was zu tun ist.

Ablaufplanung

ist der Prozess des Zusammenführens von Teilplänen für verschiedene Ziele zu einem Ausführungsmodul, bei dem Kompatibilitäten und (z.B. zeitliche und vorrangige) Einschränkungen zwischen verschiedenen Teilplänen berücksichtigt werden. Ablaufplanung (Scheduling) bedeutet also, zu entscheiden, wann was zu tun ist.

Ausführung

ist für die korrekte und fristgerechte Umsetzung der in der Planungs- und Terminierungsphase festgelegten Verpflichtungen verantwortlich.

Belief-Desire-Intentions Architektur

• Die BDI Architektur implementiert Praktische und Prozedurale Schlussfolgerungsagenten

Belief-Desire-Intentions Architektur

Die Belief, Desire, und Intentionsdatenbanken werden über vier Funktionen miteinander im Interpreter verknüpft: Belief Revision Function BRF, Filter, Option Generation Function, und die Action Selection Function

Belief-Desire-Intentions Architektur

BDI Kontrollschleife

• Der Agent empfängt Ereignisse, die entweder

  • extern (aus der Umgebung, aus perzeptuellen Daten)
  • intern generiert sind

• Er versucht, Ereignisse zu behandeln, indem nach Plänen gesucht wird, die übereinstimmen

• Die Menge von Plänen, die dem Ereignis entsprechen, sind Optionen / Wünsche

• Wählt einen Plan aus um seine Absichten (Wünsche) zu erfüllen: wird dem dann verpflichtet - eine Absicht

• Wenn ein Plan ausgeführt wird, können neue Ereignisse generiert werden, die eine Behandlung erfordern

Belief-Desire-Intentions Architektur

Beliefs

• Überzeugungen stellen Informationen dar, die der Agent über seine Umgebung hat

• Sie sind symbolisch dargestellt

  • Logik erster Ordnung

Plans

• Im Vorfeld von den Entwicklern offline kodiert

• Gibt dem Agenten Informationen darüber,

  • wie er auf Ereignisse reagiert
  • wie er Ziele erreicht

• Planstruktur: triggering_event : context <- body

  • Ereignis (trigger_event)
  • Kontext (context)
  • Körper (Implementierung body)

Belief-Desire-Intentions Architektur

• Bedeutung: Wenn das trigger_event gesehen wird, und geglaubt wird, dass der context wahr ist, dann kann der body ausgeführt werden!

Ereignis/Triggerbedingung

Ist ein Ereignis, mit dem der Plan umgehen kann

Kontext

Definiert die Bedingungen, unter denen der Plan verwendet werden kann

Körper

Definiert die Aktionen, die ausgeführt werden sollen, wenn der Plan ausgewählt wird

Ereignisse

+!P : Neues Ziel P erworben → “erreiche P”

-­!P : Ziel P verworfen

+B : Neue Annahme B hinzufügen

-­B : Annahme B verwerfen

Belief-Desire-Intentions Architektur

BDI Kontrollschleife

1. B ← B0;/* B0 are initial beliefs */ 
2. I ← I0;/* I0 are initial intentions */ 
3. while true do
4.   get next percept ρ via sensors; 
5.   B ← brf (B,ρ);
6.   D ← options(B, I);
7.   I ← filter(B,D, I);
8.   π ← plan(B, I , Ac); /* Ac is the set of actions */
9.   while not (empty(π) or succeeded(I , B) or impossible(I , B)) do 
10.    α ← first element of π; 
11.    execute(α); 
12.    π ← tail of π; 
13.    observe environment to get next percept ρ; 
14.    B ← brf (B, ρ); 
15.    if reconsider(I , B) then 
16.      D ← options(B, I); 
17.      I ← filter(B, D, I); 
18.    end-if 
19.    if not sound(π , I , B) then 
20.      π ← plan(B, I , Ac) 
21.    end-if 
22.   end-while 
23. end-while

Belief-Desire-Intentions Architektur : AgentSpeak

• AgentSpeak ist eine BDI-basierte Programmiersprache für den Entwurf rationaler Agenten mit logischen Formeln

Beispiel: Hello World Agent

/* Initial beliefs and rules */ 
/* Initial goals */ 
!start.
/* Plans */ 
+!start : true <- .print("hello world.").

Beispiel: Faktorisierungsagent

/* Initial belief */
fact(0,1). 
/* Additional belief: if x<5 then add new belief */
+fact(X,Y) : X < 5 <- +fact(X+1, (X+1)*Y).
/* If x==5 then print result */
+fact(X,Y) : X == 5 <- .print("fact 5 == ", Y).

Belief-Desire-Intentions Architektur : AgentSpeak

Beispiel: Faktorisierungsagent 2

/* Initial and single goal */
!print_fact(5).
/* If this is the goal, first compute fact, then print it */
+!print_fact(N) <- !fact(N,F);
  .print("Factorial of ", N, " is ", F).
/* How to compute factorial */
+!fact(N,1) : N == 0.
+!fact(N,F) : N > 0 <- !fact(N-1,F1); F = F1 * N.

Kommunikation in AgentSpeak

• Z.B. gibt es zwei Agenten: Der eine weiß wie man die Faktorisierung berechnet, der andere nicht.

• Der Experte wird vom Idioten Anfragen empfangen und wird darauf antworten → Client-Server Architektur

Belief-Desire-Intentions Architektur : AgentSpeak

.send(rcvr, type, content)
.broadcast(type,content)

• Mit der .send Operation wird eine Nachricht an den Agenten rcvr mit dem Nachrichtentyp type und dem Inhalt content gesendet.

• Der Nachrichtentyp type ist dabei ein Typ aus der Liste:

type ∈ {tell,untell,achieve,unachieve,
               askOne,askAll,askHow, tellHow,untellHow}

- tell/untell: Hinzufügen/Entfernen von Annahmen
- achieve/unachieve: Hinzufügen/Entfernen von zu erreichenden Zielen
- askOne,askIf: Ziel testen

.send(obi_wan, askOne, ?father(luke), Answer)    
.send(obi_wan, askIf, ?father(luke))    

Belief-Desire-Intentions Architektur : AgentSpeak

Beispiel: Der Idiot

/* Initial goals */ 
!start.
/* Plans */
+!start : 
  true <- .print("starting.."); 
    !query_factorial(2); 
    !query_factorial(4); 
    !query_factorial(6); 
    !query_factorial(10).
  
+!query_factorial(X) : 
  true <- .send(expert, tell, giveme(X)).
  
+fact_result(X,Y) : true <- 
  .print("factorial ", X, " is ", Y, " thank you expert").

Belief-Desire-Intentions Architektur : AgentSpeak

Beispiel: Der Experte

+!giveme(X)[source(A)]:
  true <- !fact(X,Y);
          .send(A,tell,fact_result(X,y);
          .print("Factorial of ", X, " is ", Y).
  
+!fact(X,1) : X == 0.
  
+!fact(X,Y) : X > 0
    <- !fact(X-1,Y1);
    Y = Y1 * X.

Hybride Architekturen

Die zwei Architekturen symbolische Schlussfolgerungsagenten und reaktive Agenten wurden historisch zu hybriden Architekturen fusioniert:

• 1956–present: Symbolic Reasoning Agents

  • Its purest expression, proposes that agents use explicit logical reasoning in order to decide what to do.

• 1985–present: Reactive Agents

  • Problems with symbolic reasoning led to a reaction against this—led to the reactive agents movement, 1985–present.

• 1990-present: Hybrid Agents

  • Hybrid architectures attempt to combine the best of symbolic and reactive architectures.