TU Darmstadt / ULB / TUbiblio

Algorithmen und Hardwarearchitekturen zur optimierten Aufzählung von Automaten und deren Einsatz bei der Simulation künstlicher Kreaturen

Halbach, Mathias (2008)
Algorithmen und Hardwarearchitekturen zur optimierten Aufzählung von Automaten und deren Einsatz bei der Simulation künstlicher Kreaturen.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Abstract

Eine minimalistische Robotersteuerung zur vollständigen und autarken Überquerung eines Gebietes bildet die Basisidee. Prinzipiell wäre es möglich, auch andere Aufgaben mit dieser, auf einem Zustandsautomaten basierenden Steuerung zu erfüllen, sie ist nicht einmal an einen Roboter gebunden. So können die steuernden Automaten auch für unterschiedlichste Bereiche selbst in der Theoretischen Informatik Verwendung finden. Die sich stellende Frage ist, wie ein minimalistischer Automat aussieht. Dazu werden alle möglichen Kombinationen aufgezählt. Da dabei aber zahlreiche Duplikate entstehen, die sich in ihrer Auswirkung nicht unterscheiden, gilt es, nur die relevanten Automaten aufzuzählen. Hierzu wurde ein neuartiges, allgemein anwendbares Schema entwickelt. Dazu müssen die Automaten mehrere, effizient auswertbare Kriterien erfüllen – andernfalls lassen sich aufgrund dessen eine Reihe von Automaten ungeprüft überspringen. Dies führt zu einer erheblichen Reduzierung der notwendigen Überprüfungen. Statt real mit Robotern die Steuerung durch die gewonnenen Automaten auszutesten, ist es einfacher, ein Simulationssystem zu schaffen, basierend auf dem Prinzip des zellularen Automaten. Neben einer rein softwarebasierten Lösung gibt es auch verschiedene, hardwarebasierte Spezialarchitekturen unter Verwendung eines FPGA-Bausteins, um so zur Lösungsfindung beizutragen. Nach einem Vergleich der unterschiedlichen Konzepte erfolgt schließlich die Präsentation einiger Ergebnisse von erfolgreichen Automaten.

Item Type: Ph.D. Thesis
Erschienen: 2008
Creators: Halbach, Mathias
Type of entry: Primary publication
Title: Algorithmen und Hardwarearchitekturen zur optimierten Aufzählung von Automaten und deren Einsatz bei der Simulation künstlicher Kreaturen
Language: German
Referees: Hoffmann, Prof. Dr.- Rolf ; Fey, Prof. Dr.- Dietmar
Date: 15 November 2008
Place of Publication: Darmstadt
Publisher: Technische Universität
Refereed: 14 May 2008
URL / URN: urn:nbn:de:tuda-tuprints-11810
Abstract:

Eine minimalistische Robotersteuerung zur vollständigen und autarken Überquerung eines Gebietes bildet die Basisidee. Prinzipiell wäre es möglich, auch andere Aufgaben mit dieser, auf einem Zustandsautomaten basierenden Steuerung zu erfüllen, sie ist nicht einmal an einen Roboter gebunden. So können die steuernden Automaten auch für unterschiedlichste Bereiche selbst in der Theoretischen Informatik Verwendung finden. Die sich stellende Frage ist, wie ein minimalistischer Automat aussieht. Dazu werden alle möglichen Kombinationen aufgezählt. Da dabei aber zahlreiche Duplikate entstehen, die sich in ihrer Auswirkung nicht unterscheiden, gilt es, nur die relevanten Automaten aufzuzählen. Hierzu wurde ein neuartiges, allgemein anwendbares Schema entwickelt. Dazu müssen die Automaten mehrere, effizient auswertbare Kriterien erfüllen – andernfalls lassen sich aufgrund dessen eine Reihe von Automaten ungeprüft überspringen. Dies führt zu einer erheblichen Reduzierung der notwendigen Überprüfungen. Statt real mit Robotern die Steuerung durch die gewonnenen Automaten auszutesten, ist es einfacher, ein Simulationssystem zu schaffen, basierend auf dem Prinzip des zellularen Automaten. Neben einer rein softwarebasierten Lösung gibt es auch verschiedene, hardwarebasierte Spezialarchitekturen unter Verwendung eines FPGA-Bausteins, um so zur Lösungsfindung beizutragen. Nach einem Vergleich der unterschiedlichen Konzepte erfolgt schließlich die Präsentation einiger Ergebnisse von erfolgreichen Automaten.

Alternative Abstract:
Alternative abstract Language

The fundamental idea is a minimalist control that enables a robot to cross a defined space independently. This control is a finite state machine. In principle it would be possible to complete other tasks with this finite state machine, as it is a self-contained unit. Thus it might also be useful for different fields of the theoretic computer science. The first question to answer is the construction of such a finite state machine or automaton. For that purpose all possible combinations are enumerated. As numerous combinations will be named double or triple the main task is now to develop a scheme which makes it possible to select only the automata of relevance. For that, relevance has to be defined. This is done by using general criteria, which can be calculated efficiently. For one missed criterion similar automatons can be skipped in the enumeration without being checked. This reduces the amount of automata being checked considerably. Instead of using real robots to test the generated automatons, it is easier to construct a simulation system, based on the principles of cellular automata. In addition to a purely software based solution also various hardware based architectures are designed. Field programmable gate arrays (FPGA) are used to calculate the solutions. After comparing the different concepts the results will be presented.

English
Uncontrolled Keywords: Automaten, Aufzählen, Enumeration, normieren, reduzieren, vereinfachen, Präfix, Isomorphie, Permutation, Klassifizierung, Semantik, Mealy, Pipeline, Simulation, Hardwarearchitekturen, Zellularautomat, Hardware, Bus, FPGA, Künstliches Leben, künstliche Intelligenz, formale Sprachen
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Computer Architecture
Date Deposited: 10 Dec 2008 11:43
Last Modified: 26 Aug 2018 21:25
PPN:
Referees: Hoffmann, Prof. Dr.- Rolf ; Fey, Prof. Dr.- Dietmar
Refereed / Verteidigung / mdl. Prüfung: 14 May 2008
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details