Many natural systems work based on local interactions among their component entities, and some of them are described as self-organized (selforg). This term usually refers to a system that is able to change its internal organization in order to adapt to internal or external changes without the need for an explicit external control [8]. These collective systems are particularly robust, because of the inherent redundancy, provided by their multiple components; that allow them to adapt to changes in order to ensure their own survivability.

Strongly linked with self-organization, we can find the concept of emergence [7], describing that even individual entities may perform very simple behaviors, the whole system can carry out very complex tasks, that emerge from the local interactions of those individuals.

Examples for natural self-organizing systems include social insects, such as ants and termites, where communication among individuals occurs through a stigmergy process, by the means of pheromones deposited within their environment. Other animals have evolved self-organizing behaviors such as flocks of birds and schools of fish, usually oriented to collectively avoid predators. Human societies also present self-organizing behaviors, when they work by combining local and network interactions to give rise to emergent complex global phenomena. But, perhaps, the human brain is the most complex and interesting system showing self-organization and emergence [21].

Autonomous agents and multi-agent systems are natural candidates to evolve in societies with self-organizing capabilities. Usually agents and multi-agent systems have been used for simulating self-organizing systems, in order to better understand them or to engineer new models. An open arena is the development of distributed systems, where components self-organize and work in a decentralized manner towards the achievement of a given (global) possibly emergent functionality. The use of self-organization techniques in artificial multi-agent systems follows a bottom-up approach, and ranges from imitating naturally-inspired self-organizing models to designing new self-organization models for artificial systems. At the same time, most prototypes of self-organizing systems have been developed using MAS architectures. This does not happen by chance, presently, the MAS paradigm has all the necessary means for the design, development, implementation and simulation of self-organizing systems.

Some applications of this biology inspired computation already have been very successful at computational and mathematical domains like swarm techniques applied in optimization, when the search space is too big and/or involves non linear problems. Besides, the concept of self-organization is present in almost all sciences related with complexity, including: Physics, Biology, Chemistry, Economics and Computer Science among others.

1 Short Historical Notes

The term “self-organizing” was introduced to contemporary science in 1947 by the psychiatrist and cybernetics pioneer W. Ross Ashby [1]. In 1959, Grassé [15] proposed the theory of stigmergy, that shows that direct interactions are not necessary to coordinate a group, and indirect communications through the environment can be enough. Stigmergy describes how coordination is performed by means of information deposited over the environment, that allows the indirect local interaction among the entities without the need for any external or central control.

In 1967 Koestler [18] defined the concepts of holons and holarchies, where holons are functional systems, but at the same time they are also parts of larger systems. The holonic hierarchy model involves structural patterns that form nested hierarchies of self-replicating structures named holarchies. The elements of holonic systems are denoted with the term holon, which is a combination of the Greek word holos, meaning whole?, with the suffix on meaning part, as it is used in the words proton or neuron.

Also in the 1970s, Francisco Varela [23] established the notion of autopoiesis (meaning self-production) as the process where a system is able to self-reproduce. Autopoiesis applies to closed systems made of autonomous components whose interactions self-maintain the system itself, such as living organisms or body cells.

After Ilya Prigogine’s got his Nobel Prize in 1977, scientific researchers started to migrate from the cybernetic view to the thermodynamic concept of self-organization, which describes how open systems decrease their entropy (increase ordering) when an external energy is applied onto the system.

During the last 20 years, research in artificial systems has been oriented towards introducing self-organization mechanisms specifically for software applications. These works have taken diverse inspirations from stigmergy to autopoiesis, or to the holon concept itself. Recently, a relevant effort to analyze the state of the art, to structure the research effort and to define a roadmap in the selforg area was made in the European AgentLink project [10], where a working group for studying self-organizing MAS was created.

Recent research efforts have been oriented towards introducing self-organization mechanisms specifically for software applications. A detailed and extensive introduction to self-organizing models together with a review of applications can be found in [13, 14].

2 Concepts of Self-organizing Systems

Self-organization generally refers to the internal driving force that leads to an increasing level of organization, i.e., improving the structure and the interactions among the distributed components. Self-organization is basically an adaptive process, meaning that when the environment changes the system evolves to a new stable equilibrium. We can consider two different types of self-organization systems [7]:

  • Strong self-organizing systems are those ones where there is no explicit central control either internal or external. For instance, we can consider here an ideal economic market that evolves according to liberal economic rules.

  • Weak self-organizing systems are those ones where there is an internal (central) control or planning. In this case we can consider a termite society where there is a queen that has a higher influence, p.e., than termite soldiers, over nest behavior (see Fig. 6.1).

Fig. 6.1
figure 1

A termite “cathedral” produced by a termite colony

Full size image

Therefore, the absence of explicit external control is a mandatory property for these types of systems, stating their autonomy. If the system also works under decentralized control, then there is no internal central authority or centralized information flow. In this type of systems information spreading, among the agents, is mainly done by local interactions.

As a working definition, we consider self-organization as a dynamical and adaptive process, where systems reorganize and/or maintain inner structures without the need of external control.

Self-organization is strongly coupled with the concept of emergent behavior, and this concept refers to the possibility of having some kind of emergent phenomena arising from the local interactions. Emergence is reviewed in more detail in the next section. Here, we consider a set of other relevant characteristics that self-organized systems sometimes may exhibit [6, 7]:

  • Endogenous global order: that allows the system to reach some (stable) global state produced by the system itself.

  • Simple local rules: the overall complex system behavior observed is usually based on simple individual behavioral rules. Therefore, local interactions determine the global behavior, but not codify the pattern itself.

  • Dissipation: this concept refers to some possible stable states reached by the system, where some emergent properties can be observed, and those states imply some kind of energy dissipation.

  • Instability: is a property exhibit by many chaotic systems usually characterized by nonlinear dynamics, where minor perturbations in the environmental conditions produce significant variations in the overall system behavior. Such chaotic systems exhibit sensitivity to initial conditions and parameter values, making much more difficult to understand present states and future system evolution.

  • Multiple equilibria: Multiple equilibria are observed when the systems presents several possible attractors for stable states.

  • Criticality: describing the presence of threshold effects or phase changes.

  • Redundancy: this property is present when the elements in the system have similar replicas, so if a few of them suffer any damage, then the system can continue working without special difficulties.

  • Self-maintenance: describing the capacity to self-repair its damaged elements, components or modules.

  • Adaptivity: referring to the capability of adaption to environment changes.

  • Dynamic: the whole system is a process in continuous change.

  • Autonomy: the different components of the system exhibit a high degree of freedom in their behavior.

  • Hierarchies: are present in a system when multiple nested self-organized levels can be observed.

  • Complexity: this characteristic usually is present when observing the global patterns, emerging from the interaction among local behaviors.

Measuring the presence of self-organization mechanisms is not an easy task. A self-organizing system must be studied from local or global points of view, and even considering multiple perspectives; if the self-organization process spans along multiple nested hierarchical levels. Measurements can modify the system structure (re-organization), the process (system dynamics) and the function (purpose) for each level.

3 Emergence

The roots of the emergence concept go back to ancient Greeks, and more recently to the English philosopher G.H. Lewes who used the term. Nowadays, this concept has been revised in multiple domains such as philosophy, mathematics, physics, thermodynamics, systemics and complex systems [12]. The concept of emergence relates that larger entities, patterns, and properties arise through interactions among smaller or simpler ones, that themselves do not exhibit such properties that emerge from the system as a whole. Therefore, such phenomena are observed at a global level, but they cannot be necessarily foreseen by looking only at the individual behavior. The reason is that such emergent phenomena usually arise from local interactions, occurring among the individual components. In this case we can apply the popular sentence describing that the whole is more that the sum up of its parts. A natural example can be the flocking of birds or fish schools (see Fig. 6.2), where the whole swarm structure emerges from very simple rules.

Fig. 6.2
figure 2

(source Wikimedia Commons [24])

Fish schools emerge from simple rules: keep distance, stay aligned and avoid predators

Full size image

The emergence concept can be analyzed from two perspectives: one concerning what observed properties are sufficient to identify emergence, and another focusing on the system characteristics that enable the system to produce emergence. Besides, to show emergence a system must be perceived, at least, at two interdependent levels: a macro and a micro-level. Even there are multiple definitions of emergence [6], here we define it as: A system exhibits emergence when there are coherent features at the macro-level (properties, behavior, structure, patterns, etc.) that dynamically arise from the interactions between the parts at the micro-level.

The outcome of emergence is often called an emergent phenomenon [16]. For instance, the shortest path between an ant nest and a food source, is perceived by the external observer that monitors the density of individuals and pheromones in the trails of the ants; but it is not a concept considered by the ants themselves.

Since emergent phenomena are externally observable over a certain period of time, some dynamic equilibria are needed [12], when emergence may appear between conditions that are either too ordered or too disordered. This has been vaguely described as the edge of chaos [17, 19]. Usually, the appearance of emergence, around these equilibria, implies that the system also exhibits some kind of self-organization.

In order to identify emergent phenomena, some authors establish some key properties to characterize them [6, 7]:

  1. 1.

    Observability: describing that the phenomenon needs to be observable at least at a macro-level to perceive the emergent phenomena.

  2. 2.

    Novelty: referring that global macro-level properties are novel or different from individual properties at micro-level and cannot be predicted from them.

  3. 3.

    Irreducibility: Churchland [5] describes the irreducibility properties of complex systems as those ones that are not present in their individual parts.

  4. 4.

    Interdependency: this property describes the strong dependency between the dynamics observed at both macro and micro-levels [19]. The micro-level causes the emergent phenomena, and the macro-level contains the micro-level entities, and constrains their behavior.

  5. 5.

    Nonlinearity: emergent phenomena originate from nonlinear activities at the micro-level, usually in the form of positive and negative feedback loops.

4 Self-organization Versus Emergence

The main similarity in the concepts of emergence and self-organization is that both are dynamic processes, where local interactions at microlevel manifest at macrolevel. However, albeit strongly related, the concepts of emergence and self-organization do not always appear together [6]. For instance, an ant nest shows a self-organizing process with emergence (e.g., the shortest path when foraging food), that can be observed visually and emerges as a result of local rules and stigmergy. On the other hand, many physical phenomena only show emergence without self-organization, for instance, tornados or hurricanes where atmospheric conditions determine the creation of such macro-level structures from the micro-level interaction of gas particles.

Nevertheless, the practice has shown that the coexistence of self-organization and emergence concepts in complex systems is quite natural. Self-organization enables a complex system to adapt itself to a dynamic environment, based only on the local interactions of its elements. The interactions work in such a way as to generate emergence properties of the system as a whole.

5 Mechanisms for Self-organizing Multi-agent Systems

One of the main issues when engineering multi-agent systems showing self-organizing and/or emergent properties is that there must be a correlation between the design of the local behaviors, and the global goal that the designer wants to accomplish. Therefore, the central question becomes how to program single agents that self-organize when working as a whole. This is usually difficult to perform, as many times the global goals, or some emergent properties, are not directly predictable from the local behaviors (an inherent characteristic of self-organizing systems). Thus, simulation and testing become main tools in order to validate, up to a certain level, the performance of the system [8].

There is no general neither easy classification of self-organization mechanisms in natural or artificial systems, as they can be analyzed from different points of view, and many mechanisms combine several basic principles [13]. Along this section we explore different perspectives to classify selforg mechanisms.

5.1 Information-Based Perspectives

One possible analysis of a system may consider the information flow among the system components. Therefore, there could be three concepts to be considered [13]:

  1. 1.

    What information is exchanged among the agents?

    We can consider two alternatives: markers or sematectonic information.

    1. (a)

      In interactions based on markers, agents explicitly exchange symbols or signals having a special and identical meaning for every receptor. For instance hazard audio signals, chemical substances like pheromones, etc.

    2. (b)

      When using sematectonic information, agents tend to provide implicit information without a specific shared meaning. For instance, letting a pile of objects in a specific place could influence other agents to continue doing it.

  2. 2.

    How does the information flow?

    For instance, the communication can be point-to-point, locally restricted or generally disseminated. In the first case an agent communicates with another agent in its neighborhood, in the second case, the agent can communicate with all its direct neighbors, and in the third case, the agent may disseminate a broadcast message accessible by all the members of the multi-agent system.

  3. 3.

    How do the agents use the information received?

    There are two possible uses of such information: event-driven or follow-through.

    1. (a)

      In the event-driven or trigger-based alternative, the reception of certain messages triggers specific agent activities. For instance, a hazard audio message may trigger the birds to escape flying assuming the presence of any threat.

    2. (b)

      The follow-through alternative implies a sequence of actions for the recipient agent. For example, an agent leaves a trail that other recipient agents follow.

5.2 Interaction-Based Perspectives

A natural classification of self-organization mechanisms was proposed in [8] and considers the use of direct or indirect interactions among the agents in the system.

Direct Interactions

In this approach, an organization or agent structure of the agents may already exist or it may emerge from the interactions among the agents. This model can be considered when a certain organization must be created and maintained on a set of autonomous agents (see [25]). These approaches use a few basic principles, such as localization and broadcasting, coupled with local interactions and computations done by agents in order to provide a desired global state. The final goal of these mechanisms is to converge and to provide robustness to maintain such global stable state, even under perturbations happening at the micro-level or coming from the environment. Therefore, these mechanisms focus on the structural aspects of the agent organization, such as spatial placement of agents and/or agent communication topology.

These mechanisms have the significant advantage that they enable the design of specific self-organized behaviors with the required outcomes and robust properties.

Indirect Interactions

Under this subset we can consider self-organization mechanisms based on the stigmergy concept. Here, the indirect interactions happen due to changes made by the agents over the environment, that are perceived by other agents that modify their behavior and, eventually, lead the system towards the desired global state.

In these approaches, the design phase involves selecting an appropriate self-organizing model and the evaluation of its correctness is usually performed usually by means of simulation and prototyping [9], where the model is calibrated via iterative refinements based on the experimentation results.

On the one hand, these mechanisms have reused the strengths and robustness of known self-organization mechanisms taken from biology to build self-organizing software. Besides, the agent behaviors are usually very simple and easy to implement, resulting in fast prototyping and low development cost.

On the other hand, due to the non-linearity, and the complexity of the phenomena involved; it is not possible to have direct control on the system behavior; neither it can be proven that the desired behavior will be always achieved, and multiple solutions can be reached.

5.3 Other Self-organizing Mechanisms

In [8, 13] we can find other self-organizing mechanisms that share features with the ones just described in the previous classifications. Here we mention some of them.

Reinforcing Behaviors

In some approaches, self-organization is based on the capabilities of the agents to adapt their behavior according to some kind of individual utility function, that determines a reward that they try to maximize modifying their behavior along time. The multi-agent system as a whole also has a global utility function that is not necessarily known by its agents. These approaches are usually based on distributed reinforcement learning techniques, and are also studied under the multi-agent reinforcement learning domain [3].

Cooperation

Cooperation is the leitmotiv used in the AMAS (Adaptive Multi-Agent Systems) theory [11], where the desired collective behavior must always occur as the result of cooperation among the agents in the system. In this framework, self-organization is founded on the capability that agents possess to behave cooperatively with other agents. These cooperation capabilities do not imply that agents are always helpful or altruistic, but that they are able to recognize cooperation failures called Non Cooperative Situations (NCS) and handle them. The local handling of NCS maximizes the flexibility and adaptability of the system to unexpected situations, which can happen due to the inner dynamism of the agent interactions and the environment itself.

Generic Architectures and Holonic Systems

A particular class of self-organization mechanisms is based on generic reference architectures or meta-models of agents organizations, which are dynamically modified as needed according to the requirements of the particular application. The common technique for representing such architectural meta-models is as a typed, directed complex graph.

Two classical examples of such reference architectures are the Mediator [20] and the PROSA [2] architectures, that are both based on the holonic hierarchy model and applied in manufacturing systems. When agents are organized according to the holonic metaphor, they participate in holons forming holarchies [18], and self-organization then refers to altering and adapting such holarchies following the perturbations coming from other agents or from the environment [22].

6 Conclusion

In this chapter we have reviewed the concepts of self-organization and emergence that have attracted attention within the multi-agent system community. This interest is mainly explained because multi-agent systems are well adapted to simulate and implement self-organizing models due to the inherent characteristics of selforg systems. Self-organizing systems consist of a huge number of autonomous entities distributed over space, and connected locally or using a network topology, but with a limited communication range. These entities usually have selfish goals, that not necessarily coincide with the goals of the global system. Altogether, these characteristics have made multi-agent systems a reference model for engineering selforg systems by means of design and simulation.

Hardware and software engineering nowadays manage large-scale distributed systems, usually composed by a large number of elements. It is unrealistic to be able to achieve distributed optimal control of such systems, and even more from a centralized point of view. This is not feasible because of the huge size of those systems, the unpredictability of their dynamic organization, their interactions with the environment, and the diversity of the goals pursued by the different devices. As the building blocks are autonomous entities inherently dynamic, that work distributed and decentralized in a loosely coupled model over a continuously changing environment. The result is a dynamic system in terms of composition and topology.

On the one hand, the problem is how to design individual agent behavior that collectively produce emergent properties that fit with the overall goal to be addressed. In general, the possibility to engineer and to predict the outcomes of emergent properties is feasible only in trivial problems, and that is why most of the artificial selforg systems have been inspired by natural systems. On the other hand, classical and object-oriented software engineering techniques do not fit well within the self-organizing context, as usually they follow a top-down approach, or they just define the global behavior as a direct function of its components or modules. Besides, as we have seen, the environment plays an important role as a source for self-regulating the agents’ behavior in selforg systems.

Nowadays, the growing complexity of the ICT ecosystem and the appearance of concepts like sensor networks, traffic management, autonomic computing, ubiquitous computing, ambient intelligence, Internet of Things, etc.; needs new solutions to support the design and the analysis for autonomous, adaptive and robust complex distributed systems. Selforg models are potentially good candidates to understand such complex behavior, where emergent phenomena may appear from their numerous interacting components, and where self-organization can be a powerful tool to manage complexity.

7 Further Reading

The book The Origin of Order: Self-Organization and Selection in Evolution [17] by Stuart Kaufman is a classic introduction to the topic from the theoretical biology perspective. An alternative book is Self-organization in biological systems [4] by Scott Camazine et al., which is mainly oriented to the study of natural systems. Finally, the book Swarm intelligence: from natural to artificial systems by Bonabeau, Dorigo and Theraulaz provides an approach more related with the concepts described in this chapter in order to engineer artificial systems.