Formalization of emergence in multi-agent systems

ABSTRACT

Emergence is a distinguishing feature in systems, especially when complexity grows with the number of components, interactions, and connectivity. There is immense interest in emergence, and a plethora of definitions from philosophy to sciences. Despite this, there is a lack of consensus on the definition of emergence and this hinders the development of a formal approach to understand and predict emergent behavior in multi-agent systems. This paper proposes a grammar-based set-theoretic approach to formalize and verify the existence and extent of emergence without prior knowledge or definition of emergent properties. Our approach is based on weak (basic) emergence that is both generated and autonomous from the underlying agents. In contrast with current work, our approach has two main advantages. By focusing only on system interactions of interest and feasible combinations of individual agent behavior, state-space explosion is reduced. In formalizing emergence, our extended grammar is designed to model agents of diverse types, mobile agents, and open systems. Theoretical and experimental studies using the boids model demonstrate the complexity of our formal approach.

References

1. R. Abbott, Emergence Explained: Abstractions Getting Epiphenomena to Do Real Work, Complexity, 12(1):13--26, 2006.
2. N. A. Baas and C. Emmeche, On Emergence and Explanation, Intellectica, pages 67--83, 1997.
3. C. Baier and J. Katoen, Principles of Model Checking, The MIT Press, 2008.
4. Y. Bar-Yam, A Mathematical Theory of Strong Emergence Using Multiscale Variety, Complexity, 9(6):15--24, 2004.
5. M. A. Bedau, Weak Emergence, Philosophical Perspectives: Mind, Causation, and World, 1997.
6. M. A. Bedau, Downward Causation and the Autonomy of Weak Emergence, Principia 3, 3:5--50, 2003.
7. E. Bonabeau and J. Dessalles, Detection and Emergence, Intellectica, 25(2), 1997.
8. D. J. Chalmers, Strong and Weak Emergence, The Re-emergence of Emergence, Oxford University Press, 2006.
9. W. K. V. Chan, Interaction Metric of Emergent Behaviors in Agent-based Simulation, Proc of Winter Simulation Conference, pages 357--368, 2011.
10. C. C. Chen, Complex Event Types for Agent-based Simulation, PhD thesis, University College London, 2009.
11. J. P. Crutch_eld, Is Anything Ever New? Considering Emergence, Complexity: Metaphors, Models, and Reality, G. Cowan, D. Pines, and D. Melzner (eds.), SFI Series in the Sciences of Complexity XIX:479--497, Addison-Wesley, 1994.
12. V. Darley, Emergent Phenomena and Complexity, Artificial Life IV, pages 411--416, 1994.
13. J. Deguet, L. Magnin, and Y. Demazeau, Elements about the Emergence Issue: A Survey of Emergence Definitions, ComPlexUs, 3:24--31, 2006.
14. G. B. Dyson, Darwin Among the Machines: The Evolution of Global Intelligence, Perseus Books Group, 1998.
15. D. Fisch, M. Janicke, B. Sick, and C. Muller-Schloer, Quantitative Emergence - A Refined Approach Based on Divergence Measures, Proc of 4th IEEE International Conference on Self-adaptive and Self-organizing Systems, pages 94--103, 2010.
16. J. Fromm, Types and Forms of Emergence, Complexity Digest, vol. 25(3), 2005.
17. R. Gore and P. F. Reynolds, Applying Causal Inference to Understand Emergent Behavior, Proc of Winter Simulation Conference, pages 712--721, 2008.
18. P. Haglich, C. Rou, and L. Pullum, Detecting Emergence in Social Networks, Proc of 2nd IEEE International Conference on Social Computing, pages 693--696, Minneapolis, MN, USA, 2010.
19. B. Heath, R. Hill, and F. Ciarallo, A Survey of Agent-based Modeling Practices (January 1998 to July 2008), Journal of Artificial Societies and Social Simulation, 12(4):9, 2009.
20. J. H. Holland, Emergence: From Chaos to Order, Addison Wesley, 1997.
21. C. W. Johnson, What are Emergent Properties and How Do They Affect the Engineering of Complex Systems? Reliability Engineering and System Safety, 12:1475--1481, 2006.
22. A. Kubik, Toward a Formalization of Emergence, Artificial Life IX, 9(1):41--65, 2003.
23. Z. Li, C. H. Sim, and M. Y. H. Low, A Survey of Emergent Behavior and Its Impacts in Agent-based Systems. Proc of IEEE International Conference on Industrial Informatics, pages 1295--1300, 2006.
24. E. J. Manley and T. Cheng, Understanding Road Congestion as an Emergent Property of Traffic Networks, Proc of 14th World Multi-conference on Systemics, Cybernetics and Informatics, pages 25--34, 2010.
25. T. Moncion, P. Amar, and G. Hutzler, Automatic Characterization of Emergent Phenomena in Complex Systems, Journal of Biological Physics and Chemistry, 10:16--23, 2010.
26. M. Mnif and C. Muller-Schloer, Quantitative Emergence, Proc of IEEE Mountain Workshop on Adaptive and Learning Systems, pages 78--84, Logan, UT, USA, 2006.
27. J. C. Mogul, Emergent (Mis)Behavior vs. Complex Software Systems, Proc of 1st ACM SIGOPS/EuroSys European Conference on Computer Systems, volume 40, pages 293--304, New York, USA, 2006.
28. M. E. J. Newman, Complex Systems: A Survey, American Journal of Physics, 79:800--810, 2011.
29. I. Norros, B. J. Prabhu, and H. Reittu, Flash Crowd in a File Sharing System Based on Random Encounters, Proc of Workshop on Interdisciplinary Systems Approach in Performance Evaluation and Design of Computer & Communications Systems, New York, USA, 2006.
30. T. O'Conner, Emergent Properties, American Philosophical Quarterly, 31(2):91--104, 1994.
31. D. T. Pele and A. M. Tepus, Information Entropy and Efficient Market Hypothesis, Proc International Conference on Applied Economics, 2011.
32. M. Randles, H. Zhu, and A. 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.
33. C. W. Reynolds. Flocks, Herds and Schools: A Distributed Behavioral Model, Proc of 14th Annual Conference on Computer Graphics and Interactive Techniques, pages 25--34, New York, NY, USA, 1987.
34. C. Rou, A. Vanderbilt, M. Hinchey, W. Truszkowski, and J. Rash, Properties of a Formal Method for Prediction of Emergent Behaviors in Swarm-based Systems, Proc of 2nd IEEE International Conference on Software Engineering and Formal Methods, September 2004.
35. A. K. Seth, Measuring Emergence via Nonlinear Granger Causality, Artificial Life XI, pages 545--552, 2008.
36. C. E. Shannon, A Mathematical Theory of Communication, Bell System Technical Journal, 27(3):379--423, 2000.
37. C. Szabo and Y. M. Teo, An Integrated Approach for the Validation of Emergence in Component-based Simulation Models, Proc of Winter Simulation Conference, pages 242:1--242:12, 2012.
38. C. Szabo and Y. M. Teo, An Objective-based Approach for Semantic Validation of Emergence in Component-based Simulation Models, Proc of 26th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, pages 155--162, ZhangJiaJie, China, July 15-19, 2012.
39. Y. M. Teo and C. Szabo, Semantic Validation of Emergent Properties in Component-based Simulation Models, Book Chapter in Ontology, Epistemology, and Teleology of Modeling and Simulation -- Philosophical Foundations for Intelligent M&S Applications, edited by Andreas Tolk, pages 319--333, Springer-Verlag, 2013.
40. B. Zhan, D. N. Monekosso, P. Remagnino, S. A. Velastin, and L. Q. Xu, Crowd Analysis: A Survey. Machine Vision and Application, 19(5-6):345--357, September 2008.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies