Modellierung und Techniken zur Optimierung von Multiagentensystemen in Zellularen Automaten

Für eine Reihe von Problemstellungen werden heutzutage Multiagentensysteme als dezentral organisierte Systeme mit autonom und parallel agierenden Agenten eingesetzt. Solche Systeme sollen oft Eigenschaften wie Adaptivität, Selbstheilung, Kontrollierbarkeit oder Ausfallsicherheit aufweisen. Schlagworte wie Schwarmintelligenz, Emergenz und Synergie werden verwendet, um zu beschreiben, wie aus möglicherweise einfachen lokalen Subsystemen komplexe globale Systeme entstehen. Der systematische Entwurf von lokal agierenden Agenten, so dass eine globale Aufgabe erfüllt werden kann, ist nicht trivial. Aber durch die Parallelität der Verarbeitung und die relative Einfachheit der einzelnen Agenten kann ein Einsatz von Multiagentensystemen im Vergleich zu einer komplexen Verarbeitungseinheit zu einer Verbesserung der Leistung und/oder zu einer Verringerung des Ressourcenbedarfs führen. Z.\,B. können in Kamerachips Multiagentensysteme zur parallelen Verarbeitung von Bilddaten eingesetzt werden, oder zu adaptiven Routing-Algorithmen in Netzwerken auf Chips. Der schwierige Prozess des Entwurfs eines emergenten Systems kann sich daher trotzdem lohnen. Das generelle Ziel dieser Arbeit ist es, erstens ein Modell zur Beschreibung von Multiagentensystemen zu entwickeln, das für beliebige Strukturen der Agentenkontrolle (Verhaltenssteuerung) geeignet ist und zweitens Techniken zur Optimierung dieser Strukturen zu entwerfen. Zellulare Automaten können als Modell für Multiagentensysteme, denen eine räumliche diskretisierbare Struktur anhaftet, und die in Hardware-Chips implementiert werden sollen, gut verwendet werden. In dieser Arbeit wird ein allgemeines Modell für Multiagentensysteme in Zellularen Automaten entworfen, das mit einer beliebigen Struktur für die Programmierung des Agentenverhaltens versehen werden kann. Es werden für drei Beispielanwendungen Multiagentensysteme in dem entworfenen Modell Agenten mit einer Steuerung durch endliche Zustandsautomaten eingesetzt: das vollständige Erkunden eines in kleine Segmente aufgeteiltes, unbekanntes Gebiet mit Hindernissen, die vollständige Verbreitung von initial, gegenseitig exklusiv verteilter Information und der Transport von Nachrichten in einem zweidimensionalen Mesh-Netzwerk. Das Agentenverhalten, also der Inhalt der endlichen Zustandsautomaten, wird dabei mit Genetischen Algorithmen heuristisch optimiert, um die vorher definierten, globalen Ziele zu erreichen. Es werden außerdem generelle Optimierungstechniken für den strukturellen Aufbau der Agenten entworfen und Maßnahmen zur Anpassung der Konfiguration des Zellularen Automaten vorgestellt, alle mit dem Ziel, das Multiagentensystem als Ganzes effektiver und effizienter zu machen. Am Schluss der Arbeit werden Experimente und Ergebnisse präsentiert, die die Effektivität und Effizienz der Genetischen Algorithmen, sowie der Optimierungstechniken für die Agentenstruktur bewerten. Die Genetischen Algorithmen bewähren sich in allen Beispielsystemen und finden akzeptable Agentenverhalten. Nicht alle Anpassungen in der Agentenstruktur und der Konfiguration des Zellularen Automaten sind effektiv und effizient, aber erfolgreich sind insbesondere solche Optimierungen, die eine räumliche oder zeitliche Heterogenität oder eine Randomisierung in das Verhalten der Agenten hineinbringen