Multiagentensysteme: Modelle, Programmierung, Plattformen

Einführung in die Agentenwelt

Herausforderungen

Bei der Entwicklung von modernen Informatiksystemen gibt es verschiedene Herausforderungen:

• Ubiquität → 1. Nichtgebundensein an einen Standort 2. Allgegenwart

• Pervasivität → Durchdringung der Informatik in Dinge und Geräte

• Vernetzung von Geräten und Programmen

• Verteiltheit und Parallelisierung von Programmen

• Intelligenz und Lernen

• Autonomie → Ohne zentrale Instanzen und Steuerung

• Robustheit → 1. Die Welt ändert sich 2. Die Welt verhält sich unsicher

• Adaptivität → Die Welt hat sich verändert

• Delegation von Aufgaben und Hierarchien

• Menschen-Maschine Schnittstelle

Software im Wandel

• Die drei Paradigmen der Programmierung: Befehlsorientiert → Funktionsorientiert → Objektorientiert
• Zukünftige Softwareentwicklung → Agentenbasiert?

Vergleich Traditionelle vs. Multiagentensysteme

Endliche Zustandsautomaten

• Das Gegenteil von Agenten?

• Ein endlicher Zustandsautomat (EZA/englisch FSM) verarbeit Eingangsdaten (Variablen x) und gibt Ergebnisse y in Abhängigkeit seines Zustandes σ ∈ Σ aus

• Die Menge der Zustände Σ ist von Beginn an festgelegt und konstant!

• Keine Adaptivität, keine Rekonfiguration!

• Einfachstes Modell einer Berechnung (im Sinne der Informatik)

• Folgendes Beispiel zeigt einen EZA der eine Zahl auf Teilbarkeit durch 3 unteruschen soll

• Dabei wird die Zahl im binären Zahlensystem Ziffer für Ziffer links nach rechts in den Automaten gegeben

• Dieser ändert bei jeder neuen Eingabe (Sensor) seinen Zustand σ ∈ Σ={0,1,2}

Endliche Zustandsautomaten

Zelluläre Automaten

• Die Ursuppe für Agenten?

• Zelluläre Automaten besitzen diskrete Zustände und ändern ihren Zustand nur zu diskreten Zeitpunkten

Zelluläre Automaten

• Es gibt immerhin schon Nachbarschaftskommunikation (Datenaustausch) zwischen Knoten des Netzwerks

• Aber: Ein Automat ist noch ein (nicht adaptiver) endlicher Zustandsautomat → ZA = Lokal verbundende EZA!

• Auch die Netzwerkkonfiguration ist statisch - entspricht nicht natürlichen Systemen

• Nachbarschaftsrelationen können durch einen Radius charakterisiert werden:

  • Radius 1: Nur unmittelbare Nachbarn → von-Neuman Nachbarschaft
  • Radius ≤ 2: kurzreichweitige Verbindungen (einfache Systeme)
  • Radius > 2: langreichweitige verbindungen (komplexe Interaktion und Dynamik)

• Kommunikation kann als Austausch von Signalen zwischen einzelnen Zellen verstanden werden

• Zelluläre Automaten besitzen räumliche und zeitliche Dynamik

Zelluläre Automaten

• Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

Zelluläre Automaten

• Eine Zelle besitzt eine endliche (kleine) Menge von Zuständen σ = { s₁,..,s_n}.

• Eine Berechnung mit Eingabe- und internen Daten (Perzeption und innerer Zustand) führt i.A. zu einer Änderung des Zustandes der Zelle → es gibt einen Zustandsübergang

• Übergangsregeln Φ können aus einfachen arithmetischen Operationen (Funktionen) bestehen, und beziehen die Zellen aus der Nachbarschaft N mit ein (durch Kommunikation):

Zelluläre Automaten

• Die Nachbarschaftskonnektivität und die Anzahl der Zustände je Zelle bestimmen die Anzahl der möglichen lokalen Regeln die zu einem Zustandsübergang in der Nachbarschaftsgruppe führen → wird sehr schnell sehr groß!!

Zelluläre Automaten

Beispiele für Dynamik und Emergenz

Zelluläre Automaten

var world = new CAWorld({
  width: 96,height: 64, cellSize: 6
});
world.palette = [
  '255, 255, 255, 1', '68, 36, 52, 1'
];
world.registerCellType('wall', {
    getColor: function () {
        return this.open ? 0 : 1;
    },
    process: function (neighbors) {
        var surrounding = this.countSurroundingCellsWithValue(neighbors, 'wasOpen');
        this.open = (this.wasOpen && surrounding >= 4) || surrounding >= 6;
    },
    reset: function () {
        this.wasOpen = this.open;
    }
}, function () { /* init cells */ this.open = Math.random() > 0.40; });
world.initialize([ { name: 'wall', distribution: 100 } ]);

Agenten

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

Merkmale

• Fähigkeit zu eigenständiger Aktivität (Nicht nutzeraktiviert)

• Autonomes, “selbstbestimmtes” Verhalten (Nicht durch zentrale Instanz gesteuert)

• Fähigkeit zum selbstständigen Schlussfolgern (Umgang mit unsicheren Wissen)

• Flexibles und rationales Verhalten (Adaptivität an veränderliche Weltbedingungen)

• Fähigkeit zu Kommunikation und Interaktion (Synchronisation)

• Kooperatives oder konkurrierendes Verhalten (Lösung von Wettbewerbskonflikten)

• Fähigkeit zur ziel- und aufgabenorientierten Koordination (Kooperation)

Agenten

• Man unterscheidet zwischen realen und virtuellen Welten;
• Agenten können natürliche (reale) Welten abbilden oder in realen Welten agieren

Multiagentensysteme - Entwurf

Entwurf von Agenten

• Wie konstruiert man Agenten,

  • die unabhängig und autonom von Nutzeren und Systemadminstratoren agieren,

  • um die an sie delegierten Aufgaben zu erledigen?

Entwurf von Gesellschaften

• Wie konstruiert man Agenten,

  • die mit anderen Agenten interagieren und sich austauschen,

  • um ihre Aufgaben mit dem Ziel einer globalen Aufgabe zu erfüllen,

  • auch wenn manche dieser Agenten gegensätzliche Interessen haben und ihre eigenen (konkurrierenden) Ziele verfolgen?

Multiagentensysteme - Entwurf

Multiagentensysteme - Taxonomie

Reaktiver Agent

Ein Agent der seine Umgebung wahrnimmt und zeitnah darauf reagiert

Deliberativer Agent

Ein Agent mit explizit dargestelltem, symbolischen Weltmodell mit dem Entscheidungen über symbolische Argumentation getroffen werden

Interagierende Agenten

Multiagentensysteme mit kommunizierenden Agenten

Multiagentensysteme - Paradigmen und Repräsentation

Erweiterung des Paradigmas der intelligenten Systeme

Individuelle Intelligenz

• Ist die Umsetzung von Fähigkeiten wie z.B. Planen, Lernen, Schlussfolgern

Sozialfähigkeit

• Welche gemeinsame Sprache können Agenten nutzen, um ihren Wissensstand (Daten) und ihre Absichten mitzuteilen?
• Ontologien: Wie muss die Welt (digital, real, virtuell) informatorisch repräsentiert werden, damit sie von Agenten “verstanden” wird?
• Wie erkennen Agenten, dass ihr Wissen, ihre Ziele oder ihre Aktionen mit denen anderer Agenten stimmig ist?
• Wie erzielen und verhandeln sie Vereinbarungen oder Absprachen?
• Wie koordinieren sie ihre Aktivitäten, um gemeinsam (globale) Ziele zu erreichen?
• Wie entsteht Kooperation für globale Ziele in Gesellschaften “eigennütziger” Agenten?

Multiagentensysteme - Emergenz

Emergenz ist eine wichtige Eigenschaft in Ensembles von Systemen wo individuelle lokale Aktionen zu einem globalen zielgerichteten Verhalten führen sollen (Schwarmverhalten)

• Man spricht von Emergenz wenn es ein Attribut (Eigenschaft/Ziel) auf Systemebene gibt was nicht auf individueller Ebene definiert wurde/existiert!

• Komplexe kommunizierende Systeme sind meistens durch emergente Phänomene gekennzeichnet.

• Aber: Ist das emmergente Verhalten gewünscht und mit den Systemzielen (Aufgaben) vereinbar???

Multiagentensysteme - Intelligenz

Verteilte Künstliche Intelligenz

Verteilte Künstliche Intelligenz befasst sich mit der Untersuchung, Konstruktion und Anwendung von Multi-Agenten Systemen, in denen mehrere interagierende, intelligente Agenten verschiedene Ziele verfolgen oder eine Reihe von Aufgaben bearbeiten [Biundo-Stephan 2001]

• Intelligente Agenten sind
  • autonome Software- oder
  • Hardwareeinheiten;
  • die ggf. mobil sind (zwischen verschiedenen Hostplattformen migrieren können) sind,
  • die flexibel (adaptiv in ihrem Verhalten) basierend auf gelernten Wissen,
  • robust (Fehlererkennung, Umgang mit unsicheren Wissen) sind,
  • und mit anderen Agenten sowie ihren Nutzern interagieren.

Multiagentensysteme - Eignung

• Multi-Agenten Systeme sind geeignet für Anwendungen

  • in großen/ausgedehnten,

  • verteilten,

  • heterogenen Umgebungen (bezgl. Plattformen, Betriebssystemen, Programmiersprachen, Netzwerktopologien, Performanz..), z.B., im Internet, in Cloud Umgebungen oder Sensornetzwerken,

  • die ein hohes Maß an Interaktion erfordern,

  • die technisch unzuverlässig und störanfällig sind,

  • die sich in ihrer Konfiguration ändern können (d.h. die Welt und ihre Ontologie ändern sich)

  • die einen Divide-and-Conquer Ansatz erlauben, d.h. die Zerlegung eines großen Problems, großer Datenmengen, und großer Algorithmen auf immer kleinere Einheiten.

Multiagentensysteme - Wofür?

Sichten auf Multi-Agenten Systeme

• Agenten als Softwareentwicklungsparadigma (agentenorientierte Programmierung)

  • Moderne Softwarearchitekturen setzen sich aus vielen, dynamisch interagierenden Komponenten zusammen

  • Weiterentwicklung der Konzepte der Modularisierung und Objektorientierung

• Agenten als Mittel zur Modellierung und Simulation natürlicher/menschlicher Gesellschaften (Soziologie)

  • Erforschung gesellschaftlicher Entwicklungen in Vergangenheit und Zukunft

  • Verhalten von Menschenmengen (Notfälle, Flucht, ..)

Multi-Agenten Systeme - Wofür?

• Agenten als Mittel zur Modellierung von Netzwerken und verteilten Systemen

• Agenten als Mittel zur Modellierung von parallelen Systemen und Konkurrenz

• Mobile Agenten als Verteilungsparadigma und verteiltes Datenverarbeitungsmodell (Sensornetzwerke, Internet der Dinge, Cloud Computing, …)

Multiagentensysteme - Dafür!

Multiagentensysteme - Dafür!

Multiagentensysteme - Klassifizierung

Multiagentensysteme - Zusammenfassung

Netzwerke

Klassifikation von Netzwerken

Klassifikation nach den Observablen und dem elektrischen Leistungsbedarf → Datenverarbeitung in Netzwerken und Sensornetzwerken

Netzwerke

Sensornetzwerke

Multi-Agenten Systeme in Sensornetzwerken

Multi-Agenten Systeme können für

• autonome,

• zuverlässige,

• selbstorganisierende, und

• adaptive Datenverarbeitung und Kommunikation in Netzwerken genutzt werden.

Multi-Agenten Systeme mit reaktiven mobilen Agenten können für die Sensorverarbeitung in Sensornetzwerken eingesetzt werden, die aus Sensorknoten bestehen die unzuverlässig arbeiten (z.B. wegen Energiemangel) und unzuverl. verbunden sind.

Multi-Agenten Systeme in Sensornetzwerken

Funktionalen Schichten in Sensornetzwerken

• Vertikale Schichten

Sensing

Akquisition and Vorverarbeitung von Sensordaten sowie Sensordatenfusion

Aggregation

Verteilung und Sammlung von Sensordaten, Informationsgewinnung, Fusion

Applikation

Analyse, Speicherung, Visualisierung, Mensch-Interaktion, Datenbanken, Server

• Horizontale Schichten

Multi-Agenten Systeme in Sensornetzwerken

Funktionale Schichten in Sensornetzwerken stellen Aufgaben, Ziele, und Kooperation von Agenten dar! Mobile Agenten können alle Schichten abdecken!