Carlos Gershenson's homepage


S-O.S

Self-organizing Systems

 

If you are searching for an introduction to Self-organizing Systems, probably the best place to begin is at Principia Cybernetica.

My work on self-organizing systems is summarized in my PhD thesis. Particular papers are listed below.

  • Gershenson, C. (2007). Design and Control of Self-organizing Systems. PhD Thesis. Vrije Universiteit Brussel. [pdf]

  • Abstract: Complex systems are usually difficult to design and control. There are several particular methods for coping with complexity, but there is no general approach to build complex systems. In this thesis I propose a methodology to aid engineers in the design and control of complex systems. This is based on the description of systems as self-organizing. Starting from the agent metaphor, the methodology proposes a conceptual framework and a series of steps to follow to find proper mechanisms that will promote elements to find solutions by actively interacting among themselves. The main premise of the methodology claims that reducing the “friction” of interactions between elements of a system will result in a higher “satisfaction” of the system, i.e. better performance.

    A general introduction to complex thinking is given, since designing self-organizing systems requires a non-classical thought, while practical notions of complexity and self-organization are put forward. To illustrate the methodology, I present three case studies. Self-organizing traffic light controllers are proposed and studied with multi-agent simulations, outperforming traditional methods. Methods for improving communication within self-organizing bureaucracies are advanced, introducing a simple computational model to illustrate the benefits of self-organization. In the last case study, requirements for self-organizing artifacts in an ambient intelligence scenario are discussed. Philosophical implications of the conceptual framework are also put forward.

  • Gershenson, C. and F. Heylighen (2003). 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.

  • Abstract: We do not attempt to provide yet another definition of self-organizing systems, nor review previous definitions. We explore the conditions necessary to describe self-organizing systems, inspired on decades of their study, in order to understand them better. These involve the dynamics of the system, and the purpose, boundaries, and description level chosen by an observer. We show how, changing the level or ?graining? of description, the same system can be self-organizing or not. We also discuss common problems we face when studying self-organizing systems. We analyse when building, designing, and controlling artificial self-organizing systems is useful. We state that self-organization is a way of observing systems, not a class of systems.

     

  • Heylighen, F. and C. Gershenson (2003). The Meaning of Self-organization in Computing. IEEE Intelligent Systems, section Trends & Controversies - Self-organization and Information Systems, July/August 2003, pp. 72-75.
  •  

  • Gershenson, C. and F. Heylighen (2004). Protocol Requirements for Self-organizing Artifacts: Towards an Ambient Intelligence To be published in Proceedings of International Conference on Complex Systems ICCS2004. Also AI-Lab Memo 04-04.

  • Abstract: We discuss which properties common-use artifacts should have to collaborate without human intervention. We conceive how devices, such as mobile phones, PDAs, and home appliances, could be seamlessly integrated to provide an "ambient intelligence" that responds to the users desires without requiring explicit programming or commands. While the hardware and software technology to build such systems already exists, yet there is no protocol to direct and give meaning to their interactions. We propose the first steps in the development of such a protocol, which would need to be adaptive, extensible, and open to the community, while promoting self-organization. We argue that devices, interacting through "game-like" moves, can learn to agree about how to communicate, with whom to cooperate, and how to delegate and coordinate specialized tasks. Like this, they may evolve distributed cognition or collective intelligence able to tackle any complex of tasks.

    This work has been featured in: TRN.

     

  • Gershenson, C. (2005). Self-Organizing Traffic Lights. Complex Systems 16(1): 29-53. [preprint]

  • Abstract: Steering traffic in cities is a very complex task, since improving efficiency involves the coordination of many actors. Traditional approaches attempt to optimize traffic lights for a particular density and configuration of traffic. The disadvantage of this lies in the fact that traffic densities and configurations change constantly. Traffic seems to be an adaptation problem rather than an optimization problem. We propose a simple and feasible alternative, in which traffic lights self-organize to improve traffic flow. We use a multi-agent simulation to study three self-organizing methods, which are able to outperform traditional rigid and adaptive methods. Using simple rules and no direct communication, traffic lights are able to self-organize and adapt to changing traffic conditions, reducing waiting times, number of stopped cars, and increasing average speeds.

    Try the simulation with your Java-enabled browser. You can find there also the source code of it, to be used with NetLogo.

    This work has been featured in: News @ Nature 2004/12/03. doi: 10.1038/news041129-12; TRN; ACM TechNews 7(747); Trends; De Tijd 2004/12/13, p. 17.; Science & Vie 1049, Février 2005, p. 32; Bayerischer Rundfunk, Berliner Morgenpost, Wienweb.at, Pagina 12, Le peuple des connecteurs.

     

  • Gershenson, C. (2006). A General Methodology for Designing Self-Organizing Systems. ECCO working paper 2005-05.

  • Abstract: Our technologies complexify our environments. Thus, new technologies need to deal with more and more complexity. Several efforts have been made to deal with this complexity using the concept of self-organization. However, in order to promote its use and understanding, we must first have a pragmatic understanding of complexity and self-organization. This paper presents a conceptual framework for speaking about self-organizing systems. The aim is to provide a methodology useful for designing and controlling systems developed to solve complex problems. First, practical notions of complexity and self-organization are given. Then, starting from the agent metaphor, a conceptual framework is presented. This provides formal ways of speaking about "satisfaction" of elements and systems. The main premise of the methodology claims that reducing the "friction" or "interference" of interactions between elements of a system will result in a higher "satisfaction" of the system, i.e. better performance. The methodology discusses different ways in which this can be achieved. A case study on self-organizing traffic lights illustrates the ideas presented in the paper.

    I presented this work as an invited talk at the Multi-Agent Systems session of the CSS'05 Conference in Liverpool, September 14th, 2005. Video Summary 2:40 [asf: 3.1 Mb]. Full talk Audio 38:30 [mp3: 64Kbps, 17.6 Mb] Slides [pdf].

    This work was featured in Complexity 11(1):4.

     

  • Gershenson, C. (2008). Towards Self-Organizing Bureaucracies, International Journal of Public Information Systems, 2008(1):1-24.

  • Abstract: The goal of this paper is to contribute to eGovernment efforts, encouraging the use of self-organization as a method to improve the efficiency and adaptability of bureaucracies and similar social systems. Bureaucracies are described as networks of agents, where the main design principle is to reduce local "friction" to increase local and global "satisfaction". Following this principle, solutions are proposed for improving communication within bureaucracies, sensing public satisfaction, dynamic modification of hierarchies, and contextualization of procedures. Each of these reduces friction between agents (internal or external), increasing the efficiency of bureaucracies. Current technologies can be applied for this end. "Random agent networks" (RANs), novel computational models, are introduced to illustrate the benefits of self-organizing bureaucracies. Simulations show that only few changes are required to reach near-optimal performance, potentially adapting quickly and effectively to shifts in demand.

    Try or download (source code included) Random Agent Networks software, (@ SourceForge.net Logo)

    RAN dynamics

    Dynamics for a random agent network of N=25, K=5 with homogeneous topology for 200 time steps. a) Response delays. b) Queue lengths. 

  • Cools, S.-B., C. Gershenson, and B. D'Hooghe (2007). Self-organizing traffic lights: A realistic simulation In Prokopenko, M. (Ed.) Self-Organization: Applied Multi-Agent Systems, Chapter 3, pp. 41-49. Springer, London.

  • Abstract: We have previously shown in an abstract simulation (Gershenson, 2005) that self-organizing traffic lights can improve greatly traffic flow for any density. In this paper, we extend these results to a realistic setting, implementing self-organizing traffic lights in an advanced traffic simulator using real data from a Brussels avenue. On average, for different traffic densities, travel waiting times are reduced by 50% compared to the current green wave method.

    This work has been featured in Discovery News and Complexity 12(4):6

    Wetstraat simulation

    SOTraCon

  • Gershenson, C. (2003). Self-organizing Traffic Control: First Results Unpublished.

  • Abstract: We developed a virtual laboratory for traffic control where agents use different strategies in order to self-organize on the road. We present our first results where we compare the performance and behaviour promoted by environmental constrains and five different simple strategies: three inspired in flocking behaviour, one selfish, and one inspired in the minority game. Experiments are presented for comparing the strategies. Different issues are discussed, such as the important role of environmental constrains and the emergence of traffic lanes.

    The precise data and clearer graphs of this work can be found here.

    You can also download the virtual laboratory SOTraCon version 1.0. See the README.

         


    Carlos Gershenson's homepage