Multiagentensysteme: Modelle, Programmierung, Plattformen

PD Stefan Bosse
Universität Bremen, FB Mathematik & Informatik
SS 2020
Version 2020-05-20

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.

figtopdownbotup

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.

Definition 1.

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

fignetlogoWorld


Abb. 1. Simulationswelt und kartesische Koordinaten

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

Definition 2.

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

NetLogo - Einführung

Anweisungen

Definition 3.

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

Definition 4.

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

NetLogo - Einführung

Dynamische Erzeugung von Agenten

Definition 5. (Erzeugung von neuen Agenten auf dem aktuellen Patch)

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

Definition 6.

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)

Definition 7.

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: