EmergentSystemsMeeting1

A summary of this meeting can also be found at http://serendip.brynmawr.edu/local/scisoc/emergence/blankkumar.html .

1. What is Emergence?

Notes for Meeting Friday Sep 26, 2002, 8am.

Contents:

What is Emergence?

Core Ideas of Emergence

Examples of Emergence

Cellular Automata

2D CA with Simple Rules
Conway's Game of Life

Self-organized Criticality
Emergent Behaviors in Robotics
Emergent Computation

People, Places, and other Resources

1.1. Core Ideas of Emergence

"Whole is greater than the sum of parts"
The local interaction of small, 'simple' pieces (agents) gives rise to a global, complex "pattern"
Usually driven by self-organization
Often, phase transitions appear as the number of interacting elements increases (ie, an observer sees a dramatic change in behavior that occurs quickly, like the transition from ice to water)
Sometimes this area is called the "edge of chaos"
The emergent, global "pattern" may create a novel "level" (an actual new thing, or maybe a new level of description?)
This global behavior is often said to be unexpected, a surprise, unpredicatable
Often, emergent systems can be described by so-called "Power Laws" (little things happen often, big things happen rarely) (See also PowerLaws)
Often seen as acting against the Second Law of Thermodynamics (Paul says: this is just nonequilibrium thermodynamics.)

Summary: An emergent system (sometimes called a complex adaptive system) is a system that can be described at different levels, in which global properties at one level emerge from the interaction of a number of simple elements at lower levels. Global properties are emergent in the sense that, even if they result from nothing else but local interactions among elements, they cannot be predicted [1] or inferred from a knowledge of the elements or or the rules by which the elements locally interact.

.. [1] "cannot be predicted" is an idea that cannot be stated precisely

Course description: A multi-disciplinary exploration of the interactions underlying emergent systems. Such systems include those that appear to be greater than the sum of their parts. Often characterized by simple, local interactions, these systems self-organize to produce global phenomena not readily apparent in the parts alone. Emergent properties can be found in real and simulated systems, for example, ant colonies, cities, brains, economies, earthquakes, weather, both natural and artificial evolution, computers, and even life itself.

When the small, interacting pieces cause global harm, we call these emergencies

2. Examples of Emergence

Emergence is everywhere, but we list some of the common textbook examples below.

2.1. Cellular Automata

A Cellular Automata (CA) is:

a set of cells that can be in various states
a set of rules for changing a cell's state

The cells are usually laid out in a grid, either in 2 dimensions (like a checker board), or in 1 dimension (like beads on a necklace). The grid is usually seen as "wrapping around" (when you fall off the left, you appear on the right; when you fall off the bottom, you appear on the top).

The rules are applied to all cells at once, in parallel. The rules are based on a local neighborhood that surrounds each cell.

Why CAs?

They hopefully abstract out all but the essential bits
They are computers! They can compute anything that can be computed (Turing Machine Equivilent)
...but they can compute in ways very unlike what humans normally do

2.1.1. 2D CA with Simple Rules

http://el.www.media.mit.edu/groups/el/projects/emergence/

If a square is on, it turns off. If a square is off, it turns on if exactly two of its eight neighboring squares are on.

// Simple Cellular Automata Rules:

for all cells on board:
   if cell == on:
      cell = off
   else:
      if neighborhood() == 2:
         cell = on

2.1.2. Conway's Game of Life

http://serendip.brynmawr.edu/complexity/life.html

At each step, life persists in any location where it is also present in two or three of the eight neighboring locations, and otherwise disappears (from loneliness or overcrowding). Life is born in any empty location for which there is life in three of the eight neighboring locations.

// Game of Life Cellular Automata Rules:

for all cells on board:
   if cell == on:
      if not (neighborhood() == 2 or neighborhood() == 3):
         cell = off
   else:
      if neighborhood() == 3:
         cell = on

2.2. Self-organized Criticality

Begin dropping sand in a spot. Soon, the pile will grow to a pyramid. After a while, the top of the sand pile won't be able to support as much sand that is up there. Either a small sand slide, or a big sand avalanche, will occur. Small sand slides happen much more frequently than large sand avalanches. If you plot (on a log-log plot) slide size on the X axis, and frequency on the Y axis, you'll see a straight line from upper left down to lower right (See PowerLaws). This same kind of relationship holds in word frequencies, earthquake magnatudes, etc.

http://cmth.phy.bnl.gov/~maslov/Sandpile.htm

2.3. Emergent Behaviors in Robotics

It is commonplace to observe emergent behaviors in robots as they interact with their environment. This can be demonstrated in the simplest of ways. For example, see the video below (live demo for Septempter 27, video coming shortly!) of a robot that follows a wall.

However, if you look at the algorithm (rules) driving the robot, you will obeserve a very simple set of rules:

If I am not touching a wall on my right side, I will turn right.
If I am touching a wall on my right side, I will turn left.

The program below produces the resulting emergent, wall following behavior.

#define RIGHTMOTOR 3
#define LEFTMOTOR 1
#define BENDSENSOR 2

int Thresh = 100;

void main() {
    int STOP = 0;
    int L = 0, R = 0;
    int sensor = 0;
    
    while(!STOP) {                    // as long as stop button is not pressed
        
        sensor = analog(BENDSENSOR);  // Am I touching something?
        
        if (sensor < Thresh)          // decide to turn left or right
          turnright();                
        else                         
          turnleft();  
        
        STOP = stop_button();        // stop now?              
    }
    alloff();
    printf("Bye\n");
} // main

// turn left
void turnleft() {
    motor(LEFTMOTOR, 0);
    motor(RIGHTMOTOR, 100);
} // turnleft

// turn right
void turnright() {
    motor(RIGHTMOTOR, 0);
    motor(LEFTMOTOR, 100);
} // turnright

In general, it is always the case that a robot's behavior is an emergent property of its motor interaction with the environment. A robot and its environment can be described as a dynamical system because the sensory state of the robot at any given time is a function of both the environment and its previous actions. This has a couple of consequences: mobile robots are harder to design; and even the simplest of robots are capable of producing complex behavior.

2.4. Emergent Computation

Emergence can also be as computation:

Soap bubbles compute the most efficient structure for containing the most amount of air
Bees compute the most efficient packing

The following is an image created by watching a 2D CA over time. The first row is an initial random configuration, and time runs downwards as the rules are applied over and over. These rules were designed by humans to compute density.

The following is a zoom in on a set of rules applied to a random initial configuration (first row). These rules were evolved to compute density.

These are some simple experiments in evolving CAs to compute. But the promise for much faster computing methods (superlinear parallel computing) may lie in emergent techniques.