Tuesday, March 29, 2011

Evolving a cellular automaton with neural controllers

Evolution of Hungarian flag
What happens if you integrate a cellular automaton with neural network controllers? In an experiment, we extended the model of CA with a neural network that controls the cell behavior according to its internal state. The model is used to evolve an Artificial Neural Network controlling the cell behavior in a way a previously defined reference pattern emerges by interaction of the cells. Each cell is controlled by an instance of the same ANN. The ANNs have connections to neighbors and one output of each ANN determines cell color.
At the beginning of each simulation, all cells had the same state and commenced their operation at the same time - this is comparable with a number of people cooperatively drawing an image in the dark.
We used our tool FREVO for evolving the neural network in a way that it reproduces the given pattern. The best results have been achieved when evolving simple structures with large areas of a single color as they are present for example in flags. For more complex images, however, the current setup causes the evolutionary algorithm to get stuck at a suboptimal stage like depicted in the approach to learn the image of Leonardo da Vinci's Mona Lisa painting. There is, however, a large space of possibilities for variations of the model which gives rise to future work.
Complex images like this painting cannot be reproduced - Mona Lisa kinda vanished huh?

Friday, March 11, 2011

Self-organized positioning of mobile relays

Quadcopter from Microdrones
The Fifth International Workshop on Self-Organizing Systems (IWSOS 2011) in Karlsruhe was a great success. Helmut Lindner won the best student poster award with his work on self-organizing mobile drones.
In catastrophic scenarios, wireless communication is an important means for coordinating rescue and saving operations. However, in such situations, the standard communication infrastructure is often not available. One possibility to solve this problem would be the usage of helicopter drones as flying relay stations. For the positioning of the drones, we would have to cope with disturbances of wireless media (interference from other nets, signal fading, etc.), an unknown landscape, as well as the need to add or remove relay nodes as they need to recharge.
Simulation of movement patterns for four drones
At IWSOS 2011, Helmut Lindner presented a evolution-based algorithm for a self-organizing positioning of the drones. The ground stations are connected by multi-hop communication over drone relays. For each possible route a “flow” value Phi is calculated, which serves as a local fitness function for each drone. The drones are moving around in order to increase their Phi value. A movement that worsened the Phi value is reversed, while for an improvement, the current direction is kept. This way, the drones execute a distributed (1+1) evolution strategy.