Matthew Egbert

m.egbert@auckland.ac.nz

• Computational models are often designed to be comparable to a target real-world phenomenon.
• Through an iterative process the model can be improved upon until it can predict what the real world system will do in various circumstances.
• A trade off is common between being simple, realistic and predictive. What is the minimal model that is maximally predictive?

https://en.wikipedia.org/wiki/Oregonator

http://www.scholarpedia.org/article/Oregonator

Many systems of interest are extremely complex, involving many components, involved in complex forms of feedback, etc.

And this leads to some serious challenges!

1. Prohibitive computational complexity
2. Free parameters -- How do we assign values to unknowns?
3. When models become too big, they become almost as hard to understand as their target!

Lots of work to be done here, and progress continues to be made.

• An alternative approach is to create artificial systems that capture some interesting life-like property, and to study that.
• Artificial systems can be designed to be more simple than their real-world target.
• This was the approach of cyberneticists such as Grey Walter in the mid-20th century.
• And artificial life can be thought of as an extension of this way of working.

• Precise equivalence between the artificial system and a target real-world system is not always the primary goal.
• Sometimes, the goal is to investigate a hypothesis or the implications of a theory ...

Hypothesis: "Effective motion is not purely the performance of a computer-like brain, but is enabled by the physical properties of the body and how it interacts with the world."

How much can a brainless body do?

• No computer / "brain"
• No sensors
• No motors!
• Just a very deliberately designed shape.

Compared to humans, very simple and easy to study.

I will now present a few examples of "classic" A-Life investigations that centre on computational models.

Part of my goal is to communicate that developing and studying artificial systems

• thought experiment: what are the implications of these rules or assumptions?
• sufficiency proof: X suffices to produce Y
• intuition pump: the model is used to facilitates an intuitive understanding of a system
• creativity pump: the model is used to produce new theories or hypotheses

• What produces these amazing patterns of behaviour?
• Are there leaders and followers?
• Are they responding to their environment?
• What purpose does swarming serve?
• Is the same mechanism(s) at play in schools of fish as in flocks of birds?

http://gencept.com/the-coordinated-beauty-of-thousands-of-birds-moving-in-sync

• Created by Craig Reynolds in 1986, and presented at one of the very first Artificial Life Workshops shortly thereafter.
• Regarded as a classic example of Artificial Life, demonstrating how complex life-like behaviour can come from simple rules.
• Instead of describing things at the high-level (the flock) the system is defined at the low-level (the birds and the simple rules that determine their behaviour). The simple rules result in complex collective behaviour.

Images taken from Craig Reynold's website. http://www.red3d.com/cwr/boids/

Boids change their behaviour in response to the position and velocity of other, nearby boids.

The neighborhood is parameterized by:

• a distance (measured from the center of the boid)
• an angle, measured from the boid's direction of flight (its heading)

Images taken from Craig Reynold's website. http://www.red3d.com/cwr/boids/

Steer to avoid being too close to flock-mates -- collision avoidance.

Accelerate away from each flock-mate at rate inversely proportional to proximity. i.e. the closer you are to a flock-mate, the more you accelerate away from that flock-mate.

Images taken from Craig Reynold's website. http://www.red3d.com/cwr/boids/

Steer toward the average heading of local flock-mates.

Calculate the mean velocity of all flock-mates. Update velocity to be a little bit more similar to that value.

Images taken from Craig Reynold's website. http://www.red3d.com/cwr/boids/

Move toward the average position of local flock-mates.

Calculate the mean position of flock-mates and accelerate toward that position.

DEMO:

http://www.emergentmind.com/

Images taken from Craig Reynold's website. http://www.red3d.com/cwr/boids/

Prediction
We cannot use the model to precisely predict the real-world system. (Although there may be some qualitative predictions that could be made.) But ...

Sufficiency Proof
The three simple rules are sufficient for this kind of system to display the complex kind of swarming that we witness in Nature. "Life-like" complex (but not random) behaviour. This is an example of ...

Emergence
Complex, yet organized global behavior can arise from the interaction of simple local rules.

How do you design a simple set of rules to produce a desired collective behaviour?

Biology
Insight into group and social dynamics (e.g. ants and termites).

Engineering
How can you get a swarm of robots to perform a particular collective behaviour?

Termites rush to a damaged area of the nest.
U.S. Department of Agriculture (taken by Scott Bauer)
Damage to a nest of Formosan subterranean termites brings hoards of workers and soldiers with dark, oval shaped heads scrambling to repair the hole.
CC BY 2.0

Entertainment
Computer animation and games

Whenever you have ...

• a population of reproducing individuals,
• whose offspring are similar but not identical to their parents (thanks to eg. genetic mutations)
• and where some individuals are more likely to produce offspring than others ...

Over many generations, the population will evolve, to contain individuals that are increasingly capable of consistently producing offspring in that environment.

Slides heavily influenced by lectures given by Inman Harvey at University of Sussex http://users.sussex.ac.uk/~inmanh

http://ngm.nationalgeographic.com/ngm/photo-contest/2012/entries/195801/view/

Breeding is one example of an artificial kind of evolution, where people impose artificial selection pressures.

Part of the idea is to harness the "creative power" of evolution.

You select for what you want (e.g. by allowing certain cattle to breed) and hopefully(!) the evolution finds a solution.

Evolving a paper airplane:

1. Generate 20 random sequences of folding instructions
2. Fold each piece of paper according to instructions written on them
3. Throw them all out of the window
4. Pick up the ones that went furthest, look at the instructions
5. Produce 20 new pieces of paper, writing on each bits of sequences from parent pieces of paper (occasionally make a mistake while copying the instructions, “mutation”)
6. Repeat from (2) on.

In biology fitness is (roughly speaking) the likelihood of an individual to procreate before it dies.

In artificial evolution, the fitness of an individual is how good it is at what you want it to do.

An individual that has high fitness is one that is good at the task you are trying to evolve a solution for.

In Nature ...

Genotype: the genetic material, passed down from one generation to the next, undergoes mutation and recombination

• the order of the nucleotides on DNA
• AGGCCACACTTTTCCCGGAC

Phenotype: what undergoes selection “what the genotype codes for”

• typically: the body and the brain

We often have a similar divide in artificial evolution.

Genotype: A set of instructions for creating the phenotype. Passed down from one generation to the next, undergoes mutation and recombination.

• e.g. a set of instructions

Phenotype: What is evaluated for fitness.

• e.g. the paper airplane

We usually need both of these, because the thing that is easy to copy, mutate and recombine is not the thing that is evaluated for fitness.

By studying artificial evolution, we develop a better understanding of some of the processes underlying natural evolution.

• Is one form of mutation or recombination or selection pressure more effective than another?
• What is the best way for a genotype to encode a phenotype?
• How do learning and development affect evolution?
• Can organisms evolve to become more evolvable?
• Why in the fossil record do sudden changes occur rather than steady, gradual changes?
• etc.

Machine Learning
Getting the computer to do something it wasn't explicitly programmed to do. Pattern recognition, behaviour design.

"Create a black box that does X for me."

Engineering
Used to engineer complex non-linear systems that are hard to approach with conventional methods.

The 2006 NASA ST5 spacecraft antenna. This complicated shape was found by an evolutionary computer design program to create the best radiation pattern. https://en.wikipedia.org/wiki/Evolved_antenna

Lots of demos online ...

• http://cs.lmu.edu/~ray/notes/biomorphs/
• http://www.emergentmind.com/animorphs
• http://rednuht.org/genetic_walkers/
• ...

David Goldberg 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley

Melanie Mitchell and Stephanie Forrest 1994, Genetic Algorithms and Artificial Life. Artificial Life, volume 1; 3 pp 267-289.

Melanie Mitchell 1998, An Intro to GAs, MIT Press

Z Michalewicz 1996, GAs + Data Structures = Evolution Programs, Springer Verlag

Karl Simms (1994) Evolved Virtual Creatures -- 4:09