Our work on formalising emergent behavior in multi-agent systems will appear in PADS 2013!

Abstract: Emergence is a distinguishing feature in systems, especially when system 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 exist. However, 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 approach to formalize and verify the existence and extent of emergence without prior knowledge 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 show the feasibility of our approach but also highlight future avenues of improvement.