Agentensysteme (WP&nbps;43)

Semester Sommersemester 23 (update 2023-02-03)

Komplexe Aufgaben durch kleine proaktive Bausteine lösen.

Diese Kursbeschreibung ist noch in der Entwicklung und kann sich ändern. Es soll hier aber frühzeitig die Möglichkeit geben sich über die grundsätzliche Richtung des Kurses zu informieren.

Der Kurs ist seminaristisch gehalten. Das bedeutet, dass es neben den frontalen Vorlesungsteilen auch Seminarbeiträge der Studierenden zu kleinen, ausgewählten Themen geben wird. Die wesentliche Arbeit besteht in der Erarbeitung eines eigenen Entwurfs zur Selbstorganisation von Netzen. (Siehe Prüfungsleistung)

  • Abschlusspräsentation: 2023-07-14, 12:00 Uhr, Raum S 216
  • Vorlesungsskript (Stand: final SoSe 2023)

Übungen

Hinweis

Wer lieber ein pdf liest, kann dies mit pandoc leicht erzeugen. Zum Beispiel für Aufgaben 01:

curl https://informatik.hs-bremerhaven.de/lafischer/lehre/ss23/wp43/01-uebung.md | pandoc -f markdown -t latex -o /tmp/01-uebung.pdf

Inhalt

Das Grundlagenwissen für die Arbeit am Entwurf wird in Vorlesungen vorgestellt. Die folgenden Themen werden in der Vorlesung diskutiert.

(1. Entwurf, Änderungen möglich)

  • Kleine Komponenten - Große Wirkung
    • sehr leichte Einheiten
    • Sensoren
    • Aktuatoren
    • (Kommunikation)
      • Kommunikationskanal
      • Umgebung
  • Theory
    • Self-organisation
      • Self-organising hierarchies
      • [Bonabeau hierarchy models] (https://link.springer.com/article/10.1007/BF02459478)
    • Swarm Intelligence
    • Greedy Algorithmen
    • Pheromone Communication
  • Selbstorganisation
    • Greedy Routing
    • Ameisen-Sortieralgorithmus
  • Anwendungen
    • Industrial Agent
    • Simulation
    • Verteilte Systeme
    • Autonome Systeme
    • KI-Algorithmen
      • Neuronale Netze
      • Adversarial Learning
  • Agentenprogrammierung

Prüfungsleistung

Prüfungsform: Entwurf

  • praktischer Teil siehe Entwurfsaufgabe
  • theoretischer Teil:
    • Vortrag und Ausarbeitung (Umfang: 3 Seiten)
    • Thema und Zeitplan in der ersten Woche

Entwurfsaufgabe

In einem dreistufigen Entwurf werden wir die Selbstorganisation von Netzen erforschen. Basierend auf gegebenen Graphen implementieren wir Agenten-basierte Algorithmen mit denen sich Wege in diesen Graphen finden lassen. Manchmal wird das unter dem Schlagwort “Next-Generation Networking” plakativ zusammengefasst.

Wir werden zwei unterschiedliche Formen implementieren. Zunächst eine Heuristik für sogenannte Greedy Embeddings, bei der sich die Knoten der Graphen durch wechselseitige Kommunikation innerhalb eines Raumes automatisch positionieren. Im zweiten Teil implementieren wir “Ameisen” die mittels “Pheromonspuren” die Wege im Graphen optimieren. Als finalen Versuch werden wir die beiden Methoden kombinieren.

Schnittstellen zwischen den “Ameisen” und “Knoten” werden gemeinsam spezifiziert so, dass die einzelnen Teillösungen leicht miteinander kombiniert werden können.

Teil 1: Selbstorganisierende Knoten

  • Jeder Knoten(-agent) kommuniziert seine aktuelle Position mit seinen direkten Nachbarn.
  • Jeder Knoten(-agent) passt seine eigene Position so an, dass er “in der Mitte” seiner Nachbarn steht.
Experiment/Eigener Spielraum:
  • Lokale Algorithmen und Parameter zur adaptionen an “die Mitte”.
  • Positionsräume (zyklisch, Dimensionszahl,…)
  • Reihenfolge und Äuslösung von Kommunikation
Ziel:
  • Möglichst viele Routen zwischen Knoten sind direkt “greedy routable”
  • Die “Position” eines Knotens stellt seine eindeutige Netzadresse dar.
  • Adaption der Adressen auf veränderte Vernetzungsstrukturen.

Teil 2: Ant Colony Optimisation (ACO)

Ein Problem aus Teil 1 ist, dass die Adresse der Knoten sich ändert, sobald sich irgendetwas an der Netzstruktur ändert. Wenn ich eine Nachricht an Knoten “A” senden möchte, muss ich also zunächst wissen an welcher “Position” sich der Knoten befindet.

Implementation kleiner Agenten (Ameisen), die sich im Graphen von gegebenen Startknoten zu Zielknoten über das Netz der Kanten bewegen. Dabei legen sie digitale Pheromonspuren auf ausgehenden Kanten aus und berücksichtigen diese bei Ihrer Wegeentscheidung. Eine Pheromonspur besteht dabei aus einer Zieladresse und der Stärke der Spur. Jede Ameise mit gleichem, oder ähnlichem Ziel, verstärkt eine Pheromonspur.

Eigener Spielraum:
  • Parametrisierung der Wegeentscheidung (z.B. wie stark reagiert meine Ameise auf Pheromone vs. wie oft folgt sie unbekannten Kanten?
  • Verdunstungsgeschwindigkeit von Pheromonen
  • Unterschiedliche Ansätze zur Generalisierung von Adressen in Pheromonspuren
Ziel:
  • Möglichst kurze Routen zwischen allen Knoten in möglichst kurzer Zeit etabliert.
  • Optimierte Speicherung der Pheromonspuren.

Teil 3: ACO auf Imperfekten Greedy Embeddings

Wenn wir bis hierhin gekommen sind, können wir versuchen beide Ansätze gleichzeitig zu nutzen. Eine Nachricht an einen Knoten mit unbekannter Adresse wird jetzt anhand dieser Pheromonspur weitergeleitet. Der Zielknoten könnte dann entsprechend in der Antwort auf die Nachricht seine aktuelle Adresse angeben. Ähnlich könnte mit einer Nachricht verfahren werden, welche das Ziel über “greedy routing” nicht erreichen kann.

Experimentieren:
  • Nach welcher Regel wird entschieden, dass eine Adresse nicht erreichbar ist?
  • Gibt es eine Regel nach der entschieden werden kann vom “Pheromon-Routing” wieder zurück zum “greedy routing” umzuschalten?
Ziel:
  • Selbstorganisation der Wegfindung eines veränderlichen Netzes
  • Nachrichtenpakete können “selbstständig” ihren Weg finden und schalten zwischen den Routingarten hin und her.
  • Geeignete Darstellung des Netzes und Bewertung des Systems.

Übergreifende Aufgaben

…abseits der Agentenprogrammierung

  • Erfassen,
  • Zusammenfassen,
  • Bewerten und
  • Darstellen der Wegefindung und der Qualität der gefundenen Wege

Vor- und Beigaben

  • Entwicklungsumgebung (noch nicht festgelegt)
  • Format der Graphbeschreibungen (als Input)
  • Format der Graphveränderungen (als Input)
  • Gemeinsam erstelltes Kommunikationsformat
  • Testgraphen