What is self-organization?
Ashby \cite{Ashby1947sos} coined the term "self-organizing system" to describe phenomena where local interactions lead to global behaviors or patterns. Common examples are found in collective motion \citep*{Vicsek2012} and pattern formation \citep*{Cross1993}. However, as Ashby already noted, we only have to call an attractor of a system "organized" to say that it self-organizes though its dynamics. It simply goes to its most probable state. To define it properly, we run into the difficulties of agreeing on what a system is, what is organization, and what is self \citep*{GershensonHeylighen2003a}.
We can understand a self-organizing system as one in which the organization increases in time. However, it can be shown that depending on how the variables of a system are chosen, the same system can be said to be organizing or disorganizing \citep*{Gershenson2003}. Moreover, in several examples all elements have equal agency, and the system behavior is the outcome only of those interactions, so it is not straightforward to identify the self of the system. Finally, in cybernetics and systems theory the dependency of the boundaries of a system on the observer has thoroughly been discussed \citep{Gershenson2013The-Past-Presen}: one wants to have an objective description of phenomena, but descriptions are necessarily made by observers, making them partially subjective.
Hence, in discussing self-organisation, one has to identify what is self and what is other, which is the first step to define what a living system is according to the tradition of \citet*{Maturana_1980}. A living system is inherently self-organising because the self is continuously produced/renewed by processes brought forth by the systems internal components. In other words, according to \citet{Varela_1974}, a system can be recognised as a unity with
boundaries that encompass a number of elementary components, which at the basis of the organisation of the system, as they are responsible
for the definition of the system boundaries and for the (re)production of
the very same components. So, if self-organisation is so deeply linked with living systems, it is clear that also Artificial Life must be strongly influenced.
Being pragmatic, we can better decide when is it useful to describe a system as self-organizing \cite{GershensonDCSOS}. This is usually when we are interested on more than one scale of a phenomena and on how the lower scale produces the observables at the higher scale, as well as how the higher scale constrains and promotes observables at the lower scale. For example, how bird behavior leads to flock formation, and how the flock regulates the bird behavior.
Self-organization has been an important concept for several disciplines, such as. statistical mechanics \citep{Wolfram1983,Crutchfield2011}, supramolecular chemistry \citep{Lehn2017}, and computer science \citep{mamei2006case}. Artificial life has exploited self-organizing systems in different contexts \citep{Aguilar2014The-Past-Presen}, already from early examples of snowflakes \citep*{Packard1986} and boids \cite{reynolds87flocks}. In this work, we aim at reviewing and classifying the relationship between self-organization and artificial life. In the next section, ***
Definitions
Ashby coined the term self-organizing system to show that a machine could be strictly determinate and yet exhibit a self-induced change of organization \citep{Ashby1947}. This notion was further developed within cybernetics \cite{vonFoerster1960,Ashby1962}.
In many contexts, a thermodynamical perspective has been taken, where organization can be seen as the opposite of entropy \citep*{NicolisPrigogine1977}. Since there is an equivalence between Boltzmann-Gibbs entropy and Shannon information, this notion has also been applied in contexts related to information theory \citep{Fernandez2013Information-Mea}.
However, there are several other definitions of self-organization. For example, Shalizi defines self-organization as an increase in statistical complexity, which in turn is defined as the amount of information required to minimally specify the state of its causal architecture \citep*{Shalizi2001}. As an alternative to entropy, the use of the mean value of random variables has also been proposed \citep*{Holzer:2011}.
The recent field of guided self-organization explores mechanisms by which self-organization, which tends to have its own dynamics, can be regulated for specific purposes \citep{Prokopenko:2009,Ay2012Guided-self-org,GSO2013,GSOInception2014,ProkopenkoGershenson2014}. Most of this research is based on information theory. For example, the self-organization of random Boolean networks \citep{Kauffman1969,Kauffman1993} can be guided to specific dynamical regimes \citep*{Gershenson:2010}., The concept of self-organization is also heavily used in organization science, relevant to artificial society models \citep{gilbert1995artificial,EpsteinAxtell1996}.
Even when there is no agreed definition of self-organization, this is not an obstacle for studying it. Well, a lack of an agreed definition of "life" has not been an obstacle for biology nor ALife.
Domains
Artificial life can be divided into soft, hard, and wet, roughly referring to computer simulations, physical robots, and protocell research, respectively. We can also include living technology as the application of artificial life \citep{Bedau:2009}. Self-organization has been relevant for all ALife domains.
Soft ALife
Soft ALife, or mathematical/computational modeling and simulation of life-like behaviors, have been strongly linked to self-organization. Cellular automata (\citealp{Ilachinski_2001}), one of the most popular modeling frameworks used in earlier forms of soft ALife, are well-explored, illustrative examples of self-organizing systems. Each cell (dynamical unit) in cellular automata determines its next state in a fully distributed manner, using a state-transition function of its current states and its neighbors'. With no explicit central controller involved, cellular automata can spontaneously organize their state configurations to demonstrate various forms of self-organization, such as dynamical critical states seen in e.g. sand-pile models (\citealp{Bak_1988}) and in the Game of Life (\citealp{Bak_1989}), spontaneous formation of spatial patterns (\citealp{Young_1984}; \citealp{Wolfram_1984}; \citealp{Ermentrout_1993}), and most importantly to ALife, self-replication (\citealp{Langton_1984}; \citealp{Langton_1986}; \citealp{Reggia_1993}; \citealp{Sipper_1998}) (***footnote: Note that the earlier literature on self-reproducing cellular automata (\citealp{burks1966}; \citealp{Codd_1968}) is not included here, because those models typically had a clear separation between a central universal controller and a structure that is procedurally constructed by the controller, which may not be a good example of self-organization as discussed in this article.) and evolution by variation and natural selection (\citealp{Sayama_1999}; \citealp{Sayama_2004}; \citealp{Salzberg_2004}; \citealp{Suzuki_2006}; \citealp{Oros_2007}; \citealp{Oros_2009}). Similarly, partial differential equations (PDEs), a continuous counterpart of cellular automata, have even longer history of demonstrating self-organizing dynamics (\citealp{TURING_1990}; \citealp{prigogine1971}; \citealp{Field_1974}; \citealp{Pearson_1993}).
Another representative class of soft ALife that shows self-organization is the models of collective behavior of self-driven agents (\citealp{Vicsek2012}). Reynolds' Boids (\citealp{Reynolds_1987}) is arguably the best known in this category, in which self-propelled bird-oids, or boids, move in a continuous space according to three kinetic rules: cohesion (to maintain positional proximity), alignment (to maintain directional similarity), and separation (to avoid overcrowding and collision). A variety of related models have since been proposed and studied, including simplified, statistical physics-oriented ones (e.g., \citealp{Vicsek_1995}; \citealp{Levine_2000}; \citealp{Aldana_2007}; \citealp{Newman_2008}) and more detailed, behavioral ecology-oriented ones (e.g., \citealp{COUZIN_2002}; \citealp{Kunz_2003}; \citealp{Hildenbrandt_2010}). These models produce natural-looking flocking/schooling/swarming collective behaviors out of simple decentralized behavioral rules, and they also exhibit phase transitions between distinct macroscopic states. Such collective behavior models have been brought to Artificial Chemistry studies (\citealp{Dittrich_2001}; \citealp{Banzhaf_2015}) as well, such as Swarm Chemistry and its variants (\citealp{Sayama_2009}; \citealp{dittrich2011}; \citealp{Sayama_2011}; \citealp{Sayama_2012}; \citealp{Erskine_2015}) where kinetically/chemically distinct species of agents interact to form non-trivial spatio-temporal dynamic patterns. More recently, these collective behavior models have also been actively utilized in Morphogenetic Engineering (\citealp{Doursat_2011}; \citealp{Doursat_2012}), in which researchers attempt to achieve successful merger of self-organization and programmable architectural design.
Other examples of self-organization in soft ALife are found in simulation models of Artificial Societies. Their roots can be traced back to the famous segregation models developed by Sakoda and Schelling back in the early 1970s (\citealp{Sakoda_1971}; \citealp{Schelling_1971}; \citealp{Hegselmann_2017}), in which simple, independent decision making by individual agents would eventually cause a spatially segregated state of society at a macroscopic level. Agent-based simulations of Artificial Societies has been one of the core topics discussed in the ALife community (\citealp{axtell1996}; \citealp{Lansing_2002}), which have elucidated self-organization of social order such as geographical resource management (\citealp{Lansing_1993}; \citealp{Bousquet_2004}), cooperative strategies (\citealp{Lindgren_1993}; \citealp{Brede_2011}; \citealp{Adami_2016}; \citealp{Ichinose_2017}), and common languages (\citealp{Steels_1995}; \citealp{Kirby_2002}; \citealp{Smith_2003}; \citealp{Lipowska_2012}). Moreover, the literature on self-organization of adaptive social network structure (\citealp{Gross_2009}; \citealp{Bryden_2010}; \citealp{GEARD_2010}) may also be included in this category.
Hard ALife
Robots are life-like artefacts when they show the ability to sense and purposely act in their environment. From Braintenberg's vehicles \citep*{Braitenberg:1986} or W. Grey Walter's tortoises \citep{walter1950,walter1951machine}, the hard way of building artificial life exploited the rich dynamics underlying the interaction between a robot and its environment, so that even simple mechanisms and behavioural rules can confer life-like attributes to seemingly dumb machines. Simple rules do not allow to go farther beyond simple life-like behaviour, however. Higher complexity can be attained either by adding rules to the robot, or by adding robots to a system that, through interaction and self-organisation, can present higher cognitive abilities, from adaptive responses to decision making.
Although self-organisation with robots does not forcedly require many interacting robots, but rather a large number of interactions (see for instance the seminal study on puck clustering \citep{Beckers_2000}, which could be run with a single robot), self-organising robots usually come in pretty large numbers \citep{Rubenstein_2014}.
Aggregation of objects or self-aggregation of robots has been tackled through self-organisation inspired by behaviour observed in living systems, such as cockroaches or bees \citep{Garnier2008,Kernbach2009} or designed through automatic methods like artificial evolution \citep{Dorigo_2004,Francesca2014}.
The movement of groups of robots can also be self-organised, in order to coordinate the direction of motion and collectively avoid obstacles \cite{Baldassarre_2007,Trianni2006,Turgut_2008}.
Self-organisation is also at the basis of collective decision making in groups of robots, whereby positive feedback from recruitment processes and negative feedback from cross-inhibition contribute to shape the outcome of a decision process \cite{Reina_2018,Valentini_2015,Scheidler_2016,Garnier_2009,Garnier_2013,Kernbach_2009,Francesca_2014,Valentini2017}.
Wet ALife
Almost all of protocell research involves self-organization, as interactions between molecules that produce membranes, metabolism, or can store information are studied \citep{Protocells2008}.
Living Technology
Living technology has been defined as technology which is based on features of living systems \citep{Bedau2009}, such as robustness, adaptability, and self-organization (which can include self-reconfiguration, self-healing, self-management, self-assembly... often named self-* in the context of autonomic computing \citep{Poslad2009}).
Self-organization has been used directly in living technology in a variety of domains \citep{Bedau2013IntroductionLT}, from protocells \citep{Rasmussen2008} to cities \citep*{Gershenson:2013}, and also several methodologies that use self-organization have been proposed in engineering \citep*{Frei:2011}.