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

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.

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.