Self-Organizing Networked Systems

6th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2012)

2012-01-18T08:54:00.003+01:00

 CALL FOR PAPERS
6th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2012)
Lyon, France
10-14 September 2012
http://saso2012.univ-lyon1.fr

Important Dates
******************
Abstract submission: April 23rd, 2012
Full paper submission: April 30rd, 2012
Notification of acceptance : June 20th, 2012

Introduction
*************
The aim of the SASO conference series is to provide a forum for presenting the latest results about self-adaptive and self-organizing systems, networks and services. To this end, the meeting aims to attract participants with different backgrounds, to foster cross-pollination between research fields, to expose and discuss innovative theories, frameworks, methodologies, tools, and applications, and to identify new challenges. The complexity of current and emerging computing systems has led the software engineering, distributed systems and management communities to look for inspiration in diverse fields (e.g., complex systems, control theory, artificial intelligence, sociology, biology, etc.) to find new ways of designing and managing networks, systems and services. In this endeavor, self-organization and self-adaptation have emerged as two promising interrelated facets of a paradigm shift.

Self-adaptive systems work in a top down manner. They evaluate their own global behavior and change it when the evaluation indicates that they are not accomplishing what they were intended to do, or when better function or performance is possible. A challenge is often to identify how to change specific behaviors to achieve the desired improvement. Self-organizing systems work bottom up. They are composed of a large number of components that interact locally according to typically simple rules. The global behavior of the system emerges from these local interactions. Here, a challenge is often to predict and control the resulting global behavior.

Topics of Interest
*******************
The SASO conference is interested in both theoretical and practical aspects of systems exhibiting self-* characteristics. A particular focus is the modeling of natural, man-made and social systems that exhibit self-adaptation and self-organization characteristics as well as the constructive use of the underlying basic principles in technical systems. The sixth edition of SASO particularly encourages submissions from the following, non-exclusive list of topic areas:

- Principles, Theory, Methods and Architectures for SASO Systems
- Robustness, Resilience and Fault-Tolerance in/with Self-* Systems
- Self-* Behavior in Communication Networks
- (Self-)Control, (Self-)Observation, (Self-)Monitoring of Engineered Systems
- Collective Phenomena in Social and Socio-Technical Systems
- Self-Organization and Self-Adaptation in Biological/Natural Systems
- Applications of Spatial and Physics-Inspired Self-Organization
- SASO Principles in Cyber-Security
- SASO Principles in Collective Robotic Systems
- SASO Principles in Cyber-Physical Systems
- Real-World Experience with Engineered Systems Exhibiting Self-* Properties

All contributions must present novel theoretical or experimental results, or practical approaches and experiences in building or deploying real-world systems and applications. Contributions that contrast "conventional" engineering principles with novel approaches making use of SASO principles are especially welcome.

Submissions Instructions
****************************
All submissions should be 10 pages and formatted according to the IEEE Computer Society Press proceedings style guide and submitted electronically in PDF format. Please register as authors and submit your papers using the SASO 2012 conference management system. The proceedings will be published by IEEE Computer Society Press, and made available as a part of the IEEE digital library. Note that a separate call for poster and demo submissions has also been issued.

Emerging Topic Papers
**************************
In addition to regular papers, SASO also encourages the submission of papers on emerging topics. These submissions should be clearly marked as such (indicating "Emerging Topic:" in the title) and should provide a well-rounded survey of novel questions, methods and abstractions that are relevant for the design of SASO systems along with a clear indication of the possible impact on the SASO community. In this category we particularly encourage submissions that present innovative applications of methodological frameworks being used in other fields of science that study SASO related phenomena, thus highlighting connections and potential for collaboration between different scientific communities.

Review Criteria
*****************
Papers should present novel ideas in the topic domains listed above, clearly motivated by problems from current practice or applied research. We expect claims of contribution to be clearly stated and substantiated by formal analysis, experimental evaluations or comparative studies. Appropriate references must be made to related work. Since SASO is a cross-disciplinary conference, a particular criterion that will be strictly enforced by the program committee is that all papers must be understandable by researchers that are not members of the particular, highly-specialize scientific community. Emphasis should rather be placed on cross-cutting aspects that are relevant to a wider audience of researchers and engineers dealing with SASO systems. Furthermore, submissions making use of principles inspired by phenomena occurring in fields like biology, physics, sociology, economics, etc. are required to provide references for all relevant work in the respective field. Papers demonstr
ating SASO principles in practical applications are expected to provide an indication of the real world relevance of the problem that is solved, including some form of evaluation of performance, usability, or superiority to alternative state-of-the-art approaches. If the application is still early work in progress, then the authors are expected to provide strong arguments as to why the proposed approach will work in the chosen domain.

The program committee strongly suggests to review the list of common reasons for SASO submissions being rejected, which is available online. Furthermore, a collection of interdisciplinary approaches to the study of SASO-related phenomena is provided. Prospective authors are invited to check whether their research question can be related to this rich body of work, thus benefiting from tools, methods and findings developed in various disciplines.

Technical Meeting Committee
********************************
General chairs
Salima Hassas, Universite Claude Bernard-Lyon 1, France
Paul Robertson, DOLL, USA

PC chairs
Anwitaman Datta (Distributed Systems), NTU, Singapore
Marie-Pierre Gleizes (Self-organization), Universite de Toulouse, France
Ingo Scholtes (Socio-tecnical Systems), ETH Zurich, Switzerland

Local chair
Gauthier Picard, Ecole Nationale Superieure des Mines de Saint-Etienne

Finance chair
Frederic Armetta, Universite Claude Bernard-Lyon 1, France

Poster chair
Stefan Dulman, Univ. Delft, Netherlands

Contest and Demos track Chairs
Olivier Simonin, LORIA, France 

Antonio Coronato, ICAR-CNR, Italy

Workshop chair
Jeremy Pitt, Imperial College London, UK

Tutorial chair
Giuseppe (Peppo) Valetto, Drexel University, USA

Publicity chair
Jose Luis Fernandez-Marquez, Univ. Geneva, Switzerland
Zhang Jie, Univ. Singapore, Singapore
Sam Malek, George Mason Univ., Fairfax, USA

Publication chair
Sven Brueckner, Jacobs Technology Inc., USA

Sponsor chair
Bob Laddaga, DOLL, USA

Web and Wiki chair
Haytham El Ghazel, Universite Claude Bernard-Lyon 1, France

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

2011-12-05T22:53:00.003+01:00

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

2011-10-16T19:37:00.005+02:00

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

2011-09-27T00:05:00.001+02:00

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

2011-09-22T01:50:00.011+02:00

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

2011-09-20T01:40:00.007+02:00

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

2011-09-07T23:44:00.007+02:00

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

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

2011-08-11T23:23:00.005+02:00

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

2011-06-16T15:07:00.000+02:00

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

2011-05-28T23:47:00.003+02:00

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 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 favorizes the guesser, who is expected to win 3% more often.

Now, we earned ourselves a cake - bon appetit!

The cake paradox

2011-05-17T09:43:00.004+02:00

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

2011-04-28T18:18:00.005+02:00

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

2011-04-08T23:59:00.004+02:00

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.

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

2011-04-07T22:38:00.004+02:00

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

2011-04-01T09:21:00.006+02:00

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.

Evolving a cellular automaton with neural controllers

2011-03-29T22:50:00.007+02:00

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

2011-03-11T22:48:00.001+01:00

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

2011-01-28T14:52:00.003+01:00

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)

So when do we call a system self-organizing?

2010-11-24T23:17:00.007+01:00

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!

C. Gershenson, F. Heylighen. When Can we Call a System Self-organizing? In Banzhaf, W, T. Christaller, P. Dittrich, J. T. Kim, and J. Ziegler, Advances in Artificial Life, 7th European Conference, ECAL 2003, Dortmund, Germany, pp. 606-614. LNAI 2801. Springer.
W. Elmenreich, H. de Meer. Self-organizing networked systems for technical applications: A discussion on open issues. In J.P.G. Sterbenz. K.A. Hummel, editor, Proceedings of the Third International Workshop on Self-Organizing Systems, pages 1–9. Springer Verlag, 2008.

A self-organizing algorithm for video distribution networks

2010-11-11T21:03:00.011+01:00

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.

A. Sobe, W. Elmenreich, and L. Böszörmenyi. Towards a Self-Organizing Replication Model for Non-Sequential Media Access ACM Multimedia 2010 Workshop - Social, Adaptive and Personalized Multimedia Interaction and Access, SAPMIA 2010
videonetwork - A simulator for self-organizing video replication and delivery @ Google Code
Self Organizing Multimedia Architecture - A Lakeside Labs Research Project

Mozart meets Darwin - Creating music by evolution

2010-11-05T12:38:00.005+01:00

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.

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.

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

2010-10-17T22:15:00.003+02:00

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!

A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki, R. Kobayashi, and T. NakagakiRules for Biologically Inspired Adaptive Network Design, Science 22 January 2010, Vol. 327. no. 5964, pp. 439 - 442.
K. Harmon, Slime mold validates efficiency of Tokyo rail network Scientific American Observations Blog, Jan, 2010.
The Ig® Nobel Prizes

Maxis' forgotten game

2010-09-21T23:27:00.008+02:00

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.

DOSBox, an x86 emulator with DOS
Simlife@Wikipedia

Evolving cooperative behavior with neural controllers

2010-09-05T22:22:00.007+02:00

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.

I. Fehérvári and W. Elmenreich. Towards evolving cooperative behavior with neural controllers.In IFIP Fourth International Workshop on Self-Organizing Systems, 2009.
Public Goods Game@Wikipedia
Prisoner's Dilemma@Wikipedia
FREVO - a tool for engineering self-organizing systems
Our project DEMESOS

Prisoner's Dilemma at the swimming pool

2010-08-31T00:01:00.001+02:00

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.

Self-organizing music

2010-08-19T21:42:00.000+02:00

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.

Evolving a self-organizing soccer team

2010-08-07T22:20:00.002+02:00

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.

I. Fehérvári and W. Elmenreich. Evolving neural network controllers for a team of self-organizing robots. Journal of Robotics, 2010.
The DEMESOS project www.demesos.tk
Software used for the evolutionary algorithm: FREVO www.frevotool.tk

Sometimes, self-organizing systems fail

2010-08-04T15:23:00.001+02:00

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

2010-08-04T15:15:00.000+02:00

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

2010-08-04T14:03:00.000+02:00

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

2010-08-04T13:58:00.000+02:00

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)
110 INPUT"ENTER RULE NUMBER";R
120 N=1
130 FOR I=1 TO 8
140 IF R AND N THEN K(I)=1
150 N=N*2
160 NEXT
170 INPUT"USE RANDOM LINE AS SEED";A$:RN=0:IF A$="Y" THEN RN=1
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

2010-08-04T13:50:00.000+02:00

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 http://wwwu.uni-klu.ac.at/welmenre/papers/fehervari-2009-evolutionary-methods-in-self-organizing-system-design.pdf).
FREVO is released under the GPL open source license. The framework, some sample components, and a tutorial can be accessed at the project webpage http://www.frevotool.tk.

Self-organizing systems can solve real-world problems

2010-08-04T13:48:00.000+02:00

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 http://wiki.openstreetmap.org/wiki/WikiProject_Haiti). 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

2010-08-04T13:47:00.000+02:00

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

2010-08-04T13:41:00.004+02:00

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

2010-08-04T13:39:00.000+02:00

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

2010-08-04T13:37:00.000+02:00

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 conlude, 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 excactly 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 miniatur 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!

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

2010-08-04T13:36:00.000+02:00

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