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.

Friday, January 28, 2011

Mozart meets Darwin now on Android

Our experiment "Mozart meets Darwin" (see my previous blog article about it for details) is online again. You can take part in the experiment by voting using the Flash application below. We also provide a version for Android mobile phones now (the download is free). Please spread the word and tell your friends: we expect many votes in order to make this work.
I will provide an analysis of the results after a few weeks.


Get Adobe Flash player


Wednesday, November 24, 2010

So when do we call a system self-organizing?

Recently, in a PhD seminar talk the discussion arose, if a particular system is self-organizing or not. Such discussions are emerging with high probability every now and then followed by a discussion that lasts for some time.
It seems that the term "self-organizing system" is a very difficult concept for the following reasons:
First, being named self-organizing, such system are often literally understood as some entity that organizes itself, like a person managing her own affairs in life. The "self" can be misleading here since it may be understood as a single controlling entity.
Actually in self-organization, there is no "self" that organizes. It rather means that systems appear to organize themselves without external direction, manipulation, or control.
Cloth of gold cone: visible pattern as a result
of a self-organizing process (Image: Wikipedia)
To avoid this misinterpretation, the term is sometimes replaced or augmented with spontaneous pattern emergence. But this creates a mental image of patterns in the reader's mind (like the cone displayed to the right). Other self-organizing processes like coherent laser light or clock synchronization create internal order, but no visible pattern.
Another problem is that you can change a system with external control to one without by redrawing the systems boundaries. So a bunch of workers being instructed by a foreman would not be perceived as self-organizing, but a construction cite with different teams, each one coming with a foreman, but otherwise loosely interacting might be seen as self-organizing (unless you model in the blueprints).
Gershenson and Heylighen proposed a nice way out of this dilemma by stating "self-organization is a way of observing systems, not an absolute class of systems". So depending if the self-organizing view is beneficial, you should model your system accordingly, otherwise not.
Another difficulty arises from the fact that self-organization roots in several disciplines, there are many notions and definitions from biology, chemistry, computer science, cybernetics, economics, mathematics, physics, and sociology. Most of these disciplines contribute one or more definitions on self-organization based on the discipline-specific terminology.
As shown by the following examples, there is no single brief but comprehensive definition for self-organization. The following definitions may be useful though:

A self-organizing system (SOS) consists of a set of entities that obtains an emerging global system behavior via local interactions without centralized control.
(from Research Days'08, see [IWSOS:2008]))

Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning. (Wikipedia)

A self-organizing system is a system that changes its basic structure as a function of its experience and environment. (Farley and Clark 1954)

Are they really refering to the same thing? So be warned, when a discussion heads towards the definition of self-organization!

Thursday, November 11, 2010

A self-organizing algorithm for video distribution networks

The way how users consume videos has changed with the availability of large repositories with a high number of more or less related videos. Many users are only interested in tiny fractions of a video and not even necessarily in the original temporal order. Moreover, they might wish to dynamically compose portions of di erent videos into one presentation.
For example, take a video recording of a ski-jumping competition. Some users might be interested in watching it sequentially. A trainer might be interested in studying the jumping-off technique of athletes in parallel. Another user might be interested in the performance of several jumpers from one country.
In order to keep up with this emergent access patterns, we invented a self-organizing video delivery network that is based on artificial hormones which are spread throughout the network when a particular video is requested. The hormone spreading is affected by the bandwidth and delay parameters of the network edges, thus indirectly help in searching for the (currently) best path to transmit a video.
The interactions between nodes like spreading/evaporating hormone or moving a video according to the neighbor with highest hormone gradient are all local within a node's neighborhood. Still, the system is able
to guide the overall transportation and placement of units in the system up to near optimum.

Friday, November 5, 2010

Mozart meets Darwin - Creating music by evolution

Mozart meets Darwin is a case study where we try to evolve a piece of music, a simple melody. To evolve something, we need a model of the canditates, a method to mutate a candidate (that is apply some random perturbations), a method to recombine two parent candidates into similar children canditates, and a way to assess the fitness of a result. Using the music notes as DNA, we came up with solutions for mutation and recombination. But the assessment of the quality cannot be done by the machine - that is where we need you to indicate which piece of music is better than the other.

Get Adobe Flash player


In the application above, you can listen to sets of five examples and rank them according to your personal preference. A computer program on a server will gather the rankings until it has sufficient input to decide how to evolve to the next generation. Mutation and recombination will be the "creativity" of the computer program. Please rank a few sets and get an impression of the approach. If you come back later, you will notice that the music pieces have improved, typically towards the overall music taste - hopefully you like it!
The results will be posted later under the GNU FDL license - so you can use the evolved melody in a song if you like.

Sunday, October 17, 2010

Ig Nobel Prize goes to research on self-organizing slime mold

The behavior of slime mold, a fungus-like organism, has been one of the most famous models of selforganization. Slime mold begin life as amoeba-like cells, each wandering around in random walk behavior. But under certain environmental conditions they suddenly change their behavior and aggregate to a single multi-cellular body; with the help of chemical signals they self-organize into a network of protoplasmic strands. This emergent behavior can solve complex tasks like creating shortest interconnections between food sources in a maze.
Fuligo septica slime mold
(not dog vomit ;-)
from Wikipedia.org/CC license
A research team in Japan discovered that if they placed food piles (oat flakes) around a central slime mold in the same layout as 36 outlying cities around Tokyo, the mold created a network connecting the food sources that looked similar to the existing rail system. By introducing also topographical barriers, the results were even more similar.
Out of this team, Mark Fricker and Dan Bebber recently received the Ig Nobel award in transportation. The Ig Nobel Prizes are given annually for ten achievements that "first make people laugh, and then make them think.". But they are also a show that makes people's interested in science, so the Ig Nobel award might be considered more than just a Nobel Prize parody. However, the slime mold result being awarded there shows that many people still perceive complex systems result as something strange, funny, or improbable. Still, it is great to see research on self-organizing systems awarded!