Student Semester Project
Winter 1997/1998
Robot Learning Group
|
|
Student Semester Project
|
|
Evolutionary robotics with an unique genome
Florian Seydoux
Department of Computer Science
Assistant: Joseba Urzelai
Vice Assistant:
Dario Floreano
Evolutionary Robotics is a promising discipline that offers plenty of possibilities.
However, typically employed technics (i.e. traditional genetic algorithms) take too
long time before converging into acceptable solutions and they comsume huge memory
resources. This latest constraint implies serious limitations for applying traditional
evolutionary algorithms to miniature autonomous embedded robots, since they do not
have enough memory resources to store long genetic populations.The main goal of this project is to analize and test the PBIL (Population Based Incremental Learning, Shumeet Baluja, 1994) algorithm. This variation of traditional genetic algorithms represents the population of genotypes by means of a probabilistic vector, reducing considerably the amount of memory resources needed for evolving genetic populations.
At a first stage, the algorithm was tested for a combinatory optimization problem (Four-Peaks). The results show that PBIL performs as well as, or better than traditional genetic algorithms carefully tunned to do well on this problem. After this initial experiment, the synaptic weights of a simple perceptron neural network with some recurrent connections at the output layer were evolved in order to generate obstacle avoidance behavior. The algorithm was performed in simulation using the Khepera Simulator of Olivier Michel (see figure). Each individual was let to perform 100 motor actions, and fitness values were computed in order to evaluate the individuals. Several hundreds of generations were necessary before obtaining an acceptable obstacle avoidance behavior like the one showed in the figure above. The large number of generations needed (larger than other similar experiments using traditional genetic algorithms) is due to the difficulty in deeling with several maximums (the populations are always generated around one point in the search space and there are no subpopulations like with traditional genetic algorithms), and maybe due to the absence of crossover operator.
Best individuals were also tested on a real Khepera robot. Even if the robot was capable of performing an obstacle avoidance behavior, the results were worse than in simulation (the robot got stuck in several points of the environment).
There is some work to do before obtaining clear conclusions about the advantages of applying the PBIL algorithm in evolutionary robotics. PBIL algorithm was used in simulation in our experiences. It would be interesting to apply the algorithm on a real robot, as a miniature khepera (until now only individuals evolved in simulation have been tested on a real khepera robot). On the other hand, only the synaptic weights of the neural network were optimized. Experiments where PBIL algorithm evolves the architecture of the neural network could be performed, too. Finally, more complex tasks (e.g., dinamically changing environments) should be evolved in order to analize the capabilities of PBIL algorithm.