Decentralised detection of emergence in complex adaptive systems

Abstract

Emergence is a hallmark of Complex Adaptive Systems (CAS), where non-deterministic interactions between agents can give rise to emergent behaviour or properties at the system level. The nature, timing and consequence of emergent behaviour are fundamentally unpredictable and may be harmful to the system or individual agents. This unpredictability, coupled with the decentralised structure of these systems, means that detecting emergence at run time presents a significant challenge. No single component of a decentralised system can possess a global view of system state, or reliably know in advance the relevant system properties that indicate emergence. Existing approaches to emergence detection have used statistical analysis of system variables that represent global features of the system. These techniques depend on a centralised system monitor with access to information on global system state. However, neither of these assumptions are met in CAS, as these are distributed and composed entirely of decentralized autonomous agents. Additionally, these approaches require prior knowledge of the system properties relevant for emergence detection, which may not be obvious or available for all systems. Other approaches use formal methods to define and predict emergence, but are intended for use at design time or are limited to well-defined, closed systems. This thesis presents Decentralised Emergence Detection (DETect), a novel distributed algorithm that enables constituent agents to collaboratively detect emergent events in CAS. The main contribution of DETect is that it does not require any centralised controller or system monitor, and instead runs locally on each agent. In addition, DETect uses only the available information from an agent's local environment at run time to facilitate detection. DETect relies on the feedback that occurs from the system level (macro) to the agent level (micro) when emergence is present. This feedback constrains agents at the micro-level, and results in changes occurring in the relationship between an agent and its environment. DETect uses statistical methods to automatically select the properties of the agent and environment to monitor, and tracks the relationship between these properties over time for changes. When a significant change is detected, the algorithm uses distributed consensus to determine if a sufficient number of agents have simultaneously experienced a similar change, before a shared conclusion is reached that emergence has occurred. On agreement of emergence, DETect raises an event, which its agent or other interested observers can use to act appropriately. The evaluation of DETect uses three multi-agent simulation case studies: flocking, pedestrian counter-flow and traffic. Each simulation model exhibits emergence allowing performance to be assessed across a range of system scales. The case studies are structured to verify the efficacy of DETect in three competences: autonomously selecting what properties to monitor, detecting feedback from emergence and forming consensus among agents on the presence of emergence. Performance is evaluated for detection of both the formation and evaporation of emergence in each system. The results of these studies demonstrate that DETect generally achieves its design objectives, facilitating the decentralised detection of emergence formation in each case study. However, the general applicability of DETect during periods of emergence evaporation is limited, with successful detection achieved in the pedestrian and traffic case studies only.