Toward A Formalization Of Emergence

Toward a Formalization of Emergence

Abstract Emergence is a concept widely used in the sciences, the arts, and engineering. Some effort has been made to formalize it, but it is used in various contexts with different meanings, and a uniŽed theory of emergence is still distant. The ultimate goal of a theory of emergence should include using emergence to model, design, or predict the behavior of multiagent systems. The author proposes a formal deŽnition of a basic type of emergence using a language-theoretic and grammar systems approach. It is shown which types of phenomena can be modeled in this sense and what the consequences are for other more complex phenomena.

1

Ales6 Kub´7k Institute of Computer Science Silesian University Bezruc.ovo n´am. 13 746 01 Opava, Czech Republic [email protected]

Keywords Emergence, categorization, multiagent system, grammar system, formal approach

Previous Work on Emergence

The word “emergence” is new to neither the philosophical nor the scientiŽc literature (see, e.g., [1, 42, 43]). In the last two decades it has appeared in numerous publications concerning scientiŽc research on complex systems ([8, 9, 10, 30, 33, 34, 38, 40, 41], to mention a few).1 The importance of the understanding of emergent phenomena in social as well as scientiŽc disciplines has led to attempts to conceptualize, formally deŽne, and categorize emergence. This section will quickly review previous discussions. Cariani distinguishes three types of emergent phenomena [14]: ² Computational emergence refers to phenomena that can be modeled by traditional

Turing machines or automata and simple computer simulations on single-processor machines.

² Thermodynamic emergence is “the formation of new physical structures in the

world at large” [14, p. 151] and applies to phenomena observed in the world of (mostly statistical) physics where the macro-states of a studied system are due to its micro-states.2

² The most interesting type of emergence is emergence relative to a model, which

can be summarized as a deviation of the system’s behavior from the observer’s model of it.

1 A nice (though older) review of the literature with the informal as well as more formal approaches to emergence can be found in the work of Cariani [14]. 2 In our work (if not stated otherwise), we understand the terms “micro-state” or “micro-speciŽcation” as descriptions of the system elements at some level (mostly the agent level), that is, its static properties and behavior along with the interaction of its elements, and by “macro-state” the structure or behavior that is observable at the higher level (mostly the multiagent level) of observation and that is the result of the micro-speciŽcation.

° c 2003 Massachusetts Institute of Technology

ArtiŽcial Life 9: 41–65 (2003)

A. Kub´Ok

Toward a Formalization of Emergence

Emergence, relative to a model, is primarily based on Rosen’s concept of emergence [49]. According to Rosen, robotic systems can surpass the limited capacities of formal-computational systems in producing emergent behavior. In this framework, formal computational models are non-emergent; adaptive systems (mainly robotic systems) can be described by the different syntax (parameters and behavioral rules) of the original description (call this syntactic emergence); and the most complex systems are evolutionary devices where new observables are needed to cope with changes in the system (call this semantic emergence). Rosen also proposes a distinction between combinatoric and creative emergence. The former refers to a new recombination of existing symbols (e.g., agent properties) in the existing observed system, while the latter concerns introduction of new primitives (observables) into the system along with the establishment of their relationship to the previously existing ones [13, 12]. The preceding deŽnitions lack a common basis of comparison. It seems that they overlap in some way, but it is unclear how. It is questionable whether evolutionary systems can produce new primitives and syntactic relationships among them in a way that computational systems cannot. There is no proof that computational systems (especially devices with super-Turing power [55]) cannot achieve what evolutionary systems can do. The power of evolutionary systems, the best example being natural selection, rests on the fact that these systems consist of massively parallel processes that try huge numbers of (computational) alternatives over vast time horizons. They are deŽned in a different manner from traditional Turing machines (in their inputs and outputs) and differ in the computational complexity of their computing.3 Deviation of the system’s behavior from the observer’s model is a consequence of these facts. Previous deŽnitions say nothing about possible general sources of behavior in complex systems and do not help us constructively to Žnd important sources (if they exist) of their differentiation. Baas proposes a formal deŽnition of emergence [4] that can be summarized as follows. Let us have a family of structures fSi g where i 2 J ( J is some index set), a family of interactions Int over Si , and an observational mechanism Obs. New higher-level structure can result from the observation of the given structure at a lower level. For example, 1 the structure S 2 can be constructed from Si11 ; i1 2 J1 , as follows: S 2 D R.Si11 ; Obs ; Int 1 /, where R stands for the result of the construction process. Then P is an emergent property of S 2 iff P 2 Obs 2 .S 2 /;

but

2 1 P2 = Obs .Si1 /

for all i1 :

In other words, P is a property that is observable at one level but not at a lower level of description. Baas distinguishes two types of emergent phenomena: ² Deducible, or computable, emergence occurs when there is a deductive or

computational process or theory D such that P 2 Obs 2 .S 2 / can be determined by D from .Si11 ; Obs 1 ; Int 1 / [4, p. 519]. As examples, Baas mentions thermodynamic systems and examples from the Želd of mathematics.

² Observational emergence occurs when P cannot be deduced as in the previous

case. Examples include G¨odel’s incompleteness theorem, which says that for some formal systems there can be true statements that cannot be deduced from the system of existing (known) true statements, and the semantic compositionality in languages (i.e., where the semantics of a word can be computationally derived from the semantics of the symbols constituting it).

3 For contemporary ideas on the computational potential of super-Turing machines and the state of the Church-Turing thesis, see the work of van Leeuwen and Wiedermann [55].

42

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

Baas does not deŽne any of the above-mentioned terms that have only symbolic counterparts (structure, interaction, observational mechanism). These are to be interpreted by the researcher or the observer of the system. Here the emergence of some property in the multiagent system is apparent only if it is not observable at the lower level of observation. This opens the possibility for any multiagent phenomenon to be emergent only because one or more agents are present beyond those at the lower (agent) level of description [29]. There can be other interesting properties that change only quantitatively (e.g., time savings [36]) and that cannot be explained by producing new structure in the studied system. As for Baas’s two types of emergence (deducible and observational), we think both are of a philosophical nature, because there is no reason (at least at present) to think that there are phenomena not reducible to micro-macro relationships. Our ignorance about micro-macro deductions cannot be obviated by declarations that such deductions do not exist. Bedau [6, 5] deŽnes weak emergence as follows. Given a system S and its microdynamic D that governs the time evolution of S, the “macrostate P of S with microdynamic D is weakly emergent iff P can be derived from D and S’s external conditions but only by simulation” [6, p. 378]. This deŽnition, even if not formal, has the potential to capture the idea of macro-states being derivable from micro-speciŽcation of the system. We try to elaborate on this idea in our work. Ronald, Sipper, and Capcarr`erre [47] present a test of emergence consisting of three phases: 1. Design. The goal of this phase is to model the behavior of agents. In a language L 1 a designer describes individual agents, their environment, and their mutual interactions. 2. Observation. The observer who is fully aware of the design describes global behavior of the multiagent system in a language L 2 distinct from the language L

1.

3. Surprise. This phase indicates the gap between the behavior of individual agents and the global behavior of the whole society. The causal link between them as well as between the above-mentioned languages is inobvious to the observer and is the source of the emergent property of the multiagent system. This view tries to associate the moment of surprise with the emergent phenomenon. Emergence consists in the fact that we cannot describe (predict, expect) the behavior of the whole system from the description of its individual components. Some loosely depicted categories of emergence phenomena based on the concept of surprise can be found in [48]. This deŽnition can be related to Rosen’s concept of emergence in that the system is not reducible to the properties and interactions of the components and it deviates from the observer’s description of it. We believe the category of surprise obscures emergent phenomena. As a consequence there is a tendency to consider emergence as a property of the system that “cannot” be reduced to the lower level of description (i.e., properties of the agents and their interactions). Another consequence is that one can only describe as emergent those phenomena for which we lack a satisfactory notion of how they work. The most profound treatment of emergence, containing many inuential ideas, can be found in the recent monograph on the subject by Holland [31]. We are inspired by Holland’s work on four main points: 1. A multiagent system (MAS) approach, the system being decomposable into parts with autonomous behavior (viz. the agents). Agents are very often characterized by rule-based behavioral descriptions. ArtiŽcial Life Volume 9, Number 1

43

A. Kub´Ok

Toward a Formalization of Emergence

2. Use of the reduction principle that the macro behavior of an observed system is reducible to the interactions of its components. 3. Heavy reliance on the fact that the whole system generates richer behavior than the sum of the behaviors of its components. 4. The inessentiality of the moment of surprise in revealing emergent behavior. Holland builds models of MASs with inherent emergent phenomena and emphasizes the importance of formal blocks in the explanation theory of emergence. Building blocks represent formal pieces of models we build to understand the underlying system. They have their own states, laws of composition to build more complex structures, laws of dynamics, and reusability. Holland writes: “Building blocks range from mechanisms in physics to the way we parse the environment into familiar objects; they provide a way of extracting repeatable features from the perpetual novelty that attends systems exhibiting emergece” [31, p. 224]. Basically, agents, their behavioral rules, and their mutual interactions deŽne complex systems, and this “gives us a common way of describing the diverse rule-governed systems that exhibit emergence” [31, p. 6]. The rest of the paper is organized as follows. In the next section we outline the framework for the categorization of emergence, give the informal deŽnition of the most basic type of emergence in multiagent systems, and elaborate on what the reader should (and should not) expect from the present work. The third section contains preliminaries of the formal languages and grammar systems theory necessary for understanding the deŽnitions used. In the fourth section we present a formal deŽnition of the basic type of emergence and give arguments why the language-theoretic approach could be interesting in the study of emergence. In the Žfth section we present some examples of different types of emergence in multiagent systems and show how our theory can be applied to modeling multiagent systems formally and how our theory reveals the source and type of emergence at hand. In the sixth section we discuss how our deŽnition Žts with other work on emergence, summarize the present work, and present our conclusions. 2

Emergence in Multiagent Systems

In relation to the study of emergence, the previously described works suffer from one or more of the following drawbacks: ² They treat emergence in an informal and intuitive manner. This concerns a large

volume of scientiŽc literature where emergence is explained without reference to any theory of emergence [8, 9, 10, 33, 40].

² The deŽnition heavily depends on the term “surprise” [47, 48]. ² The deŽnition either is too broad and so includes phenomena that are not

emergent, or is too strict and so omits phenomena that are emergent [4].

² The categorization is not Žne enough or is based on different criteria so that we are

unable to distinguish among different types of emergence or identify the source of the emergent behavior [5, 14, 47].

² It does not refer to a uniŽed framework for research on emergence [4, 5, 47]. ² It fails to deŽne “sum of the behaviors of individual parts,” a crucial point in

deŽning emergence. We know of no attempt to deŽne this concept.

44

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

² There is no modeling technique to both design and study (analyze) emergent

phenomena (i.e., to capture emergence constructively) in MASs, except computer simulations. Even by that Želd, no results have been achieved.

We think anything to be called an emergence theory should be guided in the following way: ² Formal treatment. In the beginning, informal discussions are Žne to clarify some

ideas concerning the problem. Nevertheless we ultimately need a formal theory with well-deŽned meaning that can be used in any context without loss of precision. Formal deŽnitions are also needed to unify our vocabulary on issues concerning emergence. Before now there has been no common understanding of what emergence is, how to study it, or what different types of emergent phenomena exist.

² Emphasize construction. We need to have a tool to construct models in accordance

with formal deŽnitions of emergence. Only if we are able to build artiŽcial models of studied systems in a commonly deŽned way can we verify and validate models. The gap between the language of model construction and a language of model explanation can be a source of misinterpretations and fallacious deductions.

² Ignore surprise. We think that judging the behavior of complex systems on the

basis of our subjective feeling of surprise is misleading and obscures better explanations. The standpoint of an observer is different from that of a constructor (or modeler) in that the former lacks information about the studied system. The moment of surprise can fade away once sufŽcient information is provided.

In the study of emergence it is important to distinguish different sources of the macrobehavior, that is, the behavior of the whole observed system that is due to interactions of agents with each other and with the environment. The sources of emergence thus can be agent properties, inter-agent interactions, the inuence of the environment on the agents’ actions, and ongoing evolutionary processes on the part of the agents as well as the environment. This can happen on various hierarchical levels of organization of the MAS. Based on this idea, we distinguish these Žve categories of MASs: 1. Agents interact in a static environment. The environment has no active role in the system and offers no feeback to agents. The behavioral rules of the agents do not evolve. 2. The environment plays an active role in the system and directly or indirectly inuences agents’ actions. Both agents and the environment are non-evolutionary. 3. The agents evolve in a static environment. The agents’ properties and behavioral rules change with time. 4. The agents evolve in an active environment. 5. Both agents and environment change their behavior (new properties as well as new behaviors come into existence). These categories span the simplest to the most complex MASs. Emergence can have different properties depending on the source of macro-patterns in the system. This, in turn, implies a natural categorization of different types of emergence. ArtiŽcial Life Volume 9, Number 1

45

A. Kub´Ok

Toward a Formalization of Emergence

Our multiagent modeling paradigm consists of autonomous units—agents—interacting with each other as well as with an environment.4 The agent is an abstraction of a programming procedure, process, organism, or any other unit that perceives its environment with sensors and brings about changes in it by means of effectors. The agent acts autonomously in order to fulŽll its internal goals (goals can be designed by the modeler). The agents can be very simple, characterized by reactive (using a memory) or purely reactive (memory-free) behavior, or they can be more complex, engaged in reasoning and planning. The most complex category comprises social agents that negotiate with other agents over conicts or mutual plans. The environment is a common structure where agents act and interact. It can play an active or a passive role, as mentioned above. Sometimes we can look at the environment as a special kind of agent with global inuence on other agents (e.g., a law-giving body in the human society). MASs can thus model cellular automata, systems of physical particles, neural networks, software applications, organisms, ecosystems, economic or other social systems, and so on. In this work we present a deŽnition of emergence that is based on a well-known idea from the literature on emergence [31]. We model it in the context of the simplest of the MASs described above. We will call this emergence basic emergence. We will later show how the deŽnition can be extended to more complex types of multiagent systems. We will show how in the framework of grammar systems it is possible to study MASs and Žlter out different sources of emergence. But we do not elaborate on every kind of emergence that can be observed in complex systems. Nor do we provide a general treatment of evolutionary processes in MASs. Nor do we address the theory of hierarchies, even though this is an important aspect of emergent phenomena.5 To study ongoing emergent phenomena in MASs we must design a language for describing agents and environment. The alphabet (or basic blocks) of the language and its syntax will give rise to constructs by means of which we can describe the behavior of the whole system. The behavior of the system is an effect of agents’ interactions with each other and with the environment. We try to capture emergence both formally and constructively. We propose a way to model MASs formally and, at the same time, to study their macro-properties. Thus we can unify the framework for construction as well as the observation and analysis of MASs. The deŽnition proposed below Žts some phenomena that at Žrst glance seem to be non-emergent because we can describe them adequately with existing methods (e.g., differential equations). But we believe, contrary to what many think, that emergence is not primarily a matter of inexplicability. We hold that there are phenomena that are emergent even though we understand the internal mechanism that produces them (as in the case of direct cooperation among agents). 2.1 Informal DeŽ nition of a Basic Emergence In this section we clarify our deŽnition of basic emergence. We use this deŽnition to formally deŽne emergent phenomena that are due to agent interactions in the environment [31]. By basic emergence, we mean behavior reducible to agent-to-agent interactions without any evolutionary processes involved (i.e., an agent’s behavioral set stays the same during the modeling and the analysis of the system). The environment has no rules of behavior and is changed only by the actions of agents. Our deŽnition thus concerns groups of phenomena that can be modeled by MASs of the Žrst type listed earlier. In the next sections we try to clarify the idea of a uniŽed model or anal4 A good introduction to MASs is presented by Wooldridge [56]. 5 Some attempts to address this hard problem can be found in [4, 3, 11, 28, 39].

46

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

ysis approach to a problem of emergence. We treat the basic type of emergence in a formal framework of language and grammar systems theory. Let us consider a MAS composed of the environment and some agents. Basic emergence then refers to a property of the system that can be produced by interactions of its agents (components) with each other and with the environment and cannot be produced by summing behaviors of individual agents in the environment. In this manner we can study the effects of pure inter-agent and agent-to-environment interactions. If we focus on the activity of different parts of the system (agents, environment, evolution, external stimuli), we can ceteris paribus trace the sources of emergence in the modeled natural or artiŽcial system. This deŽnition can be extended to cope with more complex multiagent systems as well. 3

Theory of Formal Languages

Before we deŽne basic emergence formally, we give some requisite notions and deŽnitions from the theory of formal languages and grammar systems. 3.1 Grammar Systems as Formal Models of Multiagent Systems Formal language theory studies the properties of formal languages that can serve as an abstract model of a computational device. Every grammar can generate some language and every language can be generated by some grammar. One of the concerns is generative power, that is, how to construct the simplest grammars to generate complex languages and what their relationship is to more general models of computational devices such as Žnite automata or Turing machines. At present there are a vast number of different theoretical models of formal languages [51], mostly centered around the Chomsky hierarchy of formal languages [15]. Every formal language can be generated by one or more grammars with given features. The grammar can be thought of as a computational device consisting of a set of rewriting rules that operate on a tape of symbols. Most of the models of formal grammars distinguish nonterminal and terminal symbols (those that can and cannot be rewritten). The strings consisting only of terminal symbols that a grammar can produce are called words, and the language deŽned by a grammar is simply the set of its words.6 The situation becomes more complex when we consider more than one grammar operating on one (or more) common tape(s). In this case we talk about the grammar systems. Grammar systems are symbolic devices composed of a set of elements (grammars) that interact with each other by means of the tape where they rewrite the symbols. This paradigm can be used to formally model multiagent systems [17]. Several grammars (thought of as agents) operate on the symbolic tape (the environment) and bring about changes in it by means of rewriting rules (the behavior of agents). The grammar system then can be looked upon as a MAS with given properties. There is a broad range of grammar systems distinguished by their component grammars, the types of their communication, rewriting modes, and the number of tapes they share. Here the interesting thing is that the whole grammar system can generate a different language than its components. For elements of formal language theory the reader is referred for example to [52, 54]. 3.2 Chomsky Grammars Now we give some explanations concerning formal languages and grammar systems. For a Žnite alphabet V of symbols or letters, by V ¤ we denote the set of all strings over V . The empty string is denoted by ¸, and V ¤ ¡ f¸g is denoted by V C . The length of a 6 For more on formal language theory the reader is referred to [52, 54].

ArtiŽcial Life Volume 9, Number 1

47

A. Kub´Ok

Toward a Formalization of Emergence

string x 2 V ¤ (the number of letters occurring in x ) is denoted by jx j. The number of symbol occurrences U µ V in x 2 V ¤ is denoted by jx jU . By u ¢ v, where u; v 2 V ¤ , we denote the operation of string concatenation. In this article we omit the concatenation symbol ¢ and write uv. A Chomsky grammar [15] is a quadruple G D .N ; T ; P; S/;

(1)

where N is a nonterminal alphabet, T is a terminal alphabet, P is a set of rewriting rules (productions) in the form x ! y, and S 2 N is an axiom (starting symbol). A direct derivation in G is denoted by H) or H)G . The transitive and reexive closures of the relation H) are denoted by H) C and H)¤ , respectively. A language L over V is a subset of V ¤ . The operations of union, intersection, and complementation are deŽned over languages as usual. The language generated by G is a construct ¤ ¤ L.G / D fw j S H)G w; w 2 T g:

(2)

The elements of the formal language are called strings or words. 3.3 Cooperating Grammar System A cooperating grammar system (or grammar system for short) is a construct of grammars (agents) mutually rewriting strings of symbols on a common tape [17]. The basic principles are inspired by distributed problem-solving models with blackboard architecture. Each agent rewrites a portion of the tape as is usual in the case of individual agents. Grammars work with different cooperation strategies (how grammars are allowed to rewrite the symbols on the tape and whether they can communicate directly or not) and modes of derivation (when the process of derivation stops). In some cases the environment can have its own rewriting rules and inuence the behavior of agents (these are so-called eco-grammar systems; see, e.g., [19, 20]). It is interesting to study what kind of language can be generated by the whole grammar system in comparison with the languages generated by individual grammars. A grammar system is a formal computational device with a certain generative power (qualiŽed by the group of languages into which the generated language falls), in some cases equivalent to a Turing machine. Formally, a cooperating grammar system is a construct 0 D .N ; T ; S; P1 ; P2 ; : : : ; Pn /;

(3)

where N is a nonterminal alphabet, T is a terminal alphabet, S 2 N is a starting symbol, and P1 ; P2 ; : : : ; Pn are Žnite sets of rewriting rules over N [ T . A basic derivation step is a relation H) Pi : x H)Pi y

iff

x D x1 ux2 ;

y D x1 vx2 ;

x1 ; x2 2 .N [ T /¤ ;

u ! v 2 Pi :

(4)

Then one can deŽne derivations of arbitrary length .H) ¤Pi / and, for k ¸ 1, derivations ¸k ·k of exactly k steps .H) Dk Pi / and of at least or at most k steps (H) Pi , H)Pi , respectively), as well as the maximal derivation: x H)tPi y x

H)¤Pi

48

iff

y and there is no z 2 .N [ T /¤ such that y H)Pi z :

(5)

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

A basic derivation step in a grammar system deŽnes how a derivation of strings on the tape proceeds when more than one agent operate over it. Let F D f¤; t g [ f· k; D k; ¸ k j k ¸ 1g: For any cooperating grammar system 0 with at most n components and f 2 F , the language generated by 0 in the cooperative mode f is f

f

f

¤ Lf .0/ D fx 2 T j S H) Pi1 x1 H) Pi2 x2 ¢ ¢ ¢ H)Pim xm D x ;

m ¸ 1; 1 · ij · n; 1 · j · m g:

(6)

The derivation in a grammar system proceeds in two basic derivation modes: parallel and sequential mode. If the agents rewrite in a parallel manner, synchronization is needed, as in discrete devices that share common resources. The agents thus choose the portion of the string that is to be rewritten, and then the rewriting takes place at once. The same symbol cannot be rewritten by two or more agents at the same time. The synchronization presents an internal clock of a grammar system as well as a conict resolution mechanism. If the agents rewrite in a sequential manner, they do not have to be synchronized, because at each time tick each agent gets a chance to act over the tape without conicts. 3.4 Array Grammar System In the preceding subsection we assumed the use of a one-dimensional tape of symbols. Here we introduce array grammars, which use a two-dimensional tape instead. Array grammars can serve as two-dimensional models of the environment. Every symbol on the tape can be identiŽed by its index in a two-dimensional array of symbols. The array of symbols can be extended beyond the blank (background) symbols #, and its size can vary accordingly. The components of an array grammar system are array grammars that are characterized by the form of their rewriting rules. The left and right sides can be in the form of an array of symbols. For more about array grammar systems see for example [21, 24, 26]. Informally an array of symbols is a set of pairs of point coordinates together with the corresponding symbol placed at that point on the tape. Let Z denote the set of integers, and let V be an alphabet. Then an array A over V is a function A: Z 2 ! V [ f#g, where support.A/ D fv 2 Z 2 j A.v/ 6D #g

(7)

is a set of points with coordinates that do not contain the blank (background) symbol #2 = V . We can write A D f.v; A.v/ j v 2 support.A/g:

(8) 2

The set of all two-dimensional nonempty arrays over V will be denoted by V C . Any 2 subset of V C is called an array language. The arrays are words of array languages. 2 For an array A 2 V C and a Žnite pattern ® of symbols over V [ f#g, we say that ® is a subpattern of A if we can superimpose ® on A in such a way that all vectors of ® marked with symbols from V coincide with the corresponding symbols in A and each blank symbol # in ® corresponds to a blank symbol # in A. ArtiŽcial Life Volume 9, Number 1

49

A. Kub´Ok

Toward a Formalization of Emergence

An array grammar is a construct GAr D .N ; T ; #; P; f.v0 ; s/g/;

(9)

where N ; T are alphabets composed of nonterminal and terminal symbols, respectively; # is a blank symbol; P is a Žnite set of rewriting rules ® ! ¯, where ®; ¯ are array patterns over N [ T [ f#g; and f.v0 ; s/g is a starting array with the starting vector v0 2 Z 2 and the starting symbol S 2 N . For an array grammar GAr D .N ; T ; #; P; f.v0 ; s/g/ and 2 two words A; B 2 .N [ T /C , we deŽne the relation A H) B to hold if there is a rule ® ! ¯ 2 P such that ® is a subpattern of A and such that B is obtained by replacing ® in A by ¯. By H)¤ we denote the reexive and transitive closure of H). The language generated by an array grammar is a construct 2

C ¤ L.GAr / D fA 2 T j f.v0 ; S/g H) Ag:

(10)

A cooperating array grammar system is a cooperating grammar system with array grammars (grammars with array rewriting rules). Formally it is an .n C 4/-tuple GS Ar D .N ; T ; #; f.v0 ; S/g; P1 ; P2 ; : : : ; Pn /;

(11)

with the components deŽned as above. In a cooperating array grammar system, array grammars rewrite the tape in a parallel manner in that they do not disturb each other, that is, one symbol cannot be rewritten by more than one production rule of array grammars. Formally, for a subset of array grammars GROUP D fAi ; 1 · i · n g and 2 two arrays D1 ; D2 2 V ¤ [ f#g, a direct derivation step, denoted by D1 H)GROUP D2 , exists if and only if there exist array productions pij 2 P i , 1 · i · n, 1 · j · li ( j th rule of ith array grammar), pij D ®ij ! ¯ij , such that for any array symbol !1 with index vk , 0 · k · r £ s ¡ 1, r; s 2 Z , that is a subpattern of ¯ij 1 and is not a subpattern of ®ij 1 , and for any array symbol !2 with index vm , 0 · m · r £ s ¡ 1, r; s 2 Z , that is a subpattern of ¯ij 2 and is not a subpattern of ®ij 2 , it holds that these symbols (areas) are disjoint (k 6D m). The previous deŽnition prescribes how a portion of an array tape can be rewritten in one step by an array grammar system. In each step there is a subset of agents (array grammars) that try to rewrite a portion of a tape according to their rewriting rules. Our deŽnition implies that the only condition that must be satisŽed is that the symbol to be rewritten (as denoted by the right-hand side of the rewriting rule) cannot be rewritten more than once in one derivation step. This is a means of resource locking shared by the group of agents. The choice of the agents to rewrite the tape is opportunistic in that there is no priority among agents. 4

Formal Framework of Emergence

In this section we focus on a formal model of emergent behavior in multiagent systems. As a Žrst step we give some preliminary deŽnitions necessary for further statements. 4.1 ModiŽ ed Cooperating Grammar System For our purposes we eliminate some of the restrictions on Chomsky grammars and make modiŽcations as follows: ² We do not distinguish the categories of terminal and nonterminal symbols, because

the models we would like to use do not strictly suppose that the derivation stops at some time. In this sense we use so-called “pure” grammars.

50

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

² We introduce agent and environmental symbols to distinguish the elements of

agents and the conditions (changes) they can bring about in the environment. We denote the alphabet of agent symbols by VA , and the alphabet of environment symbols by VE .

² We do not restrict agents to perform a speciŽed number of steps on the tape. ² We omit the application of a Žrst rewriting rule (it is not included in the set of

agents’ rewriting rules) that represents rewriting of a starting symbol. Instead we start with the conŽguration on the tape as a consequence of the Žrst rewriting.

4.2 The Sum of the Agents’ Behaviors It is very difŽcult to deŽne the sum of the agents’ behaviors in MASs, because there is no computational tool to do the job. The natural idea would be to enumerate what the agents can do individually. Thus we can produce a set of words that can be generated by agents if they do not interact with each other. The union of the agents’ languages is a candidate for the summation of their behaviors. We modify this idea in that we propose the superimposition of agents’ languages instead. This can be interpreted as a sum of conditions the agents can bring about in the environment if they act individually in the environment. What follows is an attempt to deŽne this idea formally. Let W1 D a1 a2 ¢ ¢ ¢ an , W2 D b1 b2 ¢ ¢ ¢ bm , and Wsupimp D c1 c2 ¢ ¢ ¢ cl be words of symbols ai ; bj ; ck , 1 · i · n, 1 · j · m, 1 · k · l over .VA [ VE /C . It holds that l D n iff n ¸ m, else l D m (the index of the last symbol in the resultant word is the same as the index of the last symbol in the longer of the two input words). The superimposition of the word W1 on the word W2 is a function superimpose: [W1 ; W2 ] ! Wsupimp , and we have: 1. if ai 2 VA then ck D ai ; 2. if ai D ² then ck D bj ; 3. if bj D ² then ck D ai ;

4. if ai 2 VE and bi 2 VE then ck D ai ; 5. if ai 2 VE and bj 2 VA then ck D bj .

We shall write W1 superimpose W2 . For n languages L1 D fW1 2 .VA [ VE /C g, L2 D fW2 2 .VA [ VE /C g; : : : ; Ln D fWn 2 .VA [ VE /C g their summation is a language that results from a superimposition over the permutations of n words from the set of n languages: Lsum D fWsum 2 .VA [ VE /C j Wsum

D W1 superimpose .W2 superimpose .W3 ¢ ¢ ¢ .Wn¡1 superimpose Wn /// [ ¢¢¢

(12)

[ Wn superimpose .Wn¡1 superimpose .Wn¡2 ¢ ¢ ¢ .W2 superimpose W1 ///g: The deŽnition above states that if we take n-tuples consisting of the words of the languages the agents generate (each word is from a different language), we can superimpose them in such a way that agent symbols have priority over environmental symbols (they cannot be covered by the symbols of the environment). Any nonempty symbol has priority over the symbol ². ArtiŽcial Life Volume 9, Number 1

51

A. Kub´Ok

Toward a Formalization of Emergence

To clarify these deŽnitions, we show a simple example. Consider the alphabet of agent symbols VA D fa1 ; a2 ; a3 g, the environmental symbols VE D f f; o g, and three agents generating the following languages. Agent A1 generates the language L1 D ffa 1 of g, agent A2 generates the language L2 D foa 2 ff g, and agent A3 generates the language L3 D ffoffa 3 g. Then the summation of the agents’ behaviors will be the language Lsum D ffa 1 ofa 3 ; oa 2 ffa 3 ; fa 1 ffa 3 ; fa 2 ffa 3 g If we had grammars that could represent agents moving in the environment (twodimensional grid tape), the individual languages would contain words containing the agent symbols and other environmental symbols. The language generated by the superimposition of agents’ languages would contain words composed of possibly all (if they do not overlap) of the agents’ symbols plus environmental condition symbols. The operation of superimposition seems to be artiŽcially deŽned. Nevertheless it is only a slight alteration of the operation of the union of languages to include all of the agents in the sum of the agents’ behaviors. The superimposition of agents’ languages is equivalent to the union of languages if the generated strings are of the same length and we use only one of the agent or environmental symbol sets. 4.3 A Formal DeŽ nition of a Basic Emergence After a short introduction to basic notions and deŽnitions from the theory of formal languages, we give a formal deŽnition of basic emergence in this subsection. Let MAS D .VA ; VE ; A1 ; A2 ; : : : ; An ; S/

(13)

be a MAS modeled by a modiŽed cooperating grammar system in the following way: VA is an alphabet of agent symbols, VE is an alphabet of the environment, V D VA [ VE is an alphabet for describing MAS, S is a start description of the environment over V C , and A1 ; A2 ; : : : ; An is a Žnite set of agents. An agent is a construct (pure modiŽed grammar) Ai D .Vi ; Pi ; Si /;

(14)

where Vi µ V is an alphabet of an agent, Si is a start description of an environment, and Pi is a set of rewriting rules deŽned in the form as follows: The agent can derive u H) v , where u; v 2 V C , and there is a rule ® ! ¯ 2 Pi such that ® is a subpattern of A, and B is obtained by replacing ® in A by ¯. The behavior of an agent Ai is a language generated by an agent and denoted by C ¤ L.Ai / D fw 2 V j Si H) w g:

(15)

The events in the environment (derivation of words on the tape) proceed in MAS in a parallel (or possibly sequential) manner such that the agents can rewrite the part of the tape (environment) without disturbing each other. If there are rewriting rules for agents that have to be applied in parallel, then they cannot rewrite the same symbol at the same time. Observe that it is not necessary that the left and right sides of rewriting rules applied in parallel be disjoint. Let GROUP D fAi j 1 · i · n g. If L.MAS / D fw 2 V C j S H)GROUP w1 H) GROUP w2 ¢ ¢ ¢ H)GROUP w g is a language generated by MAS, and Lsum is the language generated by the superimposition of the languages fL1 ; L2 ; : : : ; Ln j 1 · i · n g, then MAS can be 52

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

characterized as having the property of basic emergence iff 9w 2 L.MAS / such that w 2 = Lsum . The deŽnition above states that if the multiagent system as a whole can generate a language (behavior) that cannot be generated by the superimposition (summation) of individual agents’ languages (behaviors), we can characterize it as having an emergent property. Note that we do not compare the union of languages produced by individual grammars with the language of the unions of grammars. The grammar system is not a union of grammars. 4.4 Why Grammars In this subsection we give some arguments supporting our deŽnition of basic emergence and suggesting why a language-theoretic approach could be interesting in the study of emergence. The developments in the last two decades in distributed computing and decentralized systems have motivated research on grammar systems. The main contribution is a formal description and modeling of multiagent systems [17]. Its main advantage is that it presents us with the common modeling base in that we deŽne the alphabet and rewriting rules for all the parts of the modeled system and everything else is the result of rewriting derivations. The micro-structures of the model (the alphabet and the rewriting rules) lead directly to macro-patterns observable on the system level (the generated language). We do not have to use two languages for describing the parts and the wholes, respectively. Rewriting rules is a very natural way to describe the action of agents, especially in case of reactive agents [31].7 The good thing is that we can extend the model of a MAS along with the deŽnition of emergence according to the complexity of the system. Thus we can introduce into the model communication [36], internal structure of the agents (memories, reasoning mechanisms), or the activity of the environment as in the previously mentioned ecogrammar systems [16, 19, 20], and at the same time we are not forced to apply all of the principles inherent in these models. It is possible to change the structure of the environment to two, three, or even more dimensions.8 In this article the environment is represented as one tape, because the agents share the environment. It is possible to divide it so that the agents will act only on some speciŽed portion of the environment. It is also possible to model internal models (memories) of the agents, as in the blackboard architecture of distributed systems [18]. Grammar systems are formal devices that can even have the power of a Turing machine. They are discrete computational models and can easily be rewritten directly into computer code. Thus, with more complex models it is possible (and often necessary) to rewrite the grammar model into the computer simulation. The drawback of this solution is the possible loss of power of the formal device. In the future we hope to use grammar systems in the theory of hierarchies of complex systems where the generated languages on one level can become parts of the alphabets for the systems on the higher levels of description. But this is now a very hard problem. The distinction of agent from environmental symbols and the operation of superimposition of languages enable us to Žlter out some phenomena that are not emergent in the sense we present here. This sense can be characterized as the stochastic property of emergence [35]. The deŽnition of basic emergence above uses the simplest model of the multiagent system because it is intended to be a basic building block of the future uniŽed framework. Also, this way we can show whether basic emergence derives purely from the interactions of agents. 7 This is the most common type of parts of the observed system from the point of view of emergence, as found in neural networks, cellular automata, Ž sh schools, chemical systems, and so on. 8 On the deŽ nition of basic types of emergence with modiŽ ed array grammar systems working on the two-dimensional tape and how it can be used in some of the cases of evolutionary systems, see [36].

ArtiŽcial Life Volume 9, Number 1

53

A. Kub´Ok

5

Toward a Formalization of Emergence

Examples of Emergence

In this section we present several examples that illustrate the deŽnitions earlier given. We give one detailed example of basic emergence occurring in cellular automata. Other examples are modeled grammatically elsewhere, and we refer the reader to this work in following subsections. We also present one example to show non-emergent behavior in a MAS communicating by means of stigmergy. 5.1 Cellular Automata Cellular automata (CAs) offer a nice example where the grammar system approach reveals the basic type of emergence. In CAs the state of each cell in a two-dimensional grid is completely dependent on the state of the neighboring cells (e.g., von Neumann neighborhood or Moore neighborhood), and the state change occurs discretely at the same time for each cell. Perhaps the most-cited two-dimensional cellular automaton is Conway’s game of life (see [7, 27, 44]). Here a cell can be in one of two states— dead or alive. A dead cell becomes alive if three neighboring cells were just alive, and otherwise remains dead. A living cell remains alive if two or three neighboring cells were just alive, and otherwise it dies. These simple rules lead to a variety of spatial structures that exhibit regularities (or irregularities), depending on the initial state of the cells.9 We will model the game-of-life CA as a MAS of cells (very simple agents) acting autonomously according to their rules on the two-dimensional grid (the environment). 5.1.1 A Glider We concentrate on a grammar analysis of one of the most-cited patterns from the game of life—the glider. It is a period-four pattern moving diagonally one cell per period. The game of life will be modeled by the construct10 GA D .VA D fD; Ag; VE D f f g; A1 ; : : : ; A16;

f.v0 ; D/; .v1 ; A/; .v2 ; D/; .v3 ; D/; .v4 ; D/; .v5 ; D/; .v6 ; A/; .v7 ; D/; .v8 ; A/; .v9 ; A/; .v10; A/; .v11 ; D/; .v12 ; D/; .v13 ; D/; .v14; D/; .v15; D/g/;

where VA is the set of agent symbols denoting its state (D for dead, A for alive), VE is the environmental set containing the symbol for a free space (when there is no agent occupying the cell), A1 ; : : : ; A16 is the set of agents’ behavioral rules, and the set f.v0 ; D/; .v1 ; A/; .v2 ; D/; .v3 ; D/; .v4 ; D/; .v5 ; D/; .v6 ; A/; .v7 ; D/;

.v8 ; A/; .v9 ; A/; .v10 ; A/; .v11 ; D/; .v12 ; D/; .v13; D/; .v14; D/; .v15 ; D/g

is a starting description of the environment. The environment in this case is modeled as a 4 £ 4 non-extensible array of cells that forms a torus [we do not use the symbol #2 = .VA [ VE /]. Every cell in the array has its index and can contain just one agent in one of the permissible states. The starting array can be spatially represented by the 9 Nice examples and how they relate to emergence can also be found in [6, 31]. 10 The size of the environment (tape) can be adjusted arbitrarily.

54

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

following construct: D

A

D

D

D

D

A

D

A

A

A

D

D

D

D

D

The set of rewriting rules of each agent is the following: 8 f > < Ai D f > : f

f

f

A

f

f

f

A

D

D

A

A

D

D

D

D

A

D

D

A

D

D

D

D

D

D

D

D

A

A

D

D

D

D

!

f

f

f

f

f

f

f

A

f;

f

D

f

f

f

f

f

f

f

!

!

!

!

A

D

D

D

A

A

A

A

D;

D

A

D

D

D

D

A

D

D

A

D

D

D

A

A

A

D

D;

D

D

D

D

D

D

A

D

A

D

D

D

D

A

A

A

D

D;

D

A

D

D

D

D

A

D

A

D

D

D

A

D

D

D

A

A

!

f

f

f

f

D

f ;

f

f

f

D

A

A

D

A

D;

A

D

D

D

A

A

D

D

D;

A

D

A

D

A

A

!

D

D

D;

A

D

A

D

D

D

A

A

D; : : :

D

A

A

!

!

j

9 > =

1 · i · 16 : > ;

The Žrst two rules mean no change if the agent (in the middle of the grid) is alone in the environment. The third through sixth rules represent situations in which the agent remains in the same state as in the previous step. The seventh and eighth rules depict how the agent can switch from the live to the dead state. The last rule represents the reverse process—how the agent can become alive. The important point is that each agent rewrites only one cell at a time, which is different from each other cell, and it checks only the eight neighboring cells (in the Moore neighborhood). A sequence of a rewriting process in GA can look like this:

D

A

D

D

D

D

A

D

A

A

A

D

D

D

D

D

H)

D

D

D

D

A

D

A

D

D

A

A

D

D

A

D

D

ArtiŽcial Life Volume 9, Number 1

H)

D

D

D

D

D

D

A

D

A

D

A

D

D

A

A

D 55

A. Kub´Ok

H)

H)

H)

H)

Toward a Formalization of Emergence

D

D

D

D

D

D

D

D

D

D

A

D

D

A

D

D

D

D

A

D

D

D

D

D

D

D

A

A

D

D

D

A

D

A

D

A

D

A

A

D

D

A

A

A

D

D

A

A

D

D

A

A

D

D

A

A

A

D

A

A

D

D

D

D

D

D

D

D

D

D

D

D

D

D

D

A

D

D

A

D

D

D

D

A

D

A

D

A

A

D

D

A

A

D

D

D

A

D

D

A

A

D

A

D

A

A

D

D

D

D

D

A

A

D

D

A

A

D

D

A

D

D

D

D

D

D

D

D

D

D

D

D

A

D

A

D

A

D

D

D

D

D

D

A

D

A

D

D

D

A

D

A

D

A

D

D

A

A

D

A

A

A

D

D

D

A

D

A

D

D

D

D

A

D

D

D

A

A

D

D

A

D

D

D

D

D

D

D

D

D

D

D

A

D

D

D

D

A

D

D

D

A

A

D

D

D

A

D

A

A

D

D

A

A

A

D

D

D

D

D

D

D

D

D

H)

H)

H)

H)

H)

H)

H)

H)

H)

H)

H)

¢¢¢:

We can see that in a four-step period we get back the original pattern in a different place on the tape.11 From the starting conŽguration GA can generate the language containing the words L.GA/ 8 D > > > > A > > > : D

A

D

D

D

D

D

D

D

A

D

A

D

A

D

A

A

D

D

A

A

D

D

D

D

D

A

D

D

D

D

D

D

D

D

D

A

D

D

D

D

D

A

D

A

A

A

;

;

D

D

D

D

D

D

A

D

A

D

A

D

D

D

A

A

A

D

D

D

D

D

D

D

D

A

D

A

D

D

A

A

;

;

D

D

D

D

D

A

D

D

D

D

A

A

D

D

A

A

D

A

A

D

D

A

A

D

D

D

D

D

D

D

D

D

D

A

D

D

A

D

D

A

D

A

A

D

D

A

;

;

;

;

11 In our case, some of the patterns are not discernible because of two-dimensional representation of the torus.

56

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

A

D

A

A

D

D

D

D

D

D

D

A

A

D

D

D

A

A

A

D

D

A

D

D

D

A

D

D

D

D

D

A

D

A

D

D

D

A

A

D

A

A

D

D

D

D

A

D

D

D

;

;

A

D

A

D

A

D

D

A

D

D

D

D

D

A

D

D

D

A

D

A

A

D

D

D

A

D

D

D

D

D

D

D

;

;

A

A

D

D

A

D

D

A

D

D

D

D

D

D

D

D

A

D

D

A

D

D

A

D

A

D

A

A

9 D> > > > D=

A

A

D

D

A

A

D

D

D

D

D

D

D

D

;

;

;

D> > > > ; D

:

These words represent the change of the environment in four periods when the agents change state in parallel. The string pattern made of the symbol A glides diagonally down the array grid. Every agent (it is unimportant which state it is in) can generate only the language containing only one word with the symbol of itself surrounded by the free space symbols, if alone in the environment. The agent occupying the array cell with the 0th12 index can generate the language

L.A1 / D

8 > >D > > f > > > : f

f

f

f

f

f

f

f

f

9 f> > > > f= f> > > > ; f

:

The agent occupying the cell with the index 5 generates the language

L.A6 / D

8 > >f > > f > > > : f

f

f

D

f

f

f

f

f

9 f> > > > f= f> > > > ; f

:

If we superimpose the agents’ languages from the initial conŽguration, we get the language

Lsum D

8 D > > > > A > > > : D

A

D

D

A

A

A

D

D

9 D> > > > D= D> > > > ; D

that represents the sum of the agents’ behaviors. The original pattern is Žxed and nonevolving if the agents do not interact with each other because they are alone in the environment. It is obvious that the language of the whole MAS (GA) is richer than the superimposed language of the agents. Thus we have a basic emergent property of the game-of-life model—the glider. 12 This is not an error. The indices of the array start with 0, though the indices of the agents start with 1 for convenient identiŽ cation of agents.

ArtiŽcial Life Volume 9, Number 1

57

A. Kub´Ok

Toward a Formalization of Emergence

5.1.2 Discussion The glider example nicely illustrates how basic emergence is brought about purely by the agent-to-agent interactions. The phenomenon depends upon the parallelism of the agents’ actions that take part in the network-like structure. Note that we could Žnd rules of interactions in the game of life that do not give rise to emergent patterns (e.g. if the pattern does not change at all). We want to reply to some objections that could be raised against the present analysis. We extended the original CA by one symbol ( f ) representing the environment. It seems that we violated the conditions in the game of life. This is because we made a multiagent model of a CA where agents act according to their rules, whereas the environment is passive. We made a distinction between agents and the environment in which they act. This is necessary in order to analyze the glider grammatically. It does not change the game-of-life principle. It just shows that parallel action (not just any interaction) is necessary in order to produce emergent behavior. If we stick to the original conŽguration where each cell is occupied by an agent, the game-of-life principle will stay untouched. Suppose we did not introduce a new (free space) symbol into the game of life. Let us consider a language that was the sum (superimposition) of the languages that can be generated by only one agent active on the grid. We still would not get the richness of the whole game-of-life language. It is true that the deŽnition of the game of life involves the interaction of agents. Nevertheless, not every conŽguration reveals an emergent property of the whole system. We wanted to demonstrate that emergence in the game of life depends on the conŽguration of agent states, not on the rules. Our goal was to show how it is possible to formally study the behavior of a complex system and Žnd out whether it exhibits emergence. Some conŽgurations of the game of life are stationary, with no agent ever changing its state. The glider or any other such pattern is interesting because it seems to be moving. But nothing is really moving. Some patterns are simply more eye-catching than others. Many more CA rules (not conŽgurations) would produce emergent behavior. We do not know why these or other rules produce this or other “moving patterns” in certain conŽguration, and we doubt that there is a general law-like answer to this question. Our analysis shows that in the game of life some conŽgurations are emergent and some are not, and that what matters is conditions in the environment and the parallel actions of agents. 5.2 Direct Cooperation Suppose a group of agents gather blocks dispersed in a closed space and collect them in a home zone. An agent’s holding capacity is 1:5 times greater than the weight of one block. Suppose they can directly cooperate in that two agents can carry two or three blocks simultaneously. To represent this system we would use a two-dimensional tape representing the environment with the home zone, agents, and blocks—the alphabet of the grammar system. The generated language would be any situation that can happen during the execution of the block collecting task. In this experiment we could observe basic emergence, because direct cooperation can occur if two or more agents meet and hold the blocks together. The language generated by the whole MAS would contain words that are not to be generated by the agents individually. The clusters of cooperative agents cannot be generated by the summation of their individual behaviors, because direct interaction is required.13 In this case the result of the task is not so interesting for the observer, because it can also be done by any of the agents individually. Besides the cooperating agents, we can also observe something that could be called time emergence in that the cooperating agents can gather the blocks in (more 13 For a language-theoretic treatment of this scenario see [36].

58

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

than linearly) decreasing time relative to the number of agents. So two agents can fulŽll the task in less than half the time it takes for one of the agents to do it alone. This example need not generate the experience of “surprise” that emergent results of agents’ interactions often produce in observers. Direct cooperation or communication in natural as well as artiŽcial multiagent systems is one of the most apparent sources of emergent behaviors that we can observe. 5.3 Collective Spatial Behavior Matari´c [40] studies collective behavior in a group of robots. The robots are homogeneous in that are all governed by the same behavioral rules. They move about in a closed arena in which pucks are dispersed. In various scenarios Matari´c studies macrobehavior of the robot society that derives from the basic robots’ behaviors considered in parallel or in sequence. These macro-patterns are not explicitly programmed into the MAS, and somehow emerge out of the robots’ interactions. We analyzed a simpliŽed form of this scenario by modeling robot behaviors by a grammar system with a stochastic rewriting mode [35]. At every moment the robots choose their actions in a stochastic manner with a certain probability, not deterministically. The robots generate a language that represents macro-patterns of their spatial distribution in the environment. We coded the grammar system into the computer simulation. We computed the so-called stochastic value of open chains (robots moving a series, one following another) and closed chains (the robots moving in a cycle). We were interested in the relationship of micro-patterns and macro-behavior. It appeared that the higher the stochastic value we ascribed to the leader-follower behavior of each robot, the more likely was the chain behavior in comparison with other behaviors (especially random ones). In this experiment it could be shown that the sum of the robots’ behaviors (in accordance with our deŽnition) corresponds with the language generated by the society of the robots. Thus it does not reveal any basic emergent properties. Nevertheless, macro-behavioral spatial patterns appear with high stochastic values that are directly derived from the succession in time of robots’ behaviors. This can be called stochastic emergence. Actually, some spatial patterns (like the robots moving in a cycle) can be generated over a substantially greater time horizon by randomly moving robots. This is another example where the ascription of surprise to the observation of MAS properties is not a good way to understand emergence. What this example teaches us is that in the behavior of a robot society parallelism is not the critical issue, but the succession in time of robots’ behaviors is. 5.4 Stigmergy Finally we give a simple example to illustrate a non-emergent behavior of a MAS. It will be an example of stigmergic communication inspired by the reactive pheromone communication of ants and other insects [32].14 In computer engineering, stigmergy can be designed by dividing functions and data of a computer program into static data structures representing the environment and methods or functions representing the agents. The agents only change the state of the environment (data) as a reaction to their values. They do not use any memory to store the results of their computation. Memory in this case is represented by the environment with variables. We try to show that if stigmergy can be simulated by traditional procedural approaches to programming, where procedures sequentially communicate results of computing process until the result is obtained or no function calls occur, then there is no emergence in the system. 14 For a thorough treatment of ant algorithms see [23].

ArtiŽcial Life Volume 9, Number 1

59

A. Kub´Ok

Toward a Formalization of Emergence

Let Prog D fVA ; VE ; F; i1 g be a program with stigmergic computing, where VA D fg is an empty set of agent symbols, VE D fi1 ; i2 ; : : : ; in ; o1 ; o2 ; : : : ; on g is an evironmental set of input and output symbols, F D fF1 ; F2 ; : : : ; Fn g is a set of functions operating over data, and i1 is an initial input to a program. Each function has one of the following forms: F1 D fVA ; VE ; P1 ; i1 g or Fk D fVA ; VE ; Pk ; ok¡1 g;

2 · k · n;

where the set of agents and environmental symbols VA ; VE is deŽned as above; P1 D fi1 ! i1 o1 g, Pk D fok¡1 ! ik ; ik ! ik ok g, 2 · k · n, are sets of rewriting rules of functions (instructions for reacting to a certain input and changing it to an output), and i1 and ok¡1 are initial input symbols (the output of another function) of a function. Prog is modeled by a modiŽed grammar system as deŽned in Sections 3 and 4. A onedimensional tape of the grammar system represents the environment containing data (inputs and outputs). The agents (functions) rewrite data according to their rewriting rules. Every output becomes an input to another function in a sequential manner. We do not use agent symbols, because functions themselves do not have to be represented in the environment. The contents of the tape change in the following manner by applying the rewriting rules of the agents: i1 H) i1 o1 H) i1 i2 H) i1 i2 o2 H) i1 i2 i3 H) i1 i2 i3 o3 H) ¢ ¢ ¢ H) i1 ¢ ¢ ¢ in on : The behavior of each function can be represented by the language it generates. The function F1 generates the language L.F1 / D fi1 ; i1 o1 g. The language of other functions will be a construct L.Fk / D fi1 ¢ ¢ ¢ ik¡1 ok¡1 ; i1 ¢ ¢ ¢ ik¡1 ik ; i1 ¢ ¢ ¢ ik¡1 ik ok g;

2 · k · n:

The language of the whole program will be a construct L.Prog/ D fi1 ; i1 o1 ; : : : ; i1 ¢ ¢ ¢ in¡1 on¡1 ; i1 ¢ ¢ ¢ in ; i1 ¢ ¢ ¢ in on g D

n [

L.Fk /:

kD1

The language of superimposed function languages will be a construct Á Lsum D

n [

kD1

! L.Fk / [ Lres ;

which is generated by the whole program plus some other words that arise from superimposition of shorter strings over the longer ones (denoted by Lres ).15 15 This example shows that the union of languages is better suited than the superimposition of languages to the design and analysis of non-spatial behavior. Here the union of function languages coincides with the language of the whole program.

60

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

The whole program thus cannot generate more than the sum of its functions. Stigmergy in MASs does not reveal basic emergence if it can be simulated by sequential processes in a traditional program design. The following is an example of such a system. Suppose we have the task of completing a computer from given parts and agents with very limited capability that take and add a speciŽed part only if they observe that the computer is in a given phase of the completion. In this case the environmental tape would be represented by the alphabet of computer parts in the given stage of the completion. The agents react only to the speciŽed string on the tape and rewrite it in the sense that they add another part to the computer set. The task is completed after the last agent has added its part to the computer. The agents communicate only through the environment by changing speciŽed parameters. The behavior of the MAS here is nevertheless not in any sense emergent, even if it may appear impressive to the external observer (who might even attribute cooperative behavior to the agents). The language analysis discloses that the agents would generate the same words if they acted over the tape simultaneously. The reason for this is that the MAS in this experiment could be constructed as one centralized agent with parts that react to the process of computer completion. This is a traditional model of sequential or procedural computing where components of a system (procedures) sequentially pass the results of their computations to each other, possibly generating the desired result (behavior). So communication through the environment can be the source of basic emergent phenomena but is insufŽcient without other conditions being fulŽlled (e.g., the inherent parallelism of the interactions).

6

Concluding Remarks

In this article we have tried to design a formal framework for emergence. We speciŽcally tried to capture the property of a MAS that exhibits behavior not exhibited by summation of the individual agent behaviors. We formally deŽned the sum of the agents’ behaviors as the set of the superimposed words the agents generate individually. We proposed the deŽnition of basic emergence as an alternative to existing concepts of emergence. We decided to choose grammars and grammar systems as a model of agents and MASs as well as the environment. Thus, we can use parallel or sequential modes of rewriting, and every agent can be modeled as a set of rewriting rules. The deŽnition of basic emergence corresponds to the simplest case of a MAS in which only agents play an active role in the environment and no evolutionary processes occur. It is nevertheless possible to model evolving MASs with the aim of observing other kinds of emergence. It is also possible to consider internal states of agents as an internal mechanism of decision making with higher levels of rationality. Other extensions (inter-agent communication, active and more-dimensional environments, etc.) are possible. Our idea of basic emergence accords in essence with Holland’s notion of emergence [31]. It almost coincides with Bedau’s deŽnition of weak emergence [5, 6]. It corresponds in essence with the syntactic or combinatoric concepts of emergence of Cariani and has the potential to capture Cariani’s concept of creative emergence [14, 13, 12]. We think it is more descriptive than the deŽnition presented by Baas [4] in that it does not count any property of a MAS that cannot be observed at the level of agents’ description as necessarily emergent. The fact that examples of basic emergence were mostly (though not necessarily always) due to inter-agent interactions reveals that one of the following attributes should be present in MASs that are designed to produce emergent behavior: ArtiŽcial Life Volume 9, Number 1

61

A. Kub´Ok

Toward a Formalization of Emergence

² direct cooperation among agents,16 ² parallel activities that cannot be replaced by sequential actions, ² breaking some limiting or threshold parameters in the system (as in avalanche

effects, mass psychosis, etc.).

The new idea in our approach is to use a uniŽed modeling tool that can cope with different types of emergence. We propose a uniŽed formal framework that is based on grammars and the languages they generate. Still, much has to be done in the study of complex systems in relation to emergence. We propose that research on hierarchies and architectures in multiagent systems can shed more light on the formation of emergent structures in these systems (see the discussion in ArtiŽcial Life [29, 45, 46]). Evolution plays a crucial role in the genesis of higher structures or components with completely new semantics. Until now the concept of emergence was in its essence a philosophical concept in that researchers tried to explain its meaning. There is nevertheless the potential to use this concept to create new artiŽcial systems from the bottom up if we are able to describe the system’s behavior on higher semantic levels. How should we design the properties of the components of the system and their interactions? What role should the environment play if we expect some desired behavior of the whole system? This approach could be called emergence-based reverse engineering. It could help us to design interesting new software or hardware as well as explain how natural systems work. Acknowledgments The author is indebted to I. Trenc.ansk´y for his fruitful comments during the discussions that shaped this article in the beginning of the summer of 2000. He is also indebted to the reviewers who inspired many ideas and thus substantially inuenced the Žnal version of this paper. Special thanks to M. Bedau for his comments and revisions. References 1. Ablowitz, R. (1939). The theory of emergence. Philosophy of Science, 6, 1–16. 2. Austin, J. L. (1962). How to do things with words. Oxford, UK: Clarendon. 3. Baas, N. A. (1997). Self-Organization and Higher Order Structures. In F. Schweitzer (Ed.), Self-organization of complex structures: From individual to collective dynamics (pp. 71–82). New York: Gordon and Breach. 4. Baas, N. A. (1994). Emergence, hierarchies, and hyperstructures. In C. G. Langton (Ed.), ArtiŽcial life III, Santa Fe Studies in the Sciences of Complexity, Proc. Vol. XVII (pp. 515–537). Redwood City, CA: Addison-Wesley. 5. Bedau, M. A. (forthcoming). Downward causation and the autonomy of weak emergence. Principia, special issue on emergence. 6. Bedau, M. A. (1997). Weak emergence. In J. Tomberlin (Ed.), Philosophical perspectives: Mind, causation, and world, Vol. 11. (pp. 375–399). Malden, MA: Blackwell. 16 Direct cooperation in our understanding requires concurrent activities of agents for the purpose of the fulŽ lment of a common goal (e.g., if agents together carry heavy objects—that is why, e.g., water molecules do not cooperate, but only react to environmental change; their interactions cannot be interpreted as a coordination). Direct cooperation in most cases requires direct communication, possibly in advance. Direct communication is communication that is addressed among two or more agents (the sender sends the message to the speciŽ ed address and awaits the change of the internal state of the receiver—it is an act in the sense of communication act theory [2, 25, 37, 53]). The most important aspect of direct communication is that the environment does not play the role of memory (as in the stigmergic communication), but only the role of transfer medium. Typical examples of direct communication are negotiations [22, 50].

62

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

7. Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning ways (for your mathematical plays), Vol. 2. New York: Academic Press. 8. Bonabeau, E., Dessalles, J. L., & Grumbach, A. (1995). Characterizing emergent phenomena (1): A critical review. Revue Internationale de Syst´emique, 9, 327–346. 9. Bonabeau, E., Dessalles, J. L., & Grumbach, A. (1995). Characterizing emergent phenomena (2): A critical review. Revue Internationale de Syst´emique, 9, 347–371. 10. Brooks, R. A. (1991). Intelligence without reason. In Proceedings of the 12 th International Joint Conference on ArtiŽcial Intelligence (IJCAI ’91) (pp. 569–595). San Francisco: Morgan Kaufmann. 11. Campbell, D. T. (1974). Downward causation in hierarchically organized biological systems. In F. J. Afala & T. Dobzhansky (Eds.), Studies in the philosophy of biology. New York: Macmillan. 12. Cariani, P. (1998). Towards an evolutionary semiotics: The emergence of new sign-functions in organisms and devices. In G. Van de Vijver, S. Salthe, & M. Delpos (Eds.), Evolutionary Systems (pp. 359–377). Dordrecht, The Netherlands: Kluwer Academic. 13. Cariani, P. (1997). Emergence of new signal-primitives in neural networks. Intellectica, 2, 95–143. 14. Cariani, P. (1989). On the design of devices with emergent semantic functions. Ph.D. dissertation, State University of New York at Binghamton. 15. Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2, 113–124. ´ E. (1995). Eco-grammar systems: Recent results and perspectives. In Gh. Pa)un 16. Csuhaj-Varju, (Ed.), ArtiŽcial life: Grammatical models (pp. 79–103). Bucharest, Romania: Black Sea University Press. ´ E., Dassow, J., Kelemen, J., & Pa)un, Gh. (1994). Grammar systems—A 17. Csuhaj-Varju, grammatical approach to distribution and cooperation. London: Gordon and Breach. 18. Csuhaj-Varju, ´ E., & Kelemen, J. (1989). Cooperating grammar systems: A syntactical framework for blackboard model of problem solving. In Proceedings of the Conference on ArtiŽcial Intelligence and Information Control System of Robots: AIICSR’89 (pp. 121–127). New York: Elsevier. 19. Csuhaj-Varju, ´ E., Kelemen, J., Kelemenov´a, A., & Pa)un, Gh. (1994). Eco(grammar)-systems. A preview. In R. Trappl (Ed.), Cybernetics and systems ’94 (pp. 941–948). Singapore: World ScientiŽc. 20. Csuhaj-Varju, ´ E., Kelemen, J., Kelemenov´a, A., & Pa)un, Gh. (1996). Eco-grammar systems: A grammatical framework for life-like interactions. ArtiŽcial Life, 3, 1–28. 21. Dassow, J., Freund, R., & Pa)un, Gh. (1995). Cooperating array grammar systems. International Journal of Pattern Recognition and ArtiŽcial Intelligence, 9, 1029–1053. 22. Davis, R., & Smith, R. G. (1988). Negotiation as a metaphor for distributed problem solving. In A. H. Bond & L. Gasser (Eds.), Readings in Distributed ArtiŽcial Intelligence. San Mateo, CA: Morgan Kaufmann. 23. Dorigo, M., Bonabeau, E., & Theraulaz, G. (1999). Swarm intelligence: From natural to artiŽcial systems. New York: Oxford University Press. 24. Fernau, H., Freund, R., & Holzer, M. (1998). Regulated array grammars of Žnite index, Part I: Theoretical investigations. In Gh. Pa)un & A. Salomaa (Eds.), Grammatical models of multi-agent systems. Reading, UK: Gordon and Breach. 25. Finin, T., Fritzson, R., McKay, D., & McEntire, R. (1994). KQML as an agent communication language. In Proceedings of the 3r d International Conference on Information and Knowledge Management (CIKM ‘94). ACM Press. 26. Freund, R. (2000). Array grammar systems. Journal of Automata, Languages and Combinatorics, 5, 13–29.

ArtiŽcial Life Volume 9, Number 1

63

A. Kub´Ok

Toward a Formalization of Emergence

27. Gardner, M. (1983). Wheels, life, and other mathematical amusements. New York: Freeman. 28. Goertzel, B. (1994). Chaotic logic: Language, thought and reality from the perspective of complex systems science. New York: Plenum Press. 29. Gross, D., & McMullin, B. (2002). Is it the right ansatz? ArtiŽcial Life, 7, 355–366. 30. Hillis, D. (1988). Intelligence as an emergent behavior; or the songs of Eden. Daedalus, Winter, 175–189. 31. Holland, J. H. (1998). Emergence: From chaos to order. Reading, MA: Addison-Wesley. 32. H¨olldobler, B., & Wilson, E. O. (1994). Journey to the ants. Belknap Press=Harvard University Press. 33. Kelemen, J. (2000). A note on colonies as post-modular systems with emergent behavior. In R. Freund & A. Kelemenov´a (Eds.), Grammars Systems 2000. Proceedings of the 4th International Workshop on Grammar Systems (pp. 203–213). Opava, Czech Republic: Silesian University. 34. Klee, R. L. (1984). Micro-determinism and concepts of emergence. Philosophy of Sciences, 51, 44–63. 35. Kub´Ok, A. (2002). Probabilistic grammar systems as a tool to model stochastic emergence. In D. Polani, J. Kim, & T. Martinetz (Eds.), Abstracting and synthesizing the principles of living systems. 5th German Workshop on ArtiŽcial Life (pp. 169–180). Berlin: Akademische Verl.-Gesellschaft. 36. Kub´Ok, A. (2001). On emergence in evolutionary multiagent systems. In J. Kelemen & P. SosOk (Eds.), Advances in ArtiŽcial Life. Proceedings of the 6th European Conference on ArtiŽcial Life (pp. 326–337). Berlin: Springer-Verlag. 37. Labrou, Y., & Finin, T. (1997). Semantics and conversations for an agent communication language. In Proceedings of the 15th International Joint Conference on ArtiŽcial Intelligence (IJCAI ’97), Nagoya, Japan. 38. Langton, C. G. (1989). ArtiŽcial life. In C. G. Langton (Ed.), ArtiŽcial Life. Santa Fe Institute Studies in the Sciences of Complexity, Proc. Vol. VI (pp. 1–48). Redwood City, CA: Addison-Wesley. 39. Lucas, C. (1999). Complexity philosophy as a computing paradigm. Preprint of a talk presented at the “Self-Organising Systems—Future Prospects for Computing” Workshop held at UMIST, 28–29 October, in conjunction with the EPSRC “Emerging Computing” Networks Initiative. www.calresco.org/lucas/compute.htm. 40. Matari´c, M. (1994). Interaction and intelligent behavior. Ph.D. thesis, Cambridge, MA: MIT Press. 41. Minsky, M. (1986). The Society of Mind. New York: Simon and Schuster. 42. Morgan, C. L. (1923). Emergent Evolution. London: Northgate and Williams. 43. Pepper, S. (1926). Emergence. Journal of Philosophy, 23, 241–245. 44. Poundstone, W. (1985). The Recursive Universe. Chicago: Contemporary Books. 45. Rasmussen, S., Baas, N. A., Mayer, B., Nilsson, M., & Olesen, M. W. (2002). Ansatz for dynamical hierarchies. ArtiŽcial Life, 7, 329–354. 46. Rasmussen, S., Baas, N. A., Mayer, B., Nilsson, M., & Olesen, M. W. (2002). Defence of the Ansatz for dynamical hierarchies. ArtiŽcial Life, 7, 367–374. 47. Ronald, E. A., Sipper, M., & Capcarre` rre, M. S. (1999). Design, observation, surprise! A test of emergence. ArtiŽcial Life, 5, 225–239. 48. Ronald, E. A., & Sipper, M. (2000). Engineering, emergent engineering, and artiŽcial life: Unsurprise, unsurprising surprise, and surprising surprise. In M. A. Bedau, J. S. Caskill, N. H. Packard, & S. Rasmussen (Eds.), ArtiŽcial Life VII (pp. 523–528). Cambridge, MA: MIT Press.

64

ArtiŽcial Life Volume 9, Number 1

A. Kub´Ok

Toward a Formalization of Emergence

49. Rosen, R. (1985). Anticipatory Systems. New York: Pergamon Press. 50. Rosenschein, J. S., & Zlotkin, G. (1994). Rules of encounter: Designing conventions for automated negotiation among computers. Cambridge, MA: MIT Press. 51. Rozenberg, G., & Salomaa, A. (Eds.). (1997). The handbook of formal languages, 3 volumes. Berlin: Springer-Verlag. 52. Salomaa, A. (1973). Formal languages. San Diego, CA: Academic Press. 53. Searle, J. R. (1969). Speech acts. Cambridge, UK: Cambridge University Press. 54. Simovici, D. A., & Tenney, R. L. (1999). Theory of formal languages with applications. Singapore: World ScientiŽc. 55. van Leeuwen, J., & Wiedermann, J. (2001). The Turing machine paradigm in contemporary computing. In B. Engquist & W. Schmid (Eds.), Mathematics unlimited—2001 and beyond (pp. 1139–1155). Berlin: Springer-Verlag. 56. Wooldridge, M. (2002). An introduction to multiagent systems. London: Wiley.

ArtiŽcial Life Volume 9, Number 1

65