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, (@ 
)
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
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.
