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

The Symposium on Self-* Systems – Biological Foundations and Technological Applications was part of the European Meeting on Cybernetics and Systems Research (EMCSR 2012) taking place from April 10-13 in Vienna, Austria. It was organized by Vesna Sesum-Cavic, Carlos Gershenson and Wilfried Elmenreich.

Tomonori Hasegawa presented insights on the self-referential logic of self-reproduction originally formulated by John von Neumann and introduced an implementation of this abstract architecture embedded within the Avida world [1]. In the experiments, a sophisticated von Neumann Self-Referential Machine, which was introduced as seeding mechanism, can degrade to a mere copy machine that has dropped the self-referential part. Thus, with this particular implementation, in this particular world, the von Neumann architecture proves to be evolutionarily unstable and degenerates, surprisingly easily, to a primitive, non-self-referential, “copying” or “template replication”, mode of reproduction
Questions arose if a von Neumann Self-Referential Machine could evolve from a simple self-copy machine in a different set-up. The von Neumann model has the advantage of enabling new and more ways to change the system upon mutation - but what could be the evolutionary pressure to have a von Neumann architecture evolved in the first place?
Current experiments did not include sexual reproduction - could that facilitate the evolution of more complex architectures?
More from the group can be found at http://evosym.rince.ie/

Modern software systems suffer from increased complexity. Large software systems are composed of many components that are interlinked. The internal states of these systems contain a huge amount of information. The main obstacles lie in the lack of the reliability and robustness which lead to poor performance. For complex intractable problems, a random search (Monte-Carlo method) does not perform well. New and advanced approaches are necessary to deal with complexity.
Milan Tuba proposed a guided Monte-Carlo search method based on a hybrid of reinforcement learning and a genetic algorithm[2]. As a proof-of-concept the approach is applied to the problem of information retrieval in the internet.
In the discussion, the performance of the algorithm in comparison to commercial search providers, like Google, was discussed.

Sander van Splunter presented ideas on the coordination and self-organization in crisis management[3]. The main idea is to move from a task-oriented top down approach towards an emergence-oriented bottom-up approach, while keeping, a hierarchical structure. However, higher level entities control lower levels by policy, not directly. Policy defines interaction, prioritization and coordination of entities.
An entity works as an independent agent following the given policies. An important feature could be the ability to predict the failure in a given subsystem.
According to EMCSR'12 keynote lecture of Peter Csermely we have to watch signs like slower recovery, increased self-similarity, and increased variance of fluctuation patterns in order to predict a system change into a state where it cannot handle the its environment with its current policies.
In the proposed crisis management of van Splunter and van Veelen a subsystem is supposed to emerge a warning when local adaption fails to handle the problem, e.g. if a small team of firefighters cannot confine a fire in their assigned area.

Carlos Gershenson told us about "Living in living cities"[4]. One of the challenges of 21st century is preventing the problems in the ultra-fast growing cities all over the world.
These are non-stationary (changing problems), traditional algorithms do not work well. Such challenges are for example urban mobility, logistics, telecommunications, governance, safety, sustainability, society and culture. A solution is to exploit properties of living systems, which are adaptive, learning, evolving, robust, autonomous, self-repairing, and self-reproducing, and to understand cities metaphorically as organisms.
Engineering methods cannot find a single solution to these changing problems. Instead it is necessary to constantly adapt the solution, thus have a self-organizing solution to a complex problem. Will cities become the "killer app" of cybernetics and systems research?
Discussion arose around the following issues:
But how do you get the officers and responsibles of a city to cooperate? There is a need for a strong motivation to overcome the inertia of the system.
Could cities instead built from scratch? No, because of the legacy issues - it is not possible to just tear down a large city and build it anew every few decades.
Can we prove that the system is robust against malicious behavior? Difficult since such a complex system cannot be easily predicted for all sets of possible inputs.
Are explicit measures necessary or would people themselves care for the necessary adaptations? This would not increase living standard for the people.

Anita Sobe presented ideas on self-organizing content sharing at social events by such interesting examples as the marriage of Kate and William of Windsor or Barack Obama's inauguration[5].
The presented approach allows people to share their self-generated content like photos or short videos instantly at such events. Existing platforms like flickr or youtube do not provide this liveness since most content is uploaded with a few days delay. The proposed approach organizes the content using an artificial hormone system. The hormone distribution is sensitive to the quality of a network connection and therefore, reflects a quality-of-service for a network path. The system is solely based on local decisions for forwarding, replicating and moving content. Over time, the content distribution in the network gets optimized in order to support short response times for requesters. Simulations show that the system competes well to other epidemic information dissemination methods such as Gossip.
The follow-up discussion brought up interesting questions:
How is overhead reflected in the simulation? Currently overhead is implicitly modeled into the transmission cost, which is valid for a constant packet handling overhead.
Furthermore the relation of the hormone-based approach to an ant colony optimization (ACO) algorithm was discussed. We identified a major difference to ACO, since there typically either the network or the content is assumed to be static. However ACO could be extended to handle the described scenario, which might inspire future work.
What is the effect, if tags are (more) complex? The system was started with a predefined tag hierarchy which can be extended to a more complex tag hierarchy. However, with more complex tags there is no guarantee for finding content.

In the last talk, Wilfried Elmenreich gave a talk on evolving a distributed control algorithm for flying UAV drones for a coverage problem[6]. The problem of having multiple mobile agents covering (or as we say in robotics, "sweeping") an area is relevant for many applications like lawn mowing, snow removal, floor cleaning,  environmental monitoring, communication assistance and several military and security applications.
The work by Istvan Fehervari, Wilfried Elmenreich and Evsen Yanmaz described a simple grid-based abstraction of the problem which was used to test two evolved and one handcrafted control algorithm which were compared to  reference algorithms like random walk and random direction.
A short summary of Wilfried's talk and the slides are available here.
The talk triggered interesting discussion involving the comparison with the “belief-based” algorithm. A further question triggering future work is on the influence on the layout and number of sensors. What will happen if the environment changes? Since the algorithm has no memory of a map, a changing environment does not affect the result.

References

1. B. McMullin, T. Hasegawa. Von Neumann Redux: Revisiting the Self-referential Logic of Machine Reproduction Using the Avida World. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.
2. V. Sesum-Cavic, M. Tuba, and S. Rankow. The Influence of Self-Organization on Reducing Complexity in Information Retrieval. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.
3. S. van Splunter, B. van Veelen. Coordination and Self-Organisation in Crisis Management. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.
4. C. Gershenson. Living in Living Cities. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.
5. A. Sobe, W. Elmenreich, and M. del Fabro. Self-organizing content sharing at social events. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.
6. I. Fehérvári, W. Elmenreich, and E. Yanmaz. Evolving a team of self-organizing UAVs to address spatial coverage problems. In R. M. Bichler, S. Blachfellner, and W. Hofkirchner, editors, European Meeting on Cybernetics and Systems Research Book of Abstracts, Vienna, Austria, April 2012.

Evolving a Team of Self-organizing UAVs to Address Spatial Coverage Problems

Typical small UAV (AscTec Pelican)

Coordinating a team of agents, which could be a search team, cleaning robots, flying drones for surveillance or environmental monitoring is a highly relevant problem. If the environment is unknown or subject to change, an a priori planning algorithm becomes difficult to apply. Therefore we looked into decentralized self-organizing algorithms to do the job.
In a joint work with István Fehérvári, Evsen Yanmaz and Wilfried Elmenreich (me), we evolve controllers for a team of unmanned aerial vehicles (UAVs) with the task to observe or cover a partially obstructed area.
The respective agents are limited in their sensory inputs to local observations of the environment without the ability to determine their absolute position or those of others. Each agent is equipped with a number of sensors that can detect the presence of other agents, an obstacle and the border of the area.

Simulation and evaluation model

The controller of an agent is implemented as an artificial neural network. The fitness for a given configuration is derived from the average spatial coverage over several simulation runs. The area coverage performance of the evolved controllers with different number of sensors is compared to reference movement models like random walk, random direction, and an algorithm based on the belief of the intention of agents met during the execution of the simulation. Our results show that evolved controllers can create a self-organizing cooperating team of agents that exploit the advantages provided by their sensors and outperform naïve coverage algorithms and also reach the performance of a recent algorithm that is using additional information as well.

The work was presented in a talk at the European Meeting on Cybernetics and Systems Research (EMCSR 2012) in Vienna, Austria. Slides are available via slideshare:

Evolving a Team of Self-organizing UAVs to Address Spatial Coverage Problems from Wilfried Elmenreich

View more presentations from Wilfried Elmenreich.

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

 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

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.