Emergence in stigmergic and complex adaptive systems: A formal discrete event systems perspective

Some extracts from Saurabh Mittal’s paper.

A natural system is not a monolithic system but a heterogeneous system made up of disparity and dissimilarity, devoid of any larger goal. The system just “is.” Examples of such systems include ant colonies, the biosphere, the brain, the immune system, the biological cell, businesses, communities, social systems, stock markets etc. Such systems are adaptable systems where emergence and self-organization are factors that aid evolution. These systems are classified as complex adaptive systems. According to Holland (2006, 1): “CAS are systems that have a large number of components, often called agents that interact and adapt or learn.”

In this article, we investigate CAS by looking at the scale of components, interactions between the components, and emergent properties that are manifested by such CAS. We will attempt to understand some of the common underlying properties, address the adaptive nature of such complex systems and illustrate how resilience is an inherent property of CAS.

CAS is occasionally modeled by means of agent-based models and complex network-based models. Multi-agent systems (MAS) is the area of research that deals with such study. However, CAS is fundamentally different from MAS in portraying features like self-similarity (scale-free), complexity, emergence and self-organization that are at a level above the interacting agents. A CAS is a complex, scale-free collectivity of interacting adaptive agents, characterized by high degree of adaptive capacity, giving them resilience in the face of perturbation. Indeed, designing an artificial CAS requires formal attention to these specific features. We will address these features and the formalisms needed to model CAS.

The discipline of modeling originated to understand natural phenomena. By developing abstractions, we can manage the apparent complexity, reuse it and enable these complex phenomena in artificial systems to our advantage. The discipline of executing this model on a time base is “simulation.” The task of decoding the original structure from manifested behavior is the holy grail of the modeling and simulation (M & S) enterprise (Zeigler, Praehofer, & Kim, 2000). The need for M & S to make progress in understanding CAS has been well acknowledged by Holland (1992). The task is to understand the gamut of rules that exist within and without a component and understand how the component deals with such multidimensional rules in an interactive environment. M & S is the only way one can understand, mimic and recreate a natural system. Most artificially modeled systems that exhibit complex adaptive behavior are driven by multi-resolution bindings and interconnectivity at every level of system behavior. To understand life is to “model”; to adapt is to survive in an environment, where both survival and environment are loaded concepts based on the guiding discipline.

Complexity is a phenomenon that is multivariable and multi-dimensional in a space-time continuum. Therefore, what we need is a framework that helps develop system structure and behavior in an abstract manner and that is component oriented so that the system can define its interactions based on the composition of a multi-level environment.

Stigmergy, the study of indirect interaction between network components in a persistent environment, explains certain emergent properties of a system. The network components include both the environment and the agent and both are persistent, i.e. both are situated in a space-time continuum and have memory. We take Stigmergic systems to be a subset of CAS and argue that stigmergic behavior is an emergent phenomenon too. Ultimately, we are trying to get a handle on how to formalize the property of “emergence.”

Discrete event abstraction has been studied at length by Bernard Zeigler throughout his illustrious career and his pioneering work on Discrete Event Systems (DEVS) formalism in 1970s (Ziegler, 1976). As a student, his perspectives on CAS were influenced by Holland. Ziegler’s approach to CAS has been through the quantization of continuous phenomena and how quantization leads to abstraction. Any CAS must operate within the constraints imposed by space, time, and resources on its information processing (Pinker, 1997). Evidence from neuronal models and neuron processing architectures and from fast and frugal heuristics, provide further support to the centrality of discrete event abstraction in modeling CAS when the constraints of space, time and energy are taken into account. Zeigler stated that discrete event models are the right abstraction for capturing CAS structure and behavior (Zeigler, 2004). In this article, we take the discipline of modeling CAS forward, by looking at the emergence aspect of CAS. We introduce DEVS and demonstrate how recent extensions still fall a little short in modeling CAS.

We first focus on the study of network science and how scale-free networks are inherently important to study complex interactions and hierarchical systems. In Section 3 we look at various types of interactions in a complex network. Section 4 we address the concepts of emergence and self-organization in detail and examine how a complex dynamic network facilitates such behavior. Section 5, a slight digression, provides an overview of DEVS theory. We return to the subject of dynamism in a complex adaptive network in Section 6 and show how DEVS theory is positioned to give modeling and simulation support to the subject. We describe various existing formal DEVS extensions that help model various features of stigmergy, emergence and CAS. Finally, in Section 7, we present some conclusions and pointers for future research.

Complexity is a multifaceted topic and each complex system has its own properties. However, some of the properties like high interconnectedness, large number of components, and adaptive behavior are present in most natural complex systems. We looked at the mechanism behind interconnectedness using network science that describes many natural systems in the light of power laws and self-similar scale-free topologies. Such scale-free topologies bring their own inherent properties to the complex system such that the entire system is subjected to the network’s structural and functional affordances.

It is largely unknown what makes a network evolve into a scale-free network, whether it is a top-down goal-driven phenomena or bottom-up causation or just an outcome of natural interactions. Two conditions have to be present for a network to evolve into a scale-free network: 1. incremental growth and 2. preferential attachment. We explored the notions of scale-free nature, strong and weak emergence, self-organization and stigmergic behavior in a complex adaptive system with persistent agents and persistent environment. We also related the concept of emergence to network science and presented arguments on how hubs and connectors are formed when a complex system is going through a critical phase. We argued that under any occurrence of both self-organized and emergent behavior together, the properties of scale-free network exist and one has to look at right level of abstraction in a multi-level system to witness the instance based interactions. We established that stigmergy displays strong emergence and is a specialized case of CAS. We also enumerated 18 properties of a CAS, 11 of which were properties of stigmergic systems.

We presented a high level view of DEVS theory and how its formal rigor is able to specify complex hierarchical systems. We described variants of dynamic structure and multi-level DEVS, and mapped it to some of the identified properties of CAS and stigmergy. We detailed the adaptive nature of complex system with DEVS Level of system specification and what it means to have dynamic adaptive behavior at different levels of a system. During the mapping process, we found that the following capabilities warrant formal attention to extend DEVS theory of complex systems to a theory of complex adaptive systems:

  1. How clusters are formed, hubs appear and evolve.
  2. How multi-level self-organization occurs.
  3. How strong emergence results in self-organization with an embedded observer capable of causal behavior at lower levels of hierarchy.
  4. How formal attention to coupling specification may provide additional abstraction mechanisms to model dynamic interconnected environment.

Finally, we recommended the augmentation of as the foundation for Stigmergic-DEVS, and investigation of both and ML-DEVS augmented together as a foundation for CAS-DEVS.