TU Darmstadt / ULB / TUprints

Modellierung und Techniken zur Optimierung von Multiagentensystemen in Zellularen Automaten

Ediger, Patrick (2011)
Modellierung und Techniken zur Optimierung von Multiagentensystemen in Zellularen Automaten.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Dissertation von Patrick Ediger - PDF
Diss_Ediger.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (9MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Modellierung und Techniken zur Optimierung von Multiagentensystemen in Zellularen Automaten
Language: German
Referees: Hoffmann, Prof. Dr. Rolf ; Fey, Prof. Dr. Dietmar ; Fürnkranz, Prof. Dr. Johannes
Date: 28 June 2011
Place of Publication: Darmstadt
Date of oral examination: 1 June 2011
Abstract:

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.

Alternative Abstract:
Alternative AbstractLanguage

Nowadays Multi Agent Systems are applied for many problems as decentrally organized systems with agents acting autonomously and in parallel. In many cases it is desired to find capabilities like adaptivity, self-healing, controllability and reliability in such systems.

The words swarm intelligence, emergence and synergy are often used to describe the phenomenon of the development of a complex global system behavior with only locally acting and possibly simple subsystems. A systematic approach of designing local agents in a way such that a global goal is reached by guaranteeing reliability, controllability etc. at the same time, is not a trivial task. But the implementation of a Multi Agent System can still be an improvement compared to a single complex processing unit, if, due to the exploitation of parallelism and the simplicity of the agents, the performance can be increased and/or the need of resources can be reduced. E.\,g., Multi Agent Systems can be implemented for image processing in camera sensor chips or for adaptive routing algorithms in networks on a chip. Thus, in spite of the difficulties of the designing process of an emergent behavior, it might be worth doing it.

The general goal of this work is on one hand the development of a Multi Agent System model, which is suitable for an arbitrary agent control structure (agent behavior control) and on the other hand the design of techniques for the optimization of the control structure.

Cellular Automata are generally well applicable as a model for Multi Agent Systems with a spatially discrete structure and which are supposed to be implemented in hardware chips. In this thesis, a general model for Multi Agent Systems in Cellular Automata is developed, which can incorporate an arbitrary structure for the programming of the agent behavior.

Three example applications of Multi Agent Systems are defined in this thesis: the complete exploration of an unknown area with obstacles, that is divided in small sections, the complete distribution of initially mutually exclusively distributed information and the transport (routing) of messages in a two-dimensional mesh network. Agents that are controlled by a finite state machine are used in these examples. The behavior of the agents (i.\,e., the content of the finite state machines) is evolved with Genetic Algorithms, in order to reach the previously defined goals. Additionally, optimization techniques for the structural assembly of the agents are designed. Furthermore, methods for the adjustment of the configuration of the Cellular Automaton are presented. All of the methods and techniques are suggested with the intention to increase the effectivity and the efficiency of the Multi Agent Systems as a whole.

Eventually, experiments and results are presented, which evaluate the effectivity and efficiency of the Genetic Algorithms, the optimization techniques for the agents' structure as well as the methods for the adjustment of the Cellular Automaton. The Genetic Algorithms perform well in any of the example systems and find feasible solutions (agent behaviors). Not all of the adjustments and optimization techniques are effective and efficient. Particularly those methods that induce a spatial or temporal heterogeneity or that use a certain amount of randomness in the agents' behavior, are effective.

English
Uncontrolled Keywords: Zellularer Automat, Multiagentensysteme, Genetische Algorithmen, Verhaltensoptimierung
Alternative keywords:
Alternative keywordsLanguage
Cellular Automata, Multi agent systems, Genetic Algorithm, Behavior OptimizationEnglish
URN: urn:nbn:de:tuda-tuprints-26436
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Computer Architecture
Date Deposited: 29 Jun 2011 11:15
Last Modified: 08 Jul 2020 23:56
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/2643
PPN: 386244200
Export:
Actions (login required)
View Item View Item