Symposium on Self-* Systems – Biological Foundations and Technological Applications

Symposium on Self-* Systems – Biological Foundations and Technological Applications

part of EMCSR 2012, the 21st European Meeting on Cybernetics and Systems Research

April 10-13, 2012, Vienna, Austria

http://www.emcsr.net/

Call for papers

Part 1. Biologically and Socially Inspired Self-* Systems

Chairs: Vesna Sesum-Cavic, Institute of Computer Languages, Vienna University of Technology, Vienna, Austria, and Carlos Gershenson, Instituto de Investigaciones en Matemáticas y en Sistemas, Universidad Nacional Autónoma de México, Mexico City, Mexico

The increased complexity in today’s’ IT industry is one of the top problems and important obstacles. Self-organization appears as one promising way to cope with the increased complexity. Generally, self-* systems should posses as many self-* properties as possible (self-healing, self-tuning, self-learning,…) in order to achieve self-organization. Self-organization surrounds us. Many interesting self-mechanisms exist in our environment from which we can learn a lot. A careful observation of mechanisms in nature and society can discover some new tools that could beneficially be applied to different IT-problems. This conference track will focus on both biologically and socially based self-* systems. The papers could be theoretically based as well as with practical applications to important IT-problems.

Session 1: Biologically Inspired Self-* Systems (chair: V.C.)
Session 2: Socially Inspired Self-* Systems (chair: C.G.)

For further information contact vesna@complang.tuwien.ac.at and cgg@unam.mx.

Part 2. Self-Organizing Networked Systems

Chairs: Wilfried Elmenreich, Networked and Embedded Systems, Alpen-Adria-Universität Klagenfurt, Austria, and Carlos Gershenson, Instituto de Investigaciones en Matemáticas y en Sistemas, Universidad Nacional Autónoma de México, Mexico City, Mexico

Part 2 of this symposium will present and discuss current and novel approaches for applications of self-organizing systems.

A self-organizing system typically consists of many networked entities that organize themselves and cooperate through the exchange of information without the need of a centralized control instance but using a distributed approach. Information is exchanged locally among individual entities in the frame of the fulfillment of a certain global objective. Some simple and high-level rules in the individual entities lead to sophisticated functionality of the overall system. Many examples of successful distributed localized organization can be found in nature (e.g., ants, fireflies).

Self-organizing systems have various favorable properties:

• They typically adapt very easily to changes from inside and outside the system.
• Additional entities can be added and will be assimilated into the global system.
• Entities may be removed without too much affect on the global system, and other entities may take over crucial tasks of them.
• Furthermore, self-organizing systems scale very well and there is no bottleneck of a central authority.

Research into self-organizing networked systems not only has technical and user-oriented aims, it also enables a high degree of interdisciplinarity.

We encounter self-organizing systems on an almost daily basis in:

• the formations of swarms of fish and migratory birds
• the interplay of termites when they build their hills
• the activity of body cells during the healing of wounds.

In many areas of nature, single individuals or organisms work together without central coordination, but in perfect harmony. Large areas of the economy have already been functioning for many years according to this paradigm.

It is the aim of this symposium to create a forum for exchanging ideas, discuss solutions and share experiences among researchers and developers of self-organizing systems applications.
For further information contact wilfried.elmenreich@uni-klu.ac.at and cgg@unam.mx.

Confirmed keynote speakers include Edgar Morin, Péter Csermely, and Péter Érdi.

Submission details:

For submission and conference details, please visit http://www.emcsr.net/?page_id=55

Important Dates:

Submission deadline: January 14, 2012 extended to January 20, 2012
Notifications:             January 27, 2012
Schedule published:   February 7, 2012
Conference:                April10-13, 2012

Evolution as a tool for understanding and designing collaborative systems

Saudações de São Paulo (Greetings from Sao Paulo)!

I was invited to the IFIP Working Conference on Virtual Enterprises (PRO-VE 2011) to give the keynote talk on evolution as a tool for understanding and designing collaborative systems.

Here is a short summary of the talk:

Research on collaboration addresses the common tension between

• what is good for the individual actor in the short run, and
  
• what is good for the group in the long run
  

This research is based on game theory and, therefore, employs such models as the Prisoner’s Dilemma or public goods games as the basis for analysis. Using game theory, you can approach the question What is the most rational strategy? for a given model. However, in real systems often converge towards equilibria with behavior different from the calculated rational one. In order to explain these results, evolutionary approaches are a useful tool. To solve the contradiction, it is necessary to realize that typically interaction properties have not been designed by a central ruler but evolved over time. However, finding the appropriate interaction rules that induce a particular overall behavior is difficult due to the unpredictable or counterintuitive nature of such emergent and complex systems. Therefore, we propose evolutionary models to examine and extrapolate the effect and development of particular collaboration rules. An example of such an approach is our work on evolving cooperative behavior with neural controllers. Evolution, in this context, does not replace the work of analyzing complex social systems, but complements existing techniques of simulation, modeling, and game theory in order to lead for a new understanding of interrelations in collaborative systems. If you want to learn more, quickly come to the conference in Sao Paulo and/or check the slides below :-)

Evolution as a Tool for Understanding and Designing Collaborative Systems

Complexity on the workbench

Today’s technical systems contain more and more components which are typically networked and interacting with each other. So, these systems become very complex, which makes it difficult to engineer and maintain the system using traditional, hierarchical approaches.
Looking into complex systems in nature, we see that they are controlled by distributed self-organizing mechanisms that are simple, scalable, robust, and adaptive. However, putting a self-organizing approach into technical systems is not straightforward, because such complex systems are typically hard to predict. A particular change in an interaction mechanism might even have counter-intuitive effects.
In nature, the driving mechanism behind building self-organizing behavior is evolution - why not use the very same method in form of an evolutionary algorithm?
However, there is a need to integrate different tools and models like neural networks, mutation and recombination, and problem-specific simulations. With our tool FREVO we provide a unifying framework to reduce this problem to basically three components: a problem representation, an agent representation and an evolutionary algorithm.
FREVO has been used to solve quite different problems and is available as open source to everyone. It is a very flexible framework open to new components and simulations, thus, we are looking forward to see you testing your ideas with it :-)



This talk was given by István Fehérvári at FET 2011 in the science café. This work was supported in part by the Lakeside Labs project MESON (Modeling and Engineering of Self-Organizing Networks) and the Lakeside Labs GmbH.

Replacing the Java random generator

The Java random number generator was implemented in 1995. It is based on a linear congruential generator. Since then, there was considerable advancement in algorithms for pseudo random number generators. For most applications, Java's random number generator might be sufficient, but at a closer look, the algorithm has a fairly short period of 2⁴⁸ and fails some tests on the randomness of its output.
The good news is that there is an algorithm which is faster and better: the Xorshift algorithm. Xorshift is using a few (in the following implementation exactly three) of shift and exclusive-or operations. The best way to integrate it to Java is to make a subclass of java.util.random and to overwrite the seed variable and the next() method:

import java.util.Random;

/**
 * A subclass of java.util.random that implements the 
 * Xorshift random number generator
 */

public class XSRandom extends Random {
 private long seed;

 public XSRandom(long seed) {
  this.seed = seed;
 }

 protected int next(int nbits) {
  long x = seed;
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  seed = x;
  x &= ((1L << nbits) - 1);
  return (int) x;
 }
}

Since all methods of the Random generator (nextBoolean(), nextInt(), nextLong(), nextFloat(), nextDouble()), nextBytes(), nextGaussian()) depend on the next() method, this efficiently changes all number generation to the Xorshift algorithm.
A complete Java class including also a clone() method can be downloaded here (Code is under LGPL Version 3). Note that this implementation, unlike the java.util.Random is not exactly thread-safe - concurrent threads might access and change the seed variable inconsistently. However, note that concurrent access on the same random object would anyway end up in a nondeterminstic sequence of numbers for each thread.
This implementation is about 30% faster than the generator from java.util.random. It's output passes the Dieharder test suite with no fail and only two announced weaknesses. To use the class in legacy code, you may also instantiate an XSRandom object and assign it to a java.util.Random variable:

  java.util.Random rand = new XSRandom();

All method calls to rand are then using the newer, faster implementation.

Pseudo random number generators

In the previous post, we learned that a complex system can exhibit deterministic, but unpredictable behavior. Actually, this aspect has a strong application in computers that has been around for a long time: random number generators.
Many computer programs, like for example games or Monte Carlo simulation require a random function. Typically, a computer operating on defined binary states that only change at particular clock instants has no true randomness - its operations are deterministic. So, typically pseudo random number generators are used to generate number sequences similar to random ones.
In 1946, John von Neumann suggested such an algorithm named the middle-square method. Von Neumann's algorithm is simple: take a number as the "seed", square it, remove the middle digits of the resulting number (when viewed in decimal format) and take the remaining digits as your "random number". This number becomes also the new seed. The algorithm is fast, but statistic tests on the generated random numbers show that the distribution of numbers significantly differs from true random numbers. Worse, once the seed becomes zero, the algorithm gets stuck.
A few decades after Neumann, the programming language C came with a library function for generating random numbers using the functions rand (to pull a number) and srand (to set the seed). For generating one number, the algorithm linearly combines several terms based on constants derived from the seed. This means a higher implementation effort, but the test passes most statistical tests on randomness, such as for example are given ba the Dieharder random test suite.
The famous home computer Commodore 64 had a different algorithm for random number generation, which was simpler: The last seed is multiplied with a big number, a small number is added and the resulting number (given in a floating point format) is mixed up by switching bytes. Although the C64 algorithm was considered practically useful in a publication from Bowman, the Diehard test quickly shows a lot of deficiencies of the algorithm.
In 1997, Makoto Matsumoto and Takuji Nishimura came up with a very good algorithm, the Mersenne Twister. While this algorithm passes most of the Dieharder tests, the implementation has also grown in its complexity. For example, a common implementation of the algorithm requires an array of 624 numbers.

So - do you think now there is a tradeoff between quality of randomness and computation effort? Wrong!

The late (and great) George Marsaglia showed us a simple way to generate high quality numbers: the Xorshift algorithm.

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

The computational effort of the algorithm is obviously very low. If you chose "good" values for the three magic numbers (e.g., 21, 35, 4 as in the above example) Xorshift passes the Diehard tests. As it is the case in many complex systems, there is a simple way to control the systems behavior as intended, but is very difficult to find that simple way. In the case of pseudo random numbers it took 60 years from John von Neumann's middle-square to George Marsaglia's Xorshift.

• J. von Neumann. "Various techniques used in connection with random digits", in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12:36-38, reprinted 1951.
  
• M. Matsumoto and T. Nishimura. "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator". ACM Transactions on Modeling and Computer Simulation 8(1):3–30, 1998
  
• R. Bowman. Evaluating Pseudo-Random Number Generators. Comput. &amb; Graphics, Vol. 19, No. 2, pp. 315-324, 1995.
  
• G. Marsaglia. "Xorshift RNGs". Journal of Statistical Software Vol. 8 No. 14, 2003.
  

Langton's Ant - from simple rules to complex behavior

The following system is created using a very simple set of rules:

1. Let's assume an infinite 2D grid world. Each grid cell can be either black or white.
   
2. For simplicity, all grid cells are white at the beginning.
   
3. There is an ant, which can move up to four directions (N,E,S,W).
   
4. Whenever the ant enters a white field, it toggles the grid color and performs a clockwise (right) turn.
   
5. Whenever the ant enters a black field, it toggles the grid color and performs a counter-clockwise (left) turn.
   

You got the rules? Let's play! Get yourself some squared paper, a pencil and a rubber and start drawing. Or, if you are lazy, just use the Java applet below. Unfortunately I failed in simulating the infinite grid, so the simulation reverses whenever the ant leaves the system boundary, but this does not make a difference for the first 10000 iterations. You may use the mousewheel to scroll and modify the simulation speed in order to investigate what the ant is up to.


Despite the simple rules, the ant is following an interesting and unexpected path. This relates to what Carlos Gershenson has pointed out in his blog: a deterministic system does not necessarily mean that it is predictable. A system is deterministic if no randomness is involved in the development of future states of the system. Thus, given a particular starting condition, the system will always develop its future states in the same way. The real physical world, considering the randomness in quantum effects, is not deterministic. But the simulated ant in our example is. On the other hand, prediction means the ability to make a forecast of a system's state (either qualitatively or quantitatively). These two terms represent different concepts and should not be mixed up.

In our deterministic ant system, it is not possible to predict the behavior by looking at the rules unless you have tried out the simulation beforehand. Although we have just one agent, we face a complex system, since the agent is interacting with every single cell it arrives. And each move changes the cell and orientation, thus creates new information. The interesting and unexpected thing is what the ant is doing after roughly 10200 steps. Until then the movement is chaotic. But subsequently, the ant produces a "highway" by walking away to the south-east in repeated sequences of 104 steps. From that point on, the future system states can be predicted for all future states.
If you liked this, check out the work of Propp et al. on Langton's ants with multiple grid colors. They present a three-color model where it is not known if the ant will ever enter a stage producing a predictable highway. So far on deterministic models - in your face, predictability!

• Langton's ant@Wikipedia
  
• Gale, D.; J. Propp, S. Sutherland, S.Troubetzkoy, Further Travels with My Ant. Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56, 1995.
  
• Carlos Gershenson, Determinism != Predictability, Complexes Blog, September, 2010
  

Science beyond Fiction - A visit at FET 2011

The European Future Technologies Conference FET is a bi-annual cross-disciplinary conference for frontier research in Europe.
I visited the conference for the second time (last time in 2009 in Prague). This year in Budapest, topics covered robotics, complexity, evolutionary computation and brain research. But, the most entertaining part of this conference are always the exhibitions.
The video gives a short 2-minutes tour through the stations that impressed me the most:

In the beginning you see a cyclops bot, the ECCE1: the first of a series of anthropomimetic musculoskelal upper torsos. That means its torso is designed to look very human-like, together with the noises from the servos it gives me quite a Terminator feeling (compare it to the ending scene of Terminator 1 movie if you don't believe me). This impression is reinforced by the calculations and identification routines that run down the computer screen while the bot is focusing on you to give you a tight handshake-
Our contribution to the conference was Istváns talk on "Complexity on the workbench" in the science cafe. Istvan had 20 x 20 seconds to present his ideas, where he started with the complexity problem, lead over to possible approaches to build complex self-organizing control systems and finally introduced our framework Frevo from our project MESON as a hands-on tool to practically build such systems.

Next station is the artificial eel bot that is moving around in a water bassin. A nice example of bio-inspired engineering. Still I hope that they don't make it a tool like a colonoscope out of it - just too creepy :-)
The cooperating robots had an interesting setup - the composition of ground robots, a flying multicopter and a robot that can lift itself up a rope. In cooperation, the bots could for example find, grab and fetch a particular book from a shelf. This will save me the way to the library in the future :-)

Another bio-inpired research is on octopus limbs. The biological ones are amazing regarding their adaptibility in length and thickness and their strength. Several research group investigate how these mechanisms can be converted to a technology for robot manipulators. In the video, you can see a first prototype.

The elected winner of the exhibition, was "the future of biomimetic machines", featuring iCub, a humanoid robot used as a platform to study perception and learning processes. In the video, you can see the cute robot following and catching a ball. Considering that the winner at FET'09 was a project featuring a Nao robot, one can conclude: "cuteness wins" :-)
Neither cute nor creepy are the robots from the SYMBRION/REPLICATOR project - they are whatever you want them to be. In the video you can see several parts assembling themselves, very impressive, although the docking mechanism still needs a bit of tuning.
These have been a selection out of approximately 30 demonstrations at FET'11. If you are more interested, go an visit FET next time for yourself, see you there :-)

Open PhD Position in Complex Systems

It could be you!

We are looking for a PhD student to do research in the MESON (Modelling and Engineering of Self-Organizing Networks) project. We are a highly motivated international team of researchers situated at the Lakeside Science & Technology Park/University of Klagenfurt, Austria. We offer best work conditions, a beautiful campus with a pleasant, intercultural work environment, and a highly competitive salary.
Potential candidates should have a master's degree in computer science, computer engineering, mathematics, physics or related studies and should have skills in creative problem solving, Java programming, the use of the English language and knowledge in at least one of the following subjects:

• Complex systems, or
  
• Machine Learning, or
  
• Multi-agent systems, or
  
• Robotics
  

Research will be conducted at the Institute of Networked and Embedded Systems under the supervision of Wilfried Elmenreich. Working language is English. The institute cooperates with national and international partners from industry and academia and is part of the research cluster Lakeside Labs. Further information about the MESON project can be found on the project webpage. Women are especially encouraged to apply. Please mail applications containing a letter of interest, curriculum vitae, copies of academic certificates and courses, list of publications, and contact details of two references in a single PDF file to applications@lakeside-labs.com by deadline of Juli 31st, 2011.

Cake paradox resolved - an excursion into Game Theory

In the last posting we elaborated the cake paradox. In short, if we agree to bring in a cake on any day within the following week, Friday (the last day) is not a good choice, because then, the people can predict this already after there was no cake until Thursday. Iterating this argument we end up that no day is good for a surprise.

Actually, we need to clarify certain things in the model here. First, a situation where one is expecting a cake, but it is not brought is also a kind of surprise, though a disappointing one.
Second, if the colleagues are forced to choose one day, the odds are simply 1 out of 5 to guess the day right. Waiting until Thursday to place the bet does not help the guesser here, because in this case you have a high chance to have already lost because the cake was brought before.

However, the game becomes interesting, if the colleagues get the possibility to put a bet on a day at any time before that day but making betting optional. So if you are a cautious person, you might not bet at all, or would wait until Thursday evening, and place the sure bet in case the was not brought before. What is the best strategy for this set up?

Let's look at the payoff table for a situation where only Thursday and Friday are left, the cake has not been brought in yet and no bet was made so far. Player A has to bring in the cake, while player B tries to place the bet.

	Player A brings cake on Thursday	Player A brings cake on Friday
Player B places bet on Thursday	(-1,1) Player B guessed it right	(1,-1) Player B guessed it wrong
Player B waits and eventually places bet on Friday	(0,0) No bet was placed, game is over (because cake is there)	(-1,1) Player B guessed it right

This situation has no pure-strategy Nash Equilibrium. For the best mixed strategy, Player A should chose Thursday with a probability of 2/3, otherwise Friday. In contrast, Player B's best strategy is to bet on Friday with a probability of 2/3. The expected payoff for Player A is then -1/3, which means an advantage for B.

Now we can set up a payout table for the "Wednesday or Later" game. The "Later"-Payoff in the case that neither the cake has been brought yet nor Player B has used her bet so far is the 1/3 derived from the previous payout table.

	Player A brings cake on Wednesday	Player A brings cake later
Player B places bet on Wednesday	(-1,1) Player B guessed it right	(1,-1) Player B guessed it wrong
Player B waits	(0,0) No bet was placed, game is over (because cake is there)	(1/3,-1/3) Game defaults to previous situation

This way we can iterate the game until we end up on Monday. Assuming optimum mixed strategies, the best strategy for Player A to bring in the cake calculates to
16/31 for Monday
8/31 for Tuesday
4/31 for Wednesday
2/31 for Thursday
and 1/31 for Friday.

The guessing player has the same probabilities but increasing from 1/31 for Monday until 16/31 for Friday because the chances favor the guesser towards the end of the week. These mixed strategies establish a Nash equilibrium, thus none of the players has a benefit on changing the strategy. In overall, the game slightly favors the guesser, who is expected to win 3% more often.

Now, we earned ourselves a cake - bon appetit!

• Strategies in Game Theory@Wikipedia
  
• Nash Equilibrium@Wikipedia
  
• Unexpected hanging paradox@Wikipedia
  

The cake paradox

There will be cake today

At the institute we have a (recent) tradition to bring home-made cake for the group. Each co-worker is assigned one week within he or she can freely choose one workday to bring the cake. So the actual day when there is cake will be a surprise to the others.
Unless... there is one problem when the process is viewed from a logical perspective.
Consider me having made a cake and planning to bring it in on Friday. Friday is the last workday in the week, so the others could predict the cake to be brought on Friday as soon as they see on Thursday that there is no cake. So I will not choose Friday, because it won't be a surprise on that day.
However, assuming totally logical actors, also Thursday is not an option, since the others will come to the same conclusion that Friday is off the list and they would know on Wednesday evening, when no cake appeared so far, that I will bring it on Thursday. So Thursday is not a surprise day either. We can iterate this argument and end up with the interesting situtation that I have to bring the cake on Monday, since all other days would not be a surprise. Having decided that even Monday is no surprise either.
So it looks like that it is impossible to bring a cake on a weekday as a surprise if everybody knows that I have to bring a cake within this week.
The paradox is interesting but it is also obvious that there is a difference between totally logical and natural actors. Asking people, they usually agree on the argument that Friday would be no surprise, but every other day would be. What do you think?

If you like this kind of puzzles, I recommend the book of Zbigniew Michalewicz and his son on Puzzle-Based Learning.

Humanity is executing an evolutionary algorithm

One interesting aspect of humans is that they very strongly tend to copy the behavior of famous and admired individuals, a behavior that can also be found for our close relatives, the chimpanzees.
Actually, most of our behavior is based on previous experience and 'aping' others. There are actual very few situations where we use a pure deductive approach to solve a task. Wanna kick a curve ball? You can go for the deductive approach, but you will end up in a complicated physical air flow model. Better watch the neighbor’s boy doing it, and copy the movement.
The reason for this is that we live in a complex world, where the deductive approach usually fails because we cannot build accurate models. You want to start a business on the main street of your town? You would most likely fail trying to build an accurate economic model of your customers without taking into account the experience of people who already had a similar business in a comparable situation.
This leads us to two conclusions:
(i) Looking at whole humanity, we can see that they are executing an evolutionary algorithm, where behavior is inherited from successful individuals and modified to test new hypotheses or to adapt to new situations
(ii) Our intellectual abilities are mainly used to estimate effects of some moderate parameter changes - in evolutionary algorithms, this approach is known of modeling an approximation of the fitness landscape to reduce the number of erroneous trials
So, next time you are at a zoo, don't be too proud of your intellectual abilities - the main mechanism that lets humanity survive in a complex world is copying behavior as part of a giant evolutionary algorithm!

• Like Humans, Chimps Ape Their Betters, Healthday, 2011
  
• Chimpanzee News - Biology and Behaviour, Jane Goodall Institute of Canada, 2011
  
• Evolutionary Algorithm@Wikipedia
  

Logo turtle graphics

Logo is a venerable functional programming language (created 1967) which gained most of its popularity from the concept of Turtle Graphics: A small triangle on the screen (the turtle) being directed by simple commands like forward, backward, left, and right, each command followed by an argument giving the distance or turning angle.
In combination with the repeat command you could create beautiful drawings with a few commands. Being that simple, the turtle graphics of Logo is a nice way to teach the concept of programming to kids, possibly even pre-school.
The following animation shows a short demonstration of a browser-based Turtle Graphics interpreter aimed at introducing kids to computer programming. I extended the original program from John Villar by a few features. Feel free to click on it and create some nice drawings!

Click on this image to start Turtle Graphics in your browser

Another interesting aspect of turtle graphics is the agent-centric view: you need to specify movements and actions from the perspective of the turtle. For example, the effect of the forward command depends on the current heading of the turtle. This is fundamental different from most other programming languages where you draw on a canvas using absolute coordinates.
That such an agent-centric view is beneficial for modeling self-organizing systems has also been shown by the agent-based simulation language StarLogo, which is a multi-agent extension of Logo. If you are interested to use turtle graphics in education on multi-agent and decentralized systems, have a look at StarLogo.

• JSTurtlegraphics in your browser
  
• Download JSTurtlegraphics V0.3 (under GPLv3 license)
  
• StarLogo Homepage
  

Lakeside Research Days 2011: Applications of self-organization in technology

The concept and theory of complex systems and self-organization has been researched for several decades and yielded many publications. Scientists claim self-organization to be the new paradigm to cope with the emerging complexity of networked applications. However, the claimed paradigm change has not yet shown a very great impact so far. Typical applications which are claimed to implement and build on self-organization are often built by experts from the respective domain such as computer networks, wireless communications, sensor networks, etc. without generality that holds also for other domains. On the other hand, research and development on applications of self-organization have the potential to provide results across the particular domain borders. In order to enable this potential, there is a need to move the application area of self-organizing systems more towards the center of complex systems research. In other words, complex systems researcher need to learn how to apply their results and domain specific researchers need to learn more about the general aspects of self-organization. At the Research Days 2011, a group of internal researchers will discuss how this translation between complex systems theory, domain-specific theory, and practical application can be achieved.

The Research Days are an annual event concentrating on the core competence of Lakeside Labs - Self-organizing Networked Systems. During this workshop organized by Lakeside Labs GmbH in cooperation with the University of Klagenfurt, international experts devote themselves to a special topic in self-organization. The event is organized as a five days workshop in July. It takes place at Lakeside Labs in Klagenfurt am Wörthersee, Austria, near a beautiful lake and Alps scenery. Invited experts, local professors, and young researchers discuss and elaborate ideas in the field of Self-Organizing Systems (SOS). The main emphasis of the workshop is on soliciting discussions and creating new ideas regarding a topic related to self-organizing systems. The event greatly supports scientific exchange, networking, establishment of international collaborations, and joint research projects.
The following video gives a nice impression of the Research Days:



The Research Days 2011 will take place in the week of July 11-15, 2011. Please visit http://researchdays.lakeside-labs.com for further information.

iBraitenberg

Braitenberg robot approaching a light source

A Braitenberg vehicle is a simple robot that is able to show interesting complex behavior. The main feature of a Braitenberg vehicle is that it lacks a complex controller but instead directly connects the sensors' output to some actuators' input. That way, a two-wheeled vehicle can, e.g. be told to approach or to flee from an object detected by the sensors. Dominik Egarter has build a nice Braitenberg vehicle using Lego mindstorms. To be exact, it is a Braitenberg emulator contained in the Lego Mindtstorms controller brick. The interesting feature is that the vehicle can be configured via a nice iPhone app. The iBraitenberg app is a useful demonstrator to introduce robotics to pupils. We presented the work at an open lab day at the university, where the project attracted a lot of people, among them several kids.


Movie explaining the vehicle and demonstrating the iBraitenberg app.

• Sourcecode for the iBraitenberg application
  
• Braitenberg vehicle explanation@Wikipedia
  

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?

• W. Elmenreich and I. Fehérvári. Evolving self-organizing cellular automata based on neural network genotypes. In C. Bettstetter, C. Gershenson, editor, Proceedings of the Fifth International Workshop on Self-Organizing Systems, pages 16–25. Springer Verlag, 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.

• H. Lindner, Self-organized Positioning of Mobile Relays, Poster at Fifth International Workshop on Self-Organizing Systems (IWSOS 2011), Karlsruhe, Germany, 2011.
  
• Evolution Strategy@Wikipedia
  
• MESON (Modeling and Engineering of Self-Organizing Networks) - Research Project funded by Lakeside Labs
  

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.

• Project page about Mozart meets Darwin experiment
• Android App: Mozart meets Darwin (needs Android Version 2.2 or above)
• www.demesos.tk - Our research project (funded by Lakeside Labs)