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 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!

Tuesday, September 21, 2010

Maxis' forgotten game

Maxis has quite a record in providing interesting simulation games since they came out with SimCity. The game SimLife: The Genetic Playground, however, never became a hit. In the game you can simulate an ecosystem including a climate simulation, a plant groth model and a complex model of animals including herbivores (plant eaters), carnivores (meat eaters), and filter feeders. Not enough, they added an evolution model including genes and phenotypes for all plants and animals.
At this point it becomes clear why this game was without success: it is more a research simulation than an actual game. The number of statistics and graphs also support this impression. Moreover, I guess that the actual processing power at the beginning of the nineties did not allow for extensive simulation experiments. Another distinctive feature between a game and a scientific experiment: a game is designed to give the player a fair chance of success (at least in the lower level). In contrast, SimLife simulations tend to end up in extinct animals and low-diversity flora very often. For example, Spore (from Electronic Arts, which bought Maxis some time ago) has a similar scenario, but is designed as a game. I was not really able to create a stable ecology with more than 5 different species, but still I prefer SimLife over Spore.

In overall, SimLife is interesting from a complex systems point of view even still today. If you want to try it, find it at some abandonware site and run it using an emulator, e.g. dosbox.

Sunday, September 5, 2010

Evolving cooperative behavior with neural controllers

In a computer experiment, we have investigated the evolution of cooperative behavior in multi-player games. Players were randomly mixed into groups and had the chance to increase their investment by paying money into a pot where it was multiplied. However, the payout money was evenly distributed to all of the players regardless of their contribution. So a freerider could get money without paying into the pot as long as some others did.
The players were controlled by a neural network that controlled the setting strategy. Using our evolutionary design tool FREVO, we evolved the behavior in order to maximize the profit for each player. There was a pool of players controlled by neural networks. After several rounds, the more successful (thus richer) individuals were allowed to stay in the pool and produce more offspring than the less successful ones.
In the first scenario the payout was the pot times three. So if, everybody would cooperate, you can earn your money gets tripled. If the maximum bet was 20$ this means a 60$ return, in other words a 40$ revenue. But if everybody in a group pays in, it's even better to defect - let's say five out of six cooperate, you get a 50$ revenue.
The game was played iteratively 10 rounds. Originally, we expected a strategy like Tit-for-Tat to evolve and prevail. However, defection turned out to be the only stable strategy. For each system state, individuals with the defecting gene could make more revenue. In other words, ruthless behavior paid off.
The situation changed, when we introduced a "synergy factor" into the payoffs. This meant that the money of cooperating players was not multiplied linearly, but over proportionally. Assume you are working with some colleagues on a common project, let's say writing a book. If you alone invest enough time into you chapter, the book still sucks because of the other chapters which are lame or missing. If half of the authors cooperate, the book might be accepted by a mediocre publisher, but still would not be that promising. But if everybody cooperates, the result is not double the revenue of the 50% case but much more!
In the experiment we reflected this issue by a quadratic factor in the pot function. Evolving the stable strategies again showed that after some generations of defecting players, cooperation evolved as a stable strategy!

This still gives hope for our civilization - although reading the daily newspaper does not always feed this hope.

Tuesday, August 31, 2010

Prisoner's Dilemma at the swimming pool

At my vacation I was witness of "beach chair reserving behavior". As soon as the pool opens, some guests reserve their beach chairs by putting towels on a couple of beach chairs. Then they go for breakfast or whatever. So, some time later, there are several empty but reserved beach chairs around the pool. Wanting no trouble, people have to sit on the ground. Doing some quick count during the day, I noticed that there were 20 beach chairs and - surprise! - in average only 20 people at the pool. So the system would work pretty well if nobody reserved the chairs and thus getting a good chance to find an empty chair when needed. For all the participants this would be a relief: the beach chair blockers don't have to get up so early in the morning and the others suffer less of beach chair shortage.

This can be modelled as a game theoretic problem, namely the multiplayer Prisoner's Dilemma. The Prisoners Dilemma is named after a fictional story where two suspects are interrogated regarding a major crime. The police have insufficient evidence for a conviction, so they offer the prisoners separately a deal: if one confesses (defects), he goes free (temptation payoff) and the other one gets a high conviction (sucker payoff). However, if both confess, both get punished (punishment payoff). If no one confesses, both get a less severe verdict, in overall the best for everyone (reward payoff).

The following table shows the possible strategies and payoffs (exemplified with the payoffs 0,1,2,3, the higher the better):

Prisoner B stays silent (cooperate) Prisoner B tells (defect)
Prisoner A stays silent (cooperate) (2,2) both get off with small sentence (0,3) Player A gets punished for everything, Player B goes free
Prisoner A tells (defect) (3,0) Player A goes free, Player B gets punished for everything (1,1) both get punished

At the pool, we have the case of a multiplayer Prisoner's Dilemma with the options to reserve a beach chair in the morning or to refrain from this behavior.

Most others do not reserve chairs (cooperate) Most others do reserve chairs (defect)
Player does not reserve chair (cooperate) (2,2) all get a fair chance for a beach chair when needed (0,3) player must sit on the ground, some others enjoy their reserved chairs
Player does reserve chair (defect) (3,0) player has guaranteed beach chair, others are suffering slightly (1,1) only chance to get a chair is reserving in the morning, worse situation than in upper left case

Unfortunately, with a sufficient number of defecting players (people who reserve a beach chair early in the morning) there is no merit in not reserving - you will go without a pool chair then (sucker payoff). So the only feasible strategy is to struggle for any free one in the morning and probably get one chair reserved for your family of 4 people. Another problem is that the people are constantly changing. So even if a cooperative behavior could be agreed on, there might be the arrival of a new bunch of defectors the next day, who would then feel themselves lucky to get all the chairs they desire so easily. There is certainly a tempation to reserve if nobody reserves, because then you have your beach chair guaranteed (otherwise there is still the chance that you get none, if already more than 20 people are at the pool). So, defecting is a stable strategy, although it is in overall worse for the whole group - this a tragedy of the commons.

Thursday, August 19, 2010

Self-organizing music

Bacterial Orchestra by Olle Corméer and Martin Lübcke is a self-organizing evolutionary music installation. Several hardware units (cells) listen to their surroundings and pick up sounds, eventually integrating them into their own 'genom'. By analyzing the rythm, each cell decides which tunes to keep and which (possibly mis-sounding) tunes to drop. Thus, over time a strange but interesting music evolves.
As a follow-up to the Bacterial Orchestra, the group has now brought their approach to smartphones where each cell lives on a mobile phone.
That way different people can gather with their mobiles and together create a musical organism. It will evolve in the same way as Bacterial Orchestra, but the social component will give it additional extra dynamics.

Saturday, August 7, 2010

Evolving a self-organizing soccer team

This video shows the evolution of coordinated behavior of simulated robot soccer players. In the simulation, each soccer player is controlled by a neural network. The neural networks are evolved using an evolutionary algorithm, so generation after generation the strategy improves.
After a few hundred generations, the players of a team adopt a useful behavior. The used approach did not include a trainer telling them how to play or specifying predefined roles for the players such as being a defender, midfielder or striker. Still, during a game, different behavior of the players emerges. Thus, similar to biological systems, the entities take up different roles in a self-organizing way. Since the agents are not predefined, such systems have a high robustness against failure of come of the entities.

Wednesday, August 4, 2010

Sometimes, self-organizing systems fail

New World army ants are known for their self-organized swarm raids accross the forest searching for food. They form a dense carpet of ants being able to attack much larger animals like larger insects and even lizards. In order to form the swarm, the ants orient themselves by tactual stimulation and by chemical trails laid by other ants. While this system is very effective, it has a potential mode of failure. Sometimes, these ants can get trapped in a circular movement, where the tactual stimulation and the chemical trails will lead to a positive feedback towards moving in a circle. Such behavior has been observed several times in natural environment, it is also relatively easy to reproduce the behavior under lab conditions. In a paper from 1944, T.C. Schneirla elaborates the initial conditions for circling army ants. Under heavy rainfall, these ants tend to move together in a small area. After the rainfall, ants at the margin of the huddle will tend to move around first. They will mostly follow the peripheral of the group due to tactual stimulation and thus create a circular trail of chemicals, which will be followed by the other ants. Army ants have been observed to be circling until they die of dehydration. This example shows that even systems which are evolved and hardened by billions of years of evolution (for organisms in general, ants came into existence about 130 million years ago when they split from the wasps) can be trapped in unwanted behavior.

The DEMESOS project

DEMESOS stands for Design Methods for Self-Organizing Systems and is a research project funded by Lakeside Labs. The goal of the DEMESOS research project is to elaborate basic concepts for a straightforward generic design process for creating self-organizing solutions, consisting of the stages modeling, simulation and iteration, validation, re-iteration or deployment. A way to achieve this is to evolve control systems as distributed cyberbrains controlling the agents of a complex system.

The dark side of self organization

When reading books or articles on self-organization, they usually emphasize its amazing effects. Animals develop beautiful skin patterns, social insects achieve wonderful tasks with their hive mind and cities organize themselves despite of lack of central management. Much more sparsely, the more dangerous, negatives examples can be found. To give just a few: The principle of pulse coupled oscillators causes perodic cycle oscillators to globally synchronize even if the oscillators are only localla coupled. An example for this is the handclapping of an audience, but to some extend, also the synchronized regular military step of marching armies. On structures that itself can exhibit an oscillation behavior this can lead to the resonance disaster. In 1850, 485 french soldiers walked over a suspenion bridge in military step which led to resonance oscillations and finally made the brigde collapse; 226 soldiers died. Similar events happened in 1831 to Broughton's suspenion bridge and to Millennium Bridge in London (which did not crash, but moved heavily because of just 160 people). For this reason, the German Straßenverkehrsordnung contains a special paragraph prohibiting military step on brigdes.
Another example for unwanted self organization is the emergence of traffic jams from small disturbations in dense traffic flow. Assuming one driver has to break a little bit, this would cause the following car to come too close, the respective driver has to brake even harder to compensate. This means an even stronger decceleration for the next car and so on. On a global scale, a wave of stopped or slowed down cars can be observed running in the opposite direction of the traffic. Regulating the cars down to a lower speed limit can avoid the emergence of this problem and therefore increase traffic troughput depite to a reduced speed limit.
Finally, many of us experience another annoyance of an application of self-organizing complex systems. Social networks like facebook apply knowledge from network theory and data mining to extract information out of local social interactions. A user might not wanted to have disclosed this infromation in many cases. The problem is here that the robustness of self-organizing systems does not allow to fool the system. Even if you keep information like your job or your place of residence for yourself (or state it incorrectly), this information can be retrieved indirectly via an analysis of the information given by your contacts - Facebook knows you. So in this case there is only one solution - quit facebook! Even this step is difficult, Facebook normally offers only a soft deactivation of the account while keeping all your data. The function for deleting your account is well hidden: you might want to go to use the official form for deleting your facebook account. You are welcome.

Calculating one-dimensional binary cellular automata using a Commodore 64

Were the homecomputers of the mid 80ies good for doing any practical work? For example, would they have been useful in doing research on complex systems? I think, the answer is yes! As a proof of concept, I have quickly implemented a short program in Commodore Basic V2.0 that lets you explore the behavior of binary cellulary automata specified by Wolfram's code. Wolfram's work dates also back to the 1980ies, but has recently gained much attention due to his book A new kind of science.

100 DIM K(8)
120 N=1
130 FOR I=1 TO 8
140 IF R AND N THEN K(I)=1
150 N=N*2
160 NEXT
300 PRINT CHR$(147)
310 IF RN=0 THEN POKE 1043,160:GOTO 340
320 FOR I=1024 TO 2023:IF RND(0)<0.5 THEN POKE I,160
330 NEXT
340 FOR L=1024 TO 1944 STEP 40
350 A=0:IF PEEK(L+39)=160 THEN A=4
360 B=0:IF PEEK(L)=160 THEN B=2
370 FOR P=0 TO 39
380 C=0:IF PEEK(L+1+P)=160 THEN C=1
385 IF P=39 THEN C=0:IF PEEK(L)=160 THEN C=1
390 IF K(A+B+C+1) THEN POKE L+P+40,160
400 A=B*2:B=C*2
410 NEXT
420 NEXT

The program displays the results of a simulation block code on the 1000 character 64 screen. Below is the result of simulating rule 30.

A tool for engineering self-organizing systems

A main problem in engineering self-organizing systems is to find the respective behavior for the interaction of the components so that the intented behavior emerges. We address this problem in the DEMESOS project. As an outcome of the project, we have just released a first version of our Framework for Evolutionary Design (FREVO). The tool is very generic and can be applied to find a (possibly distributed) solution (i.e. a configuration for a controller) for a defined problem (i.e. a simulation giving a fitness function) using an optimization algorithm. An example of its use was to breed the neural network controllers for an agent-based robot soccer team (see
FREVO is released under the GPL open source license. The framework, some sample components, and a tutorial can be accessed at the project webpage

Self-organizing systems can solve real-world problems

On January 12, 2010, a horrible earthquake struck Haiti, devastating many houses, streets and bridges. This changed infrastructure makes it very difficult for the rescue and support teams to plan the transport of supplies and medical goods, since the standard street maps became inaccurate. To quickly adapt to these problems, the OpenStreetMap community distributedly updated their map information and integrated various data sources, thus providing an accurate mapping almost in real time (see This example shows that self-organizing approaches are especially of interest in catastrophic scenarios, where traditional hierarchically structured systems are missing the necessary level of robustness and adadptivity.

At IWSOS'09 in Zurich

We went to Zurich, Switzerland to attend IWSOS 2009, the Fourth International Workshop on Self-Organizing Systems, which was held in December 9-11 2009. I gave a talk on A Survey of Models and Methods for Self-Organizing Networked Systems, which was joint work together with Raissa D'Souza, Christian Bettstetter, and Hermann de Meer. My colleague István presented a poster on Towards evolving cooperative behavior with neural controllers were we researched on the initial conditions which are necessary to evolve cooperative behavior.

A review on the Lakeside Research Days 2009

Beginning of last summer we organized the Lakeside Research Days 2009 at the Labeside Labs in Klagenfurt. The days, which took place for the second time, were an intensive one-week workshop full of discussions, talks, and group work on the topic of self-organizing systems. The speakers, all deeply involved in self-organizing systems research, included Alain Barrat, Christian Bettstetter, Francis Heylighen, Hermann de Meer, Raissa D'Souza, Marc Timme, Anne van Rossum, and myself. The event was very successful in providing new insights, creating ideas, enabling cooperations and, in general, creating the joy of science reminding me why I became a researcher.
Our colleague Christian Philipp made an excellent short movie capturing the atmosphere and spirit of the event:

The self-organizing student protest at University of Vienna

On October 22, hundreds of protesting students occupied the Audi Max lecture room at the University of Vienna in order to create more awareness for their situation and their demands for a better university. Actually, the quality of the studies decreased when Austrian goverment de facto waived the tuition fees creating a flood of national and international students into particular studies. Since that date, the students still occupy the lecture room.
While I am very sceptic that their demands for a high quality study with a low student-to-professor ratio together with an unlimited offering of studies at no charge can be ever fulfilled within a reasonable budget, I am very impressed by the organizational structure of the protesters.
The Audi Max has a nominal capacity of 800 persons, thus without any kind of organization, the communication and coordination would not work. The traditional approach would be to elect a leader and a group of sub-leaders, etc. in order to build a hierarchically structured organization. Interestingly, the protesters are not organized like this. Instead their movement is self-organized, but structured into several task forces. This makes a lot of sense, since the people powering the protest are not always there - some might lose interest or stay away for some time, while others might join. Thus, while a service, like for example the press information is stable, its establishing components might be not. This is a nice analogy to bodily organs consisting of cells that die and reproduce in a much faster pace than the time span for which the organ is operable.
Furthermore, the students organize two plenum conferences everyday where the task forces coordinate. This plenum is as well based on a grassroots democracy. While there are elected moderators for the discussion, there is no permanent hierarchy in the organization. Yet, the system is effective and stable.
By the way, this is only one out of probably thousands and thousands examples for self-organizing systems. In a paper at IWSOS'09, we investigated how we can design or model such systems.

IEEEXtreme 24 hours programming contest

I was asked to act as a proctor for the team "Quit pro Code" at the IEEEXtreme 2009 contest. Since the tasks of a proctor (mainly to take care of the team(s)) are small comparable to those who are actively participating, I had some time to analyze the contest and learn about its philosophy.
The team of three programmers was given a set of problems which they have to implement in their favorite programming language (at least C,C++,Java were supported). All problems came with an exact specification and a set of test cases. The evaluation of a solution was performed automatically via the Mooshak tool. Given that the contest organizers had chosen their testcases well, this meant that a solution had to be perfect up to the last bit and, in some cases, also performant enough in order to give points.
It was interesting to note that time appeared not to be a limiting factor for the success in the contest. How fast problems have been solved only influenced the ranking between teams with the same amount of points. Basically, this was a good choice, since it gave a motivation for the teams to sleep and eat regularly within the 24 hours in order to stay focused.
None of the exercises involved writing large or even moderate-sized programs. As far as I could see, the solutions of my team usually were below a length of 200 LOC. The trickiness was more in deriving the idea for the possible solution and implementing it well without errors. Also creating test cases with good coverage was a very demanded skill in the contest.
To conclude, although I thought before that the IEEEXtreme contest is an event for code "hackers", my opinion is now that some classic rules of software engineering still hold true for this event. The requirement that a solution had to be exactly correct did not allow for a sloppy or ad-hoc programming style, and thus the classic stages like specification of operational and performance qualification, design specification, implementation, black box and white box testing and validation could be observed. Since a team member spent only 2-3 hours on one problem, I could observe miniature software projects evolving in a fast-forward manner.
By the way, the team Quit pro Code finished place 25th out of over 700 participants from all over the world. So, I am very proud of the team that I was allowed to proctor!

See also

The discussion on the flood of new students at Austria's universities

Recently, the Austrian goverment has decided to waive tuition fees for most students from European Union (EU) if they are within a given time plan. Students from outside of the EU pay half of what they have paid so far.
Many newspapers reported now about a consequence of this action - Austria's universities are overrun by students, which compromizes the quality of the studies. Very controversial, Austrian universities have also shown to be attractive for students from Germany who did not get approved at universities in their home country.
Unfortunately, newspapers have concentrated on complaining about the situation for overrun studies (typically psychology or communication science). However, this is not the case in general. It is worth mentioning that the University of Klagenfurt offers a technical study on "Information Technology" in English language, where currently only a few number of students fill the lecture rooms.
Although the study is of high quality and the teacher-to-student ratio is excellent, the curriculum does not attract too many students, neither national nor international. A main reason therefore is, in my opinion, the lack of information about this possibility. I don't want to be pathetic, but I get the impression that newspapers always forget that the University of Klagenfurt even has a technical faculty. And it seems that journalists prefer articles that make noise about a problem and stir up old Austrian-German ressortiments rather than providing potential students the information how to avoid this problem by choosing a study that is not overrun...