Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt ::

Einführung in die Agentenwelt

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Herausforderungen

Herausforderungen

Bei der Entwicklung von modernen Informatiksystemen gibt es verschiedene Herausforderungen:

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Software im Wandel

Software im Wandel

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

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Vergleich Traditionelle vs. Multiagentensysteme

Vergleich Traditionelle vs. Multiagentensysteme

Traditionelle Systeme

• Hierarchien großer Programme
• Sequenzielle Ausführung von Operationen
• Anweisungen von oben nach unten
• Zentrale Entscheidung
• Datengesteuert
• Vorhersagbarkeit
• Stabilität
• Verringerung der Komplexität
• Vollständige Kontrolle

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Vergleich Traditionelle vs. Multiagentensysteme

Vergleich Traditionelle vs. Multiagentensysteme

Multiagentensysteme

• Große Netzwerke kleiner Agenten
• Parallele Ausführung von Operationen
• Verhandlungen
• Verteilte Entscheidungen
• Wissensgesteuert
• Selbstorganisation
• Evolution
• Behandlung von Komplexität
• Fähigkeit zum Wachstum

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Vergleich Traditionelle vs. Multiagentensysteme

Vergleich Traditionelle vs. Multiagentensysteme

Eigenschaften von Agenten

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Endliche Zustandsautomaten

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}

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Endliche Zustandsautomaten

Endliche Zustandsautomaten

Beispiel eines EZA

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

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 als Netzwerk aus einfachen kommunizierenden Berechnungseinheiten

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

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

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

Zelluläre Automaten

• Nachbarschaftsrelationen sind auch bei Agenten wichtige Eigenschaft

Hoekstra,SCSCA,2010 Verschiedene Nachbarschaftsrelationen in ZA

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

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):

$$\sigma_{i,j}(t + 1) = \Phi(\sigma_{k,l}(t) | \sigma_{k,l}(t) \in N )$$

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

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ß!!

Anzahl der Regeln eines ZA in Abhängigkeit der Anzahl der Zustände pro Zelle und des verbinsungsgrades der Zellen

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

Zelluläre Automaten

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Zelluläre Automaten

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 } ]);

Beispiel einer ZA Weltbeschreibung

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Agenten

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)

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Agenten

Agenten

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

Beziehung realer natürlicher Welt mit Lebewesen zu virtueller Welt mit Agenten

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Entwurf

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?

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Entwurf

Multiagentensysteme - Entwurf

Entwurf von Intelligenten Agenten: Eine Roadmap [A] und AAPL als Basis

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Taxonomie

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

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Paradigmen und Repräsentation

Multiagentensysteme - Paradigmen und Repräsentation

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Emergenz

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???

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Intelligenz

Multiagentensysteme - Intelligenz

Verteilte Künstliche Intelligenz

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Eignung

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.

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Wofür?

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, ..)

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multi-Agenten Systeme - Wofür?

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, ...)

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Dafür!

Multiagentensysteme - Dafür!

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Dafür!

Multiagentensysteme - Dafür!

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Dafür!

Multiagentensysteme - Dafür!

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Dafür!

Multiagentensysteme - Dafür!

Physikalische Welt

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Klassifizierung

Multiagentensysteme - Klassifizierung

Klassifizierung und verschiedene Typen der Anwendung von MAS

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Zusammenfassung

Multiagentensysteme - Zusammenfassung

Agent

Definitionen

• Jeder im Auftrag oder Interesse eines anderen Tätige [Meyer 1994]
• Ein Software-Agent ist ein Programm, das seine Umgebung wahrnimmt und in dieser Umgebung agiert [Schneeberger 2001]

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Zusammenfassung

Eigenschaften

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multiagentensysteme - Zusammenfassung

Multiagentensysteme

• Systeme aus einer Vielzahl von gleichen oder verschiedenen Agenten
• Interagierende, intelligente Agenten die verschiedene Ziele verfolgen oder eine Reihe von Aufgaben bearbeiten.

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Netzwerke

Netzwerke

Klassifikation von Netzwerken

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

Relevante Observablen von Netzwerkknoten:

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Netzwerke

Netzwerke

Sensornetzwerke

Sugihara, 2008 Beispiele von Sensornetzwerken nach Anzahl der Knoten / Knoten Klasse

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multi-Agenten Systeme in Sensornetzwerken

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.

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multi-Agenten Systeme in Sensornetzwerken

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

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multi-Agenten Systeme in Sensornetzwerken

Funktionalen Schichten in Sensornetzwerken

• Horizontale Schichten

• Datenverarbeitung

• Kommunikation
• Speicher
• Koordination
• Management
• Sicherheit

Stefan Bosse - MAS - Modul A Einführung in die Agentenwelt :: Multi-Agenten Systeme in Sensornetzwerken

Multi-Agenten Systeme in Sensornetzwerken

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