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