Actions of terrorist organizations, flu viruses or natural disasters can be considered emergent behaviours in our environment. In recent decades, emergent phenomena have been the subject of multiple research efforts in the field of complex adaptive systems, however, it is still hard to predict, track and supervise such phenomena. This highlights the urgency to better understand the dynamics of these behaviours in order to timely detect critical phase transitions that might form a risk for software or human environments. This paper introduces an emergent verification system that integrates a data retriever from agent-based simulations and a verification module based on fuzzy classification. We follow the classification of emergent behaviours according to Fromm's taxonomy. In addition, the paper presents a scenario implementation using swarms of birds (Boids model) to demonstrate the applicability of the proposed approach. The results show that the framework is able to verify weak emergence occurred during simulations. Since this work is a part of ongoing research, the future direction is also discussed.
classification, Swarming.
Computer systems have grown extremely complex with the expansion of storage and information processing technologies as well as the evolution of networks. As a result, models and approaches for decentralized and large-scale application have been developed. It facilitates the creation of multi-agent systems and other models and simulation tools. The versatility of agent-based simulation (ABS) enables for the investigation of complicated systems' behavior. In this study, we look at how agents interact in order to identify emergence. Emergent behaviors may be observed practically anywhere in real life, yet their research is limited since they are difficult to identify [1]. Interactions between system components are unquestionably important in the formation of such events. The system may be described with AgentBased Simulation (ABS), where agents represent these components, due to the interaction among the components and their capacity to decide separately following a given logic [2]. The goal of this study is to fully use emergence's potential. Variable-based [2][3][4] and event-based [4] research efforts are primarily separated into two categories.
The variable-based technique measures emergence quantitatively using a specified variable, such as the mass center of an animal population, and detects emergence by assessing changes in that variable. Applying variable-based approaches in continuous uncertain systems is tough, and overcoming the computing cost, as well as the necessity for ongoing human involvement, are additional challenges. The event-based approach focuses on system state changes [5], and emergent behavior is regarded as a result of events that cause shifting points, either at the global level (Marco) or at the level of system components (Micro). One of the most common methods for identifying emergence is to look for changing points in the system; consequently, in this research, we employ an inflexion predictor to do so. Emergence is a global state in a system.
Data mining is the act of sorting through enormous data sets to find relationships, forecast outcomes, and solve issues. The suggested solution leverages big data using data mining with an inflection predictor. Data mining employs a variety of sophisticated and clever approaches, including classification, clustering, time series analysis, and so on. To detect the increase of emergence, we used interactions as metrics, and the technique employs a fuzzy classification with simulation data as inputs. Our technique is designed and tested using an ABS model called the Boids model [6].
This paper is set up as follows. In the next section, theoretical foundations are described. Sec. III introduces the related works that inspired this study, the proposed approach will be presented in Sec. IV, Sec. V shows experiments conducted and their analysis. Finally, in Sec. VI some concluding remarks and future work lines are presented.
Complex systems have properties that are difficult to predict by studying the behaviour of their parts [7]. Exchanges in human societies, as well as the flocking in a group of birds, are emerging behaviours [6]. Emerging phenomena can be beneficial, for example, if the new unknown proprieties are considered as "positive" or "useful", these behaviours can otherwise be "negative" or "dangerous". Identifying these properties can prevent potential danger.
Many attempts to define the meaning of emergence have been documented. Originating from philosophy [3], emergence became useful in ABS especially for studying complex systems. Emergence provides a great opportunity for understanding interactions in a complex environment [4]. In this work, we follow Fromm's [8] classification. He proposed a taxonomy that classifies emergence based on feedbacks and causality.
In this work, we only consider type II (weak emergence) and type IV (Strong emergence), Strong emergence is the notion of emergence that is most common in philosophical literature about emergence, and is the notion invoked by the British emergentists of the 1920s. Weak emergence is the notion of emergence that is most common in scientific discussions of emergence, and is the notion that is typically invoked by proponents of emergence in complex systems theory. Weak emergence describes new properties arising in systems as a result of the interactions at a micro level. However, Bedau says that the properties can be determined only by computer simulation.
Strong emergence describes the direct causal action of a macro-level system upon its components; qualities produced are irreducible to the system's constituent parts [23]. The whole is not equal to the sum of its parts [9]. 2.2.
Craig Reynolds [6] created Boids, which is an artificial life simulation. The simulation's goal is to mimic the behavior of flocks of birds. The Boids simulation, on the other hand, instead of directing the interactions of a complete flock, merely defines the behavior of each individual bird. The program generates a result that is sophisticated and realistic enough to be utilized as a framework for computer graphics applications such as computer-generated behavioral animation in motion picture films using only a few simple principles, Figure 1: Boids’ rules shows Boids’ rules.
Within the simulation, emergent properties in the Boids model could appear. When a packing behavior occurs, emergent behavior is verified. To make visual recognition of emergence easier, we chose to analyze a small number of agents. The goal of this paper is to understand these unexpected behaviours. 2.3.
Engineering fuzzy systems, based on fuzzy logic proposed by Zadeh [24] [25], date back to the 1970s, when Mamdami [26], [27] developed the first fuzzy controller. Fuzzy systems have now acquired popularity in a variety of domains, including control and automation, pattern recognition, medical diagnosis, and forecasting. Because fuzzy systems are frequently considered as black boxes, an analytical theory for fuzzy systems is required to resolve misunderstandings and disagreements. Investigation and optimization of developed fuzzy models, as well as comparison study of different methodologies, play an essential role [28], [29], [30] The objective of this work is to build a fuzzy rulebased system (FRS) to verify the raise of emergent proprieties in an ABS, results. Due to the complexity of the study, several techniques to automatically generate FRS were used i.e., ad-hoc data driven models and genetic fuzzy systems (GFS). The first technique is based on learning from the input-output dataset resulting in the simulation, the second group processes learning of a fuzzy system, precisely parameters of that system, as an optimization problem and uses a genetic algorithm (GA) to proceed that task. The system modeling process is divided into three parts. First step encloses a data retrieval from the ABS, the second phase is the emergence classification via the fuzzy system.
The fast-growing complexity of modern systems is challenging for the research community, and the need for techniques that can cope with these types of systems is crucial in numerous domains, including communication, learning, industry, and engineering. Agent-based simulation (ABS) is the most widely used simulation approach because it is versatile and capable of simulating large, interconnected systems. (ABS) techniques are commonly used to explore emergent behavior as a result of simulation. Emergence is prevalent in systems with a large number of pieces, and it is usual to see and manipulate the emergence of unanticipated behaviors using ABS simulation platforms.
It is critical to provide the theoretical background for constructing and modeling the approach by initiating the emergence type and taxonomy of the emergent behaviors we are interested in. There are many other emergence definitions, however for the sake of this study, we simulated the procedure using Bedau's [9] weak emergence definition. A weak emergence may be proven by simulation, and it is predicted and perhaps regulated in particular systems. The modeling of flocking in the Boids model, for example, is controlled by three rules: separation, cohesion, and alignment. The application of these criteria will result in grouping behavior (emergence). Experts may either increase or eliminate flocking by changing a few settings.
To define the technique after identifying the emergence’s type we're interested in, we used Fromm's type II class of emergence [10]. Fromm provided a taxonomy that categorizes four types of emergence based on distinct feedback patterns. Simple feedback (Negative or Positive) is the major characteristic of (Type II), which is defined as a top-down interaction from the macro to micro level. Positive feedbacks are preventative orders that ensure the system does not diverge into detrimental behavior, according to Fromm. Negative feedbacks are restricting to the behaviors of the agents (e.g. swarm intelligence) (e.g. Avoiding financial bubbles), To exemplify this class, in the Boids model, the Separation rule is deemed Positive if the expert does not want the birds to flock; on the other hand, removing this rule will cause the birds to swarm quickly.
Researchers have been attempting to measure emergence for a long time. As an example. [11] described emergent behavior as state-changing points and stated that algorithms may be effective in verifying emergent behavior. [12] employed interaction statistics as a measure to examine the emergence of emergent behaviors using Agent-based simulation (ABS). [13,14] proposed an ontologybased system for semantically validating emergence, which employed a semantic state distance metric to quantify semantic differences between component attribute values. [15] provides a collection of metrics-based strategies for analyzing vision-based vehicle behavior. [16] uses an age metric to identify and characterize emergence utilizing swarms of Unmanned Aerial Vehicles (UAVs). [17] proposed a statistic meter for detecting emergence and demonstrated how communication in disputed contexts is impacted.
Traditional models (mathematical, statistical) when the data is represented by equations to create the model, see Niharika et al., [18], have been used to detect shifting points in weather forecasting. Big data and learning-based models are being used in recent methods. Read [19] for further information on Big Data and Learning Models. Yu Zheng [20] employed an inflection predictor in his model, and Yu Zheng used an inflection module to capture unexpected changes in air grade in a noteworthy paper. In general, emergence verification research has progressed, however, there is still a lack in using interaction as metrics for the emergence detection. Although it is not debatable that interaction is a critical aspect in emergence, few existing approaches have addressed the analysis of massive simulation data using wellknown statistical techniques. to deal with the mentioned limitations, we present our approach in the next section.
In this section we present the multi-agent simulation framework (Figure 2) that consists of two components, agent-based simulation engine and fuzzy-based classification engine. These two components communicate with each other to implement their functionality. The main functionality of the simulation engine during the simulation is to retrieve data which will be passed to the fuzzy system to verify emergence.
The simulation system is based on Boids model which simulates a flight of birds. Emergence is detected when a flocking situation take place, as mentioned in section II, in Boids model, an emergence behaviour i.e (packing), happens every time. Simulations were conducted using NetLogo [33], which is a well-known ABS plat-from. Figure 3 presents a simulation in which, a normal behaviour i.e., no packing behaviour, only the Separation rule is on. The agent number is 50, Ticks = 300 steps.
The emergence behaviour in the Boid model is the presence of an unexpected grouping or packing behaviour, this behaviour is often observed in this model. This is the reason why the boid model is one of the most used ABS model to study weak emergence [14][2][35][36][37].
Cohesion: Each time an agent does an action of cohesion with a neighbor Alignment: Each time an agent does an action of alignment with a neighbor
Separation: Each time an agent does an action of separation to avoid collision with a neighbor Every time an interaction is detected, a proper counter is incremented.
Spreadsheet extension does work only in Netlogo version 5, so we simulate the Boid model in this version of Netlogo.
In order to get a variety of simulation data, we have run several scenarios using 5 agents, Boids' three rules are Separation (S), Alignment (A), and Cohesion (C), the results are: Number of agents: 5 and number of steps = 1000. We notice that, for a regular interaction triplet (S, A, C), we always get: Number of A = Number of C.
• Groups: Multiple packs of birds in the simulation. • None: No packing behaviour, no groups. • Full: All birds gathering in one pack.
The following presents some of the simulation results: Results with agent population = 5.
In this work, the fuzzy system is a rule-based classification system (FRBCS) using Chi’s method. This method was introduced by Chi et al. (1996), which is an extension of Wang and Mendel’s method, for treating classification problems. The Knowledge Base: it is composed of both the Rule Base (RB) and the Data Base, where the rules and the membership functions are stored respectively.
To build the rule base, we use an extension of the specification given by Singh [5], TypeII ≡ EmergentBehavior ⊓ ∃hasParticipant.(System ⊓ sendNegativeFeedbackTo.Component). We transform every rule into the following fuzzy rule: Rule Rj 1 1 = =
… ∑ ∈
∑ =1
( ) ( ) ℎ = ℎ (1) (2) We obtain: IF E=1 and NfB = 1 THEN C=1 when: • • •
E is the emergent beaviour, equal to 1 i.e verifier (in Boids thats always the case) NfB stands for Neative Feed Back (Fromm's condition for class number 1 to be verified) C is the fuzzy class, in FBRCS, it is the consequence part of the rules, in this case for this rule, C=1 so type II emergence is verified (weak emergence).
The membership function contains three fuzzy sets for each interaction (Cohesion, Separation, Alignment) variable (Low, Medium, High).
Y ( ) = { (40− ) , 30 ≤ < 40 10 If
M (N= None) for emergence, for the type, as mentioned before, the result will be 1 for weak emergence and 2 for Strong emergence. After learning fuzzy if-then rules by training patterns, different weights and constants values were used. Different weights were assigned to the rules to decrease correct classification rates. The two classes get the highest classification rate for wp=0.25. Table 4. presents the results of the correct classification. Sample of preliminary Results of correct classification rates with different weighting rules.
for all classes = 0.25 for all lasses = 0.25 for all classes ∈ class 1 ∈ class 2 ∈ class 1 ∈ class 2 = 0.5,
In recent years, emergence has become an important research focus. Emergence can be positive or negative and appears in a variety of systems. Therefore, we need a mechanism that provides a structured approach for analysis and control of such behaviors. In this paper, we investigated the use of fuzzy rulebased classification system combined with data retrieved from an ABS to verify and classify emergence. Emergent behaviour is verified before-hand in many ABS models such as the Boids model, however, detecting and classifying that phenomena is challenging. To address this issue, we propose a method to classify the flocking behaviour in multi-agent system with a fuzzy system. At this moment, we are extending the rules data base and we are testing it. The first results are promising and we are aiming to validate this method with other ABS systems using more complex models.
The author would like to thank the DGRSDT (General Directorate of Scientific Research and Technological Development) - MESRS (Ministry of Higher Education and Scientific Research), ALGERIA, for the financial support of LISCO Laboratory.
M. Randles, H. Zhu, and M. Taleb-Bendiab., ―A Formal Approach to the Engineering of Emergence and its Recurrence‖, Proc of 2nd International Workshop on Engineering Emergence in Decentralized Autonomic Systems, 2007. [2] P., Jing, H., Hu, F., Zhan, Y., Chen, & Y., Shi. Agent-based simulation of autonomous vehicles: A systematic literature review. IEEE Access, 8, 79089-79103, 2020
Organization, 1(1):49-72, 1999cxc [3] J. Goldstein, ―Emergence as a construct: History and issues.‖ Emergence: Complexity and [4] C. Johnson, ―What are emergent properties and how do they affect the engineering of complex systems?‖ Reliability Engineering and System Safety, 91 12:1475-1481, 2006 [5] S. Singh, et al., ―Detection and classification of emergent behaviors using multi-agent simulation framework (WIP),‖ In Proceedings of the Symposium on Modeling and Simulation of Complexity in Intelligent, Adaptive and Autonomous Systems (MSCIAAS '17), Saurabh Mittal and Jose Luis Risco Martin (Eds.). Society for Computer Simulation International, San Diego, CA, USA, Article 3, 8 pages, 2017 [6] C. W. Reynolds, ―Flocks, herds and schools: A distributed behavioral model‖. ACM SIGGRAPH computer graphics vol. 21 (4), pp. 25–34. 1987. [7] S. Kalantari, E. Nazemi, & B. Masoumi. Emergence phenomena in self-organizing systems: a systematic literature review of concepts, researches, and future prospects. Journal of Organizational Computing and Electronic Commerce, 30(3), 224-265, 2020 [8] J. Fromm, Types and Forms of Emergence‖, complexity Digest, vol. 25(3), 2005. [9] M. Bedau, Weak emergence,‖ In Philosophical perspectives: Mind, causation, and world. ed. J.
Tomberlin. 11:375-399: Blackwell Publishers. 1997 [10] J. Fromm, The emergence of complexity,‖ Kassel: Kassel University Press, 2004. [11] R. Grossman, et al., Discovering emergent behaviour from network packet data: Lessons from the angle project.', 2009. [12] R. Gore, and , P Jr. Reynolds., An exploration-based taxonomy for emergent behaviour analysis in simulations,‖ In Proceedings of the 2007 Winter Simulation Conference. eds. S. G. Henderson, B. Biller, M.-H. Hsieh, J. Shortle, J. D. Tew, and R. R. Barton. 1232-1240. Piscataway, New Jersy: Institute of Electrical and Electronics Engineers, 2007. [13] C. Szabo, and Y.M. Teo, An Objective-based Approach for Semantic Validation of Emergence in Component-based Simulation Models,‖ ACM/IEEE/SCS 26th Workshop on Principles of Advanced and Distributed Simulation. (2012) [14] C. Szabo, and Y.M. Teo , Formalization of weak emergence in multiagent systems, ‖ ACM Trans.
Model. Comput. Simul. 26, 1, Article 6 (September 2015), 25 pages. DOI: http://dx.doi.org/10.1145/2815502, 2015. [15] S. Sivaraman, and M.M. Trivedi, , Looking at Vehicles on the Road: A Survey of Vision-Based Vehicle Detection, Tracking, and Behavior Analysis,‖ IEEE Transactions on Intelligent Transportation Systems ( Volume: 14 , Issue: 4), 2013. [16] C. Hewitt, Viewing control structures as patterns of message passing', Artificial Intelligence, vol.
8, no 3, p. 323–374, 1977. [17] B Fraser, et al., Simulating the effect of degraded wireless communications on emergent behavior,‖
Winter Simulation Conference (WSC), 2017. [18] S.M., Cabaneros, J.K., Calautit, & B.R., Hughes. A review of artificial neural network models for ambient air pollution prediction. Environmental Modelling & Software, 119, 285-304, 2019 [19] Gaganjot Kaur Kang, Jerry Zeyu Gao, Sen Chiao, Shengqiang Lu, and Gang Xie, ―Air Quality Prediction: Big Data and Machine Learning Approaches,‖ International Journal of Environmental Science and Development vol. 9, no. 1, pp. 8-16, 2018. [20] Y. Zheng, Y. Xiuwen, L. Ming, L. Ruiyuan, S. Zhangqing, E. Chang, and L. Tianrui,. Forecasting Fine-Grained Air Quality Based on Big Data‖. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). ACM, New York, NY, USA, 2267-2276. DOI: https://doi.org/10.1145/2783258.2788573. 2015. [21] W. k V. Chan, Interaction metric of emergent behaviours in agent-based simulation,‖ Proceedings of the 2011 Winter Simulation Conference S. Jain, R.R. Creasey, J. Himmelspach, K.P. White, and M. Fu, eds. (2011). [22] P. J. Rousseeuw. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis.
Journal of Computational and Applied Mathematics, 20:53–65, 1987. [23] Laughlin, Robert (2005), A Different Universe: Reinventing Physics from the Bottom Down, Basic
Books, ISBN 978-0-465-03828-2. [24] L. Zadeh, Fuzzy sets,‖ Information Control, vol. 8, pp. 338–353, 1965. [25] Y. Wang, P. Jia, L. Liu, C. Huang, & Z. Liu. A systematic review of fuzzing based on machine learning techniques. PloS one, 15(8), e0237749, 2020 [26] E. H. Mamdani and S. Assilian, ―An experiment in linguistic synthesis with a fuzzy logic controller,‖ International Journal of Man-Machine Studies, vol. 7, no. 1, pp. 1–13, 1975. [27] E. H. Mamdani, Application of fuzzy logic to approximate reasoning using linguistic synthesis,‖ in Proceedings of the sixth international symposium on Multiple-valued logic. Los Alamitos, CA, USA: IEEE Computer Society Press, 1976, pp. 196–202. [28] V. Ojha, A. Abraham, & V. Snášel. (2019). Heuristic design of fuzzy inference systems: A review of three decades of research. Engineering Applications of Artificial Intelligence, 85, 845-864, 2019. [29] K. Mittal, A. Jain, K.S. Vaisla, O. Castillo, & J. Kacprzyk. (2020). A comprehensive review on type 2 fuzzy logic applications: Past, present and future. Engineering Applications of Artificial Intelligence, 95, 103916, 2020. [30] X. Xiang, C. Yu, L. Lapierre, J. Zhang, & Q. Zhang. Survey on fuzzy-logic-based guidance and control of marine surface vehicles and underwater vehicles. International Journal of Fuzzy Systems, 20(2), 572-586, 2018. [31] P. Kotak, & H. Modi,. Enhancing the data mining tool WEKA. 5th International Conference on
Computing, Communication and Security (ICCCS) (pp. 1-6). IEEE. 2020. [32] I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, 2nd ed. San Francisco: Morgan Kaufmann, 2005. [33] Wilensky, U. (1999) Netlogo. Evanston, IL: Center for Connected Learning and Computer-Based Modeling, Northwestern University. Available via <http://ccl.northwestern.edu/netlogo/> [accessed October 10, 2010]. [34] Soltani, A., Battikh, T., Jabri, I., & Lakhoua, N. (2018). A new expert system based on fuzzy logic and image processing algorithms for early glaucoma diagnosis. Biomedical Signal Processing and Control, 40, 366-377. 2018. [35] A. Boukehila., N. Taleb, & Y. Benazzouz. (2021). Interactions-based method to detect emergent behavior in ongoing simulations. International Journal of Modeling, Simulation, and Scientific Computing, 12(04), 2150022. [36] A. Boukehila, & N. Taleb. (2019, November). Case-Based Approach to Detect Emergence.
In Proceedings of the 2019 3rd International Conference on Big Data Research (pp. 98-102). [37] A. Boukehila, & N. Taleb. (2020, February). Statistical Study To Detect Emergent Behaviours.
In 2020 2nd International Conference on Mathematics and Information Technology (ICMIT) (pp. 164-168). IEEE.