Transcript [ slides ] Evolving virtual creatures

Evolving Virtual Creatures
by Karl Sims (1995)
Adelein Rodriguez
Outline
• Goal & Perspective
• Motivation
• Creatures
• Morphology
• Control
• Evolution
• Coevolution
• Demo
• Comments
• Other Work
Goal
• Automatically create creatures by evolving its
morphology and behaviour.
• Creatures will be optimized for specific tasks
such as walking, jumping, and swimming.
• Perspective:
• Karl Sims had previously evolved expressions for
creating virtual plants, particle effects, and others.
• Genetic Programming recently invented (1992),
evolving of variable length genomes.
• MIT Media Lab
• This work has been referenced 440 times.
Motivation
• Tedious coding process for creating behaviours
that look realistic.
• Entertainment industry:
• Creating film effects
• Creating characters
• Need specific behaviours, thus optimization
technique such as evolution can help bias.
• Previous work evolved either the morphology, or
the control structure, but not both.
• Here we want to evolve a control for a structure,
and a structure for the control.
The big picture
• Genotype
• Directed graphs of nodes and
connections. Graphs provide instructions
for building a creature and cycles for
repeating same part.
• Phenotype
• Body parts are made by starting at the
root node of the directed graph and
following the connections.
Morphology
• Node
• Dimensions
• Joint type: Defines degrees of freedom & type of
movement relative to parent part.
• Revolute
• Rigid
• Twist
• Universal
• Etc...
• Joint Limits: Point at which need to exert string
forces.
• Node (cont)
• Recursive Limit: No. of times it can generate a
part from a cycle.
• Neurons: Given an input perform a function to
produce and output.
• Connections to other nodes (parts)
• Position, orientation, scale, and reflection,
terminal only flag.
Example Hand Designed Topologies
Control
Sensors
• Connected to:
• Effector
• Neuron
• “Embedded” in body parts:
• Joint angle sensors: monitors values of degrees of
freedom.
• Contact Sensors: Positive activation (1,0) if contact.
Negative activation (-1,0) if no contact. Present on all
surfaces.
• Photosensors: 3 sensors combined to get
coordinates of global light source.
• Sensors enabled depending on environment.
(Manually?)
Neurons
• Functions: sum, product, threshold, min,
max, if, sigmoid, oscillate-wave, etc.
• Two types of functions:
• Operate on input and give output directly
• Recurrence, output depends on time
step. Can give different output even if
inputs is constant. Memory.
Effectors
• Connected to:
• Sensor
• Neuron
• Value is exerted as a joint force
• Maximum strength proportional to the max
cross sectional area of the 2 parts it joins.
Force scales with area.
Going from genotype to phenotype
• Iterate over directed graph to create body parts:
• Blocks of neural circuitry can be replicated together with
morphological nodes.
• There can be connections between adjacent parts .
Sensors, neurons and effectors from one part can
connect to sensors, neurons and effectors from other
part. Allows coordination.
• There is a separate graph of neurons not tied to any part.
Phenotype has only one copy of this graph. Brain ?
• Can allow centralized control
How it all comes together
• Nodes contain sensors, neurons (graphs), and
effectors.
• Connections allow flow of signals between
nodes.
The idea
• Similar to Nervous System:
• Localized distributed control
(neurons for every part)
• Central control (separate groups of
neurons)
Phenotype Brain
Phenotype Morphology
This creature swims by making
paddling motions with the flippers
Evolution
• Initial population: random genotypes and
previous evolution genotypes.
• Population size: 300
• Selection: Top fit 1/5 of population survives to
next generation.
• Fitness evaluation: place creature in a simulated
environment, goal is to optimize for specific task
or behaviour (e.g. jumping).
• Pre-screening process.
Fitness Evaluation
• 4 Different Evolutions, each with
different tasks:
• Swimming
• Walking
• Jumping
• Following
Swimming
•
•
•
•
Simulated environment has no gravity.
Viscosity effect.
Faster it swims, higher fitness.
Straight swimming gets higher fitness than
circling.
• Continuous movement gets higher fitness than
initial drastic jumps.
Walking
• Walking = kind of moving on land.
• Gravity and friction.
• Faster it moves, better. Vertical movement is
ignored.
• Environment could have other objects.
Jumping
• Measure vertical movement.
Following
•
•
•
•
Task is to follow a light source
Many trials with light source at different positions
Faster it moves towards light source better.
Land and water environments.
Evolution (Cont)
• Get surviving creatures, mate and/or
mutate them.
• Reproduction: Only highest fit can
reproduce, higher fit reproduce more.
• To create an offspring you can
mutate a parent, or mate two parents
by either one of two crossover types.
Mutation
• Graph mutation steps:
• 1) Node's internal parameters
• Boolean values change from true to false and vice
versa.
• Scalar values change according to a Gaussian
scale (Small adjustments are more likely than
drastic ones)
• 2) Add a new node to graph
• Must be followed by a mutation that adds a
connection to it in order to have effect.
Mutation (Cont)
• Graph mutation steps (cont):
• 3) Connection's internal parameters
• 4) Add/Remove a connection (can only happen in
morphological graphs, nor neural ones)
• 5) Remove unconnected nodes and neurons.
• Morphology graphs mutated first, then inner
graphs.
Mating
• Combines structures from two parent
genotypes to make an offspring.
• Used two mating types:
• Crossover:
• Graft
Evolution (Cont)
• Some creatures from one evolution
were used as seeds for other
evolutions.
• A creature from one medium could
be used for evolution in another
medium.
Co Evolution
• Evolving 3D Morphology and
Behaviour by Competition (1994)
• Place pairs of creatures in an arena to
compete for a common resource.
• Taller creatures start further back.
How to pair individuals
• Each to all
• Very expensive
• Each to some
• Might not get correct idea of fitness
relative to others.
• Species intrabreeding
• Species interbreeding
Interesting results
• Interspecie competition was observed
where both species developed
different techniques for grabbing the
cube, then tried to add techniques to
stop the other from grabbing it.
• Push cube from opponent, then
follow it.
• Demo
Additional Comments
• Genotype-Phenotype encoding allows to specify the
structure and behaviour in a compact way. Indirect
encoding.
• Only need to specify a few building blocks and the rules
for how to combine the building blocks
• Information reuse, modularity.
• Avoids hardships of hand coded designs. Very useful for
automatic content creation (Games)
• Use of evolutionary search allows for parallel search over
many possible structures and behaviours.
• Neural structure is added as needed and tightly connected
to the morphological structure. Co-adapation.
Additional Comments (Cont)
• Evolution attempts to find (“learn”) the
best mapping of sensors and effectors
by being exposed to the environment.
• Downside: Fitness function and
genotype language encoding need a
lot of hand design.
Other Related Work
• http://sodarace.net/
• http://www.frams.alife.pl/a/al_pict.html