Transcript 16. Artificial Life and Emergent Behavior

Course Outline



Part I – Introduction to Artificial Intelligence
Part II – Classical Artificial Intelligence
Part III – Machine Learning





Introduction to Machine Learning
Neural Networks
Probabilistic Reasoning and Bayesian Belief Networks
Artificial Life: Learning through Emergent Behavior
Part IV – Advanced Topics
TRU-COMP3710
Artificial Life and Emergent
Behavior
1
Artificial Life and
Emergent Behavior
Fall 2013
Comp3710 Artificial Intelligence
Computing Science
Thompson Rivers University
Reference



Artificial Intelligence Illuminated, Ben Coppin, Jones and Bartlett
Illuminated Series
Artificial Life – http://www.alesdar.org/oldSite/IS/
…
Emergent Behavior
3
Chapter Contents
1.
2.
3.
4.
5.
6.
7.
8.
9.
What is life?
Emergent Behavior
Finite State Automata
Conway’s Life
One-Dimensional Cellular Automata
Self-Reproducing Systems
Evolution and Evolution Strategies
Genetic Programming
Artificial Immune Systems
Emergent Behavior
4
1. What is life?

What are the defining features of life?






Not all living things obey these rules


E.g., mules
Some things that are not alive do


self-reproduction
ability to evolve by Darwinian natural selection
response to stimuli
ability to die
growth or expansion
E.g., viruses, computer viruses
Defining life is very difficult!
Emergent Behavior
5
2. Emergent Behavior



Emergent behavior is a prominent feature of life.
The idea that complex behavior emerges from simple rules.
For Goldstein, emergence can be defined as: "the arising of novel and
coherent structures, patterns and properties during the process of selforganization in complex systems" (Corning 2002).
Photo taken and supplied by Brian
Voon Yee Yap.
Cathedral Termite Mounds.
Emergent Behavior
6
Emergent Behavior

Examples

Boids –




Rules





Craig Reynolds in 1987
Simulations of birds given very simple rules about how to fly.
Automatically flew in such a way as to avoid large obstacles, without being taught
explicitly how to do so.
Tendency to move toward the center of gravity of the whole flock
No collision each other
No other rule except the above two
Now to be used in animation software
eFloys (evolving Floyes)


Social, territorial, evolving artificial life creatures
Rules



Territorialism (they defend their territory against intruders)
Potential individualism (each can possess a different personality)
Ability to evolve (using a Genetic Algorithm code).
Emergent Behavior
7
3. Finite State Automata

Very useful tool for AI, and
computer science in general

FSA: a machine with a
finite number of states.
A state represents a set of internal
data at a certain moment.
The FSA is given inputs, which result in transitions between states.
Some states are accepting, meaning the FSA is saying “Yes”.
Other states are rejecting.
In this example there are two possible input characters – a and b, and
two states, 1 and 2. Meaning of the FSA is ???
It will finish in state 1 (the accepting state) if the input has an even
number of a’s.





Emergent Behavior
8
Finite State Automata



Very useful tool for AI, and computer science in general
It is possible to mimic certain behaviors of living creatures using FSAs.
E.g., Boids




Can you make a FSA for variable names in Java?



Inputs – location, speed, other birds, obstacles, …
State – direction, speed
A set of rules that determine which state to move to from each state,
according to the input data
A variable consists of characters, numbers and ‘_’,
Must not start with a number
Can you make a FSA for pendulous words, e.g., abcddcba?
Emergent Behavior
9
4. Cellular automata
Emergent Behavior
10
Conway’s Life



A two dimensional cellular automaton.
A two dimensional grid of cells, each of which can be alive or dead.
A set of rules determines how the cells will change from one generation
to the next:
1.
2.
3.
4.
A dead cell will come to life if it has three living neighbors.
A living cell with two or three living neighbors, will stay
alive.
A living cell with fewer than two living neighbors will die of
loneliness.
A living cell with more than three living neighbors will die
of overcrowding.
Emergent Behavior
11
Conway’s Life




Surprisingly complex behavior can sometimes emerge from these
simple rules.
This diagram shows a successive sequence of generations of Conway’s
Life.
This pattern is known as a glider.
There is also a pattern known as a glider gun which constantly fires out
gliders.
Emergent Behavior
12
5. One-Dimensional Cellular Automata




A single line of cells. Each cell thus has two immediate neighbors.
It is usual to have rules that take into account the cells on either side of
the immediate neighbors as well.
Usually, the cell itself is also taken into account, meaning that each
cell’s future is determined by 5 cells.
1-D Cellular Automata often use totalistic rules, meaning that the
number of living cells out of the 5 is all that determines the cell’s state
in the next generation.



At least two living neighbors, then it will live
Less than two neighbors, then it will stay dead
If a dead cell has at least three living neighbors, then it will come to life
Emergent Behavior
13
One-Dimensional Cellular Automata

Hence, there are 32 possible rule sets. One such set of rules might be:
1
0


2
0
3
1
4
1
5
1
This says a cell can only survive if it has two, three or four neighbors.
This rule can be seen applied in five generations in the following
diagram:
1st generation
2nd
3rd
4th
5th

Applications: image processing
Emergent Behavior
14
More demonstration


Game of Life
Animal patterns
Emergent Behavior
15
6. Self-Reproducing Systems


Von Neumann proposed a self-reproducing
system based on cellular automata in the 1950s.
Langton invented loops:




8 different states
Contains all the information that is needed to reproduce itself.
The artificial system that was capable of self-reproducing.
The “organism” that Langton created lived in an environment that was
nothing more than a board of cells; each cell contains its own state.
Depending upon the state of a cell and the state of the cells around it, a
cell’s state might change in the next generation. The creature that Langton
created in this environment looked like a loop with a tail. As time
advanced the tail extended and made a new loop. This new loop then
severed itself from the original loop organism and then there were two
organisms. Both the new creature and the original creature were able to
reproduce, and so they did, eventually filling up all the available space
[Levy, 1992].
Emergent Behavior
16
Self-Reproducing Systems



HAL 9000 in the movie “2001: A Space Odyssey” was inspired by
Langton’s loops
Ultimately we may have robots that can obtain the raw materials
necessary to produce new versions of themselves.
This would be useful for exploring other planets.
Emergent Behavior
17
7. Evolution




The changes in cellular automata involve single-step selection, while
evolutionary systems involve cumulative selection (Dawkins, 1991).
Survival of the fittest means that creatures that are fit are more likely to
reproduce than those that are less fit.
This idea is modeled exactly in systems such as genetic algorithms.
Dawkins’ biomorphs


Nine genes representing a feature of the biomorphs, such as the branching
angle between branches or the length of branches.
Evolved Virtual Creatures


Karl Sims in 1994
Darwinian evolutions of virtual block creatures
Emergent Behavior
18
Evolution Strategies





Similar to hill-climbing.
A set of numeric parameters is varied from generation to generation by
making normally distributed changes to the values.
If the offspring is a better solution than the parent, then the process
repeats from the offspring.
Otherwise, the offspring is rejected, and a new attempt is made.
This is asexual reproduction – a single parent produces a single
offspring.
Emergent Behavior
19
8. Genetic Programming





http://www.genetic-programming.org/
http://www.genetic-programming.com/gpanimatedtutorial.html
Genetic programming (GP) is an automated method for creating a
working computer program from a high-level problem statement of a
problem.
Genetic programming starts from a high-level statement of “what
needs to be done” and automatically creates a computer program to
solve the problem.
Not genetic algorithms
U. S. PATENT 5,719,794
Emergent Behavior
20
9. Artificial Immune Systems



Systems modeled on the immune systems in humans and other
biological creatures.
Used in anti-virus systems, for example.
Also applied in computer security, for solving combinatorial problems,
and for machine learning problems.
Emergent Behavior
21