Emergent Behavior

CIS548

Basic theory:

Wikipedia: http://en.wikipedia.org/wiki/Emergence

[Note: blue font not in original article; added for highlighting]

“Emergence

From Wikipedia, the free encyclopedia

Emergence is the process of complex pattern formation from more basic constituent parts or behaviors.

This can be a dynamic process (occurring over time), such as the evolution of the human body over thousands of successive generations; or emergence can happen over disparate size scales, such as the interactions between a great number of neurons producing a human brain capable of thought (even though the constituent neurons are not individually capable of thought). The original term was ‘categorial novum’ coined by Nicolai Hartmann.

For a phenomenon to be termed emergent it should generally be unpredictable from a lower level description [Comment: ??]. At the very lowest level, the phenomenon usually does not exist at all or exists only in trace amounts: it is irreducible. Thus, a straightforward phenomenon such as the probability of finding a raisin in a slice of cake changing with the portion-size does not generally require a theory of emergence to explain. It may, however, be profitable to consider the ‘emergence’ of the texture of the cake as a relatively complex result of the baking process and the mixture of ingredients.

Like intelligence in AI, or agents in DAI, emergence is a central concept in complex systems yet is hard to define and very controversial. There is no scientific consensus about what weak and strong forms of emergence are, or about how much emergence should be relied upon as an explanation in general. It seems impossible to unambiguously decide whether a phenomenon should be considered emergent.

Further, ‘emergent’ is not always a deeply explanatory label even when it is agreed on: the more complex the phenomenon is, the more intricate are the underlying processes, and the less effective the word emergence is alone. In fact, calling a phenomenon emergent is sometimes used in lieu of a more meaningful explanation. See also: self-organization.”

“Emergent properties

An emergent behaviour or emergent property can appear when a number of simple entities (agents) operate in an environment, forming more complex behaviours as a collective. If emergence happens over disparate size scales, then the reason is usually a causal relation across different scales. In other words there is often a form of top-down feedback in systems with emergent properties. These are two of the major reasons why emergent behaviour occurs: intricate causal relations across different scales and feedback. The property itself is often unpredictable and unprecedented, and may represent a new level of the system's evolution. The complex behaviour or properties are not a property of any single such entity, nor can they easily be predicted or deduced from behaviour in the lower-level entities: they are irreducible. No physical property of an individual molecule of air would lead one to think that a large collection of them will transmit sound. The shape and behaviour of a flock of birds or shoal of fish are also good examples.

One reason why emergent behaviour is hard to predict is that the number of interactions between components of a system increases combinatorially with the number of components, thus potentially allowing for many new and subtle types of behaviour to emerge. For example, the possible interactions between groups of molecules grows enormously with the number of molecules such that it is impossible for a computer to even count the number of arrangements for a system as small as 20 molecules.

On the other hand, merely having a large number of interactions is not enough by itself to guarantee emergent behaviour; many of the interactions may be negligible or irrelevant, or may cancel each other out. In some cases, a large number of interactions can in fact work against the emergence of interesting behaviour, by creating a lot of ‘noise’ to drown out any emerging ‘signal’; the emergent behaviour may need to be temporarily isolated from other interactions before it reaches enough critical mass to be self-supporting. Thus it is not just the sheer number of connections between components which encourages emergence; it is also how these connections are organised. A hierarchical organisation is one example that can generate emergent behaviour (a bureaucracy may behave in a way quite different to that of the individual humans in that bureaucracy); but perhaps more interestingly, emergent behaviour can also arise from more decentralized organisational structures, such as a marketplace. In some cases, the system has to reach a combined threshold of diversity, organisation, and connectivity before emergent behaviour appears.

Unintended consequences and side effects are closely related to emergent properties. Luc Steels writes about a system with ‘emergent functionality’ in his paper Towards a Theory of Emergent Functionality: ‘A component has a particular functionality but this is not recognizable as a subfunction of the global functionality. Instead a component implements a behavior whose side effect contributes to the global functionality [...] Each behavior has a side effect and the sum of the side effects gives the desired functionality’. In other words, the global or macroscopic functionality of a system with ‘emergent functionality’ is the sum of all ‘side effects’, of all emergent properties and functionalities.

Systems with emergent properties or emergent structures may appear to defy entropic principles and the second law of thermodynamics, because they form and increase order despite the lack of command and central control. This is possible because open systems can extract information and order out of the environment.”

“Emergent structures in nature

Emergent structures are patterns not created by a single event or rule. There is nothing that commands the system to form a pattern, but instead the interactions of each part to its immediate surroundings causes a complex process which leads to order. One might conclude that emergent structures are more than the sum of their parts because the emergent order will not arise if the various parts are simply coexisting; the interaction of these parts is central. Emergent structures can be found in many natural phenomena, from the physical to the biological domain. For example, the shape of weather phenomena such as hurricanes are emergent structures.

It is useful to distinguish three forms of emergence structures. First-order emergence structures occurs as a result of shape interactions (for example, hydrogen bonds in water molecules lead to surface tension). Second-order emergence structures involves shape interactions played out sequentially over time (for example, changing atmospheric conditions as a snowflake falls to the ground build upon and alter its form). Finally, third-order emergence structures is a consequence of shape, time, and heritable instructions. For example, an organism's genetic code sets boundary conditions on the interaction of biological systems in space and time.

Emergent structures can be observed in swarms and flocks. Flocking is a well-known behavior in many animal species from swarming locusts to fish and birds. Emergent structures are a favorite strategy found in many animal groups: colonies of ants, piles of termites, swarms of bees, flocks of birds, herds of mammals, shoals/schools of fish, and packs of wolves. A more detailed biological example is an ant colony. The queen does not give direct orders and does not tell the ants what to do. Instead, each ant reacts to stimuli in the form of chemical scent from larvae, other ants, intruders, food and build up of waste, and leaves behind a chemical trail, which, in turn, provides a stimulus to other ants. Here each ant is an autonomous unit that reacts depending only on its local environment and the genetically encoded rules for its variety of ant. Despite the lack of centralized decision making, ant colonies exhibit complex behavior and have even been able to demonstrate the ability to solve geometric problems. For example, the ant colonies routinely find the maximum distance from all colony entrances to dispose of dead bodies.”

“Emergence in physics

In physics, emergence is used to describe a property, law, or phenomenon which occurs at macroscopic scales (in space or time) but not at microscopic scales, despite the fact that a macroscopic system can be viewed as a very large ensemble of microscopic systems. Some examples include:

1. Color. Elementary particles such as protons or electrons have no color; it is only when they are arranged in atoms that they absorb or emit specific wavelengths of light and can thus be said to have a color.

2. Friction. Elementary particles are frictionless, or more precisely the forces between these particles are conservative. However, friction emerges when considering more complex structures of matter, whose surfaces can convert mechanical energy into heat energy when rubbed against each other. Similar considerations apply to other emergent concepts in continuum mechanics such as viscosity, elasticity, tensile strength, etc.”

Relevance to intelligent robotics:

Example One: Boids

From Wikipedia, the free encyclopedia: http://en.wikipedia.org/wiki/Boids

“Boids

Boids, developed by Craig Reynolds in 1986, is an artificial life program, simulating the flocking behaviour of birds.

As with most artificial life simulations, Boids is an example of emergent behaviour; that is, the complexity of Boids arises from the interaction of individual agents (the boids, in this case) adhering to a set of simple rules. The rules applied in the simplest Boids world are as follows:

* separation: steer to avoid crowding local flockmates

* alignment: steer towards the average heading of local flockmates

* cohesion: steer to move toward the average position of local flockmates

More complex rules can be added, such as obstacle avoidance and goal seeking.

The movement of Boids can either be characterized as chaotic (splitting groups and wild behaviour) or orderly. Unexpected behaviours, such as splitting flocks and reuniting after avoiding obstacles, can be considered emergent.

The boids framework is often used in computer graphics, providing realistic-looking representations of flocks of birds and other creatures, such as schools of fish or herds of animals.

Boids work in a manner similar to cellular automata, since each boid "acts" autonomously and references a neighbourhood, as do cellular automata.”

Boids Rules: http://www.vergenet.net/~conrad/boids/pseudocode.html

“Rule 1: Boids try to fly towards the centre of mass of neighbouring boids.

Rule 2: Boids try to keep a small distance away from other objects (including other boids).

Rule 3: Boids try to match velocity with near boids.”

Craig Reynolds page: http://www.red3d.com/cwr/boids/

Distributed Ant Robotics: http://www.red3d.com/cwr/boids/

Example Two: Swarm Intelligence:

From Wikipedia: http://en.wikipedia.org/wiki/Swarm_intelligence

“Swarm intelligence (SI) is an artificial intelligence technique based around the study of collective behavior in decentralized, self-organized systems. The expression "swarm intelligence" was introduced by Beni & Wang in 1989, in the context of cellular robotic systems.

SI systems are typically made up of a population of simple agents interacting locally with one another and with their environment. Although there is normally no centralized control structure dictating how individual agents should behave, local interactions between such agents often lead to the emergence of global behavior. Examples of systems like this can be found in nature, including ant colonies, bird flocking, animal herding, bacteria molding and fish schooling.

Application of swarm principles to large numbers of robots is called as swarm robotics.”

Calculating swarms: http://www.sciencenews.org/articles/20001111/bob10.asp

Swarm robotics: http://en.wikipedia.org/wiki/Swarm_robotics

“Swarm robotics

From Wikipedia, the free encyclopedia

Swarm robotics is a new approach to the coordination of multirobot systems which consist of large numbers of relatively simple physical robots. The goal of this approach is to study the design of robots (both their physical body and their controlling behaviors) such that a desired collective behavior emerges from the inter-robot interactions and the interactions of the robots with the environment, inspired but not limited by the emergent behavior observed in social insects, called swarm intelligence. It has been discovered that a set of relatively primitive individual behaviors enhanced with communication will produce a large set of complex swarm behaviors.

Unlike distributed robotic systems in general, swarm robotics emphasizes a large number of robots, and promotes scalability, for instance, by using only local communication. Local communication is usually achieved by wireless transmission systems, using radio frequency or infrared communication.

Potential application for swarm robotics include tasks that demand for extreme miniaturization (nanorobotics, microbotics), on the one hand, as for instance distributed sensing tasks in micromachinery or the human body. On the other hand, swarm robotics is suited to tasks that demand for extremely cheap designs, for instance a mining task, or an agricultural foraging task. Artists are using swarm robotic techniques to realize new forms of interactive art installation.

Both miniaturization and cost are hard constraints that emphasize simplicity of the individual team member, and thus motivate a swarm-intelligent approach to achieve meaningful behavior on swarm-level.

Further research is needed to find methodologies that allow for designing, and reliably predicting, swarm behavior, given only features of the individual swarm members. Here, video tracking is an essential tool for systematically studying swarm-behavior.”

Example Three: Mataric & Steels

http://www.santafe.edu/~dynlearn/dynlearn/RoMADS/mataric02/

http://cse.ucdavis.edu/~dynlearn/dynlearn/RoMADS/steels01/index.html

Mataric, M.
Designing Emergent Behaviors: From Local Interactions to Collective Intelligence
From Animals to Animats 2; Meyer, J-A., etal (eds)

Example Four: Robot teams

Multirobot Systems: http://www.wtec.org/robotics/us_workshop/June21/03b_Multi-robot.pdf

Example Five: ALLIANCE Architecture (Lynne E. Parker)

Key ALLIANCE paper: http://www.cs.utk.edu/~parker/publications/TRA.pdf

Impatience & acquiescence (ALLIANCE paper, p. 6):

“Two types of internal motivations are modeled in ALLIANCE | robot impatience and robot acquiescence. The impatience motivation enables a robot to handle situations

when other robots (outside itself) fail in performing a given task. The acquiescence motivation enables a robot to handle situations in which it, itself, fails to properly perform its task. Intuitively, a motivational behavior works as follows. A robot's motivation to activate any given behavior set is initialized to 0. Then over time, that robot's motivation to perform a given behavior set increases at a fast rate of impatience (defined explicitly below) as long as the task corresponding to that behavior set is not being accomplished by any robot team member. The robot, however should also be responsive to the actions of its teammates, adapting its task selection to the activities of other robot team members. Thus, if the ith robot ri is aware that the kth robot rk is working on a particular task, ri should be satisfied for some period of time that that task is going to be accomplished even without its own participation in the task, and thus go on to some other applicable action. Robot ri's motivation to activate its corresponding behavior set continues to increase, but at a slower rate of impatience. This characteristic prevents robots from replicating each

other's actions and thus wasting needless energy.”

Formal proof (pp. 5-16): http://www.cs.utk.edu/~parker/Courses/CS594-fall02/Lectures/Nov5.pdf

Parker papers: http://www.cs.utk.edu/~parker/papers.html

Parker interview: http://www.ars-journal.com/ars/Interview/Interview%20with%20Lynne%20E.htm

Example Five: Cellular Automata

Basic model:

Identical cells arranged in k-dimensional array, usually 1-d or 2-d, synchronized by a global clock. Each cell has a finite set of distinct states. Initially, each cell is in a particular state. On each clock tick, all cells make a state transition based on a rule attuned to the cell’s environment (see examples below). Interestingly, from very simple rules very complicated patterns can emerge.

Short history:

John von Neumann sought to build an artificial system capable of reproduction. Based on discussions with Ullam (some say heavily influenced by Ullam) he proposed the cellular automaton model. After some time he was successful in creating a 2-d cellular automaton which created a copy of itself.

Wikipedia: http://en.wikipedia.org/wiki/Cellular_automaton

“History

Stanislaw Ulam, while working at the Los Alamos National Laboratory in the 1940s, studied the growth of crystals, using a simple lattice network as his model. At the same time, John von Neumann, Ulam's colleague at Los Alamos, was working on the problem of self-replicating systems. Von Neumann's initial design was founded upon the notion of one robot building another robot. This design is known as the kinematic model. As he developed this design, von Neumann came to realize the great difficulty of building a self-replicating robot, and of the great cost in providing the robot with a "sea of parts" from which to build its replicant. Ulam suggested that von Neumann develop his design around a mathematical abstraction, such as the one Ulam used to study crystal growth. Thus was born the first system of cellular automata. Like Ulam's lattice network, von Neumann's cellular automata are two-dimensional, with his self-replicator implemented algorithmically. The result was a universal copier and constructor (UCC) working within a CA with a small neighborhood (only those cells that touch are neighbors; for von Neumann's cellular automata, only orthogonal cells), and with 29 states per cell. Neumann proved mathematically that a particular pattern would make endless copies of itself within the given cellular universe. This design is known as the tessellation model.

In the 1970s a two-state, two-dimensional cellular automaton named Game of Life became very widely known, particularly among the early computing community. Invented by John Conway, and popularized by Martin Gardner in a Scientific American article, its rules are as follows: If a black cell has 2 or 3 black neighbors, it stays black. If a white cell has 3 black neighbors, it becomes black. In all other cases, the cell stays or becomes white. Despite its simplicity, the system achieves an impressive diversity of behavior, fluctuating between apparent randomness and order. One of the most apparent features of the Game of Life is the frequent occurrence of gliders, arrangements of cells that essentially move themselves across the grid. It is possible to arrange the automaton so that the gliders interact to perform computations, and after much effort it has been shown that the Game of Life can emulate a universal Turing machine. Possibly because it was viewed as a largely recreational topic, little follow-up work was done outside of investigating the particularities of the Game of Life and a few related rules.

In 1969, however, German computer pioneer Konrad Zuse published his book Calculating Space, proposing that the physical laws of the universe are discrete by nature, and that the entire universe is just the output of a deterministic computation on a giant cellular automaton. This was the first book on what today is called digital physics.

In 1983 Stephen Wolfram published the first of a series of papers systematically investigating a very basic but essentially unknown class of cellular automata, which he terms elementary cellular automata (see below). The unexpected complexity of the behavior of these simple rules led Wolfram to suspect that complexity in nature may be due to similar mechanisms. Additionally, during this period Wolfram formulated the concepts of intrinsic randomness and computational irreducibility, and suggested that rule 110 may be universal—a fact proved as part of the development of his later book.

Wolfram left academia in the mid-late 1980s to create Mathematica, which he then used to extend his earlier results to a broad range of other simple, abstract systems. In 2002 he published his results in the 1280-page text A New Kind of Science, which extensively argued that the discoveries about cellular automata are not isolated facts but are robust and have significance for all disciplines of science. Despite much confusion in the press and academia, the book did not argue for a fundamental theory of physics based on cellular automata, and although it did describe a few specific physical models based on cellular automata, it also provided models based on qualitatively different abstract systems.”

Simple rules

Some of the simplest rules are those proposed by Fredkin and by Conway. They are described below, along with another one. These rules are implemented in this program: http://faculty.kutztown.edu/rieksts/112/projects/ca/CAexe.zip

Transition Functions

Fredkin ::

Number of states:: 2

Neighborhood:: North, South, East, West (but not self)

Sum ← sum of neighborhood

Rule :: If sum is odd → 1

If sum is even → 0

Conway::

Number of states :: 2

Neighborhood :: NW, N, NE, W, E, SW, S, SE

Cell itself is considered separately

Sum ← sum of neighborhood

Rule :: If cell itself is 1 :

If sum is 2 or 3 → 1

else → 0

If cell itself is 0 :

If sum is 3 → 1

else → 0

Burst::

This set of transition rules is called "Burst" because it was designed to create a set of colors which burst outward from a central point. What is interesting about this particular CA is that after a period of time the patterns produced become complex and it is quite difficult to predict what new patterns will emerge on the next iteration.

Number of states :: 6 {0,1,2,3,4,5}

Neighborhood :: NW, N, NE, W, Self, E, SW, S, SE

Sum ← sum of neighborhood

Rule :: Based on value of Sum

Sum = 0 → 0

1 ≤ Sum < 9 → 1

9 ≤ Sum < 18 → 2

18 ≤ Sum < 27 → 3

27 ≤ Sum < 36 → 4

36 ≤ Sum < 45 → 5

45 ≤ Sum → 0

Winlife:

The level of complexity that can be achieved with very simple rules can be seen in the Winlife program which runs only the Conway rules, but on a variety of initial configurations.

To download winlife: ftp://ftp.digital.com/pub/games/winlife.zip

A Universal Turing machine:

According to Wolfram, von Neumann had proven that a CA can become a universal Turing machine under certain conditions [http://mathworld.wolfram.com/UniversalCellularAutomaton.html]. Being unaware of this, about a dozen years ago I devised the following process for creating a UTM from a 1-d CA with unbounded cells.

1. Start with a 2 by K two-dimensional machine with one row representing the tape of the TM, the other the read/write head, letting a particular state represent the current position of the head. Incorporate the state transition function of the UTM into the transition function of that particular state and its left and right neighbors. The role of the cell representing the r/w head and the neighbor above it is to write the new symbol onto the tape. The role of the two neighbors is to represent the new position of the r/w head.

Fold the 2-d machine into a 1-d machine by multiplying the number of tape states by the number of r/w head states.

UTM in Conway:

What is even more interesting is that the simple Conway rules can also be used to construct a universal Turing machine. An extended description of the actual construction of UTM is given by P. Rendell: http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf

Search for CA rules: http://www.cs.utk.edu/~mclennan/RO/DSCAR.html

Breeding gliders: http://www.ventrella.com/Alife/Cells/cells.html