Transcript Evolving Virtual Creatures Paper by Karl Sims Presented by Sarah

Evolving Virtual Creatures
&
Evolving 3D Morphology and
Behavior by Competition
Papers by Karl Sims
Presented by Sarah Waziruddin
Motivation
 What: Automatically generate physically
simulated characters without fully
understanding the procedures used to
control them
 How: Utilize optimization technique to
generate complex behaviours
automatically
Use of Optimization in this
paper
 Genetic Algorithm used as an
optimization technique to search
genotypes (encoding of a solution)
Genetic Algorithms
 Imitate the processes of evolution and
natural selection in biological world to
generate/evolve the best solution
Genetic Algorithms
 Goal: Create a computer program to solve
a problem defined by high level
statements
 High level statements:
 Define objective function
 Define and implement genetic representation
 Define and implement genetic operators






Genetic Algorithms
[Start] Generate random population of n suitable solutions
for the problem
[Fitness] Evaluate the fitness of each solution in the
population
[New population] Create a new population:
 [Selection] Select two parent solutions from a
population according to their fitness (the better fitness,
the bigger chance to be selected)
 [Mutation] With a mutation probability, mutate new
offspring at each position in solution
 [Sexual Reproduction] With some probability, combine
parents to form new offspring
[Replace] Replace current population with newly generated
population
[Test] If the end condition is satisfied, stop, and return the
best solution in current population
[Loop] Go to Fitness Step
Application of Genetic Algorithm
 Define objective function
 Define and implement genetic
representation
 Define and implement genetic
operators
Objective Function
 Stated implicitly
 To create realistic looking and
acting creatures
 Fitness functions used to help
evaluate if the objective function is
satisfied
Genetic Representation
 Defined by creature morphology and
neurology
 Morphology: “The form and structure of
an organism or one of its parts”
 Neurology (Nervous system): “The
system of cells, tissues, and organs that
regulates the body's responses to internal
and external stimuli”
Creature Morphology
 Articulated three dimension rigid body
parts
 Represented as a directed graph of
nodes and connections
 Each node describes one body part
 Many parameters to a node
Creature Neurology
 Comprised of:
 Sensors
 Neurons
 Effectors
Sensors
 Each sensor is at a different part of the
body
 Measure
 That body part
 The world relative to that body part
 Different types of sensors
 Joint angle sensor
 Contact sensors
 Photo sensors
Neurons
 Virtual brain: Function based on sensor
input
 Provides output effector values
Effectors
 Each effecter controls a degree of
freedom in a joint
 Each effectors value is applied as forces
or torques
 Only exert simulated muscle force
 Connected to neuron or sensor
Neural System
 Local neural system:
 Neural system generated along with
morphological system
 Connection allowed between local neural
systems
 Global neural system:
 Neurons not associated with a specific node
 Can be connected with local neural systems
Genetic Operators: Mutation (1/5)
Alter internal node parameters
 Dimensions- determine the physical shape of





the part
Joint type- number of DOF for each joint and
movement allowed for each DOF
Joint limits- point where spring forces will be
exerted for each DOF
Recursive limit
Set of local neurons
Set of connections to other nodes
 Position, orientation, scale and reflection
relative to parent
Genetic Operators: Mutation (2/5)
Add a new node at random
Leg
Segment
Body
Segment
Head
Segment
Genetic Operators: Mutation (3/5)
Parameter of each connection is
subject to change
Leg
Segment
Body
Segment
45
90
Genetic Operators: Mutation (4/5)
New connections are added at
random and old ones are deleted
Leg
Segment
Body
Segment
Head
Segment
Genetic Operators: Mutation (5/5)
Delete unconnected nodes
Leg
Segment
Body
Segment
Head
Segment
Genetic Operators: Crossover
Genetic Operators: Grafting






Genetic Algorithms
[Start] Generate random population of n suitable solutions
for the problem
[Fitness] Evaluate the fitness of each solution in the
population
[New population] Create a new population:
 [Selection] Select two parent solutions from a
population according to their fitness (the better fitness,
the bigger chance to be selected)
 [Mutation] With a mutation probability, mutate new
offspring at each position in solution
 [Sexual Reproduction] With some probability, combine
parents to form new offspring
[Replace] Replace current population with newly generated
population
[Test] If the end condition is satisfied, stop, and return the
best solution in current population
[Loop] Go to Fitness Step
Start
 Generate random population of n
suitable solutions for the problem
 Random generation of nodes and
connections
 Use existing genotype to seed function
 Create genotype manually to seed function
Fitness
 Swimming, walking, jumping
 Distance travelled by COM/unit of time
 Following
 Speed at which creature moves towards
target
 Competition
 Pairs of individuals compete for control over a
cube
 Final distance of the creature from cube and
opponents final distance from cube
New population
 Survival ratio: 1/5 of 300
 40% mutation, 30% crossover, 30%
grafting
 Children from crossover and
grafting are sometimes mutated
Results
 Different runs converged on characters
with different evolved characteristics
 Specify a User Preference using the
Algorithm
 User can specify a preference over multiple
runs of the simulation
 User can perform the natural selection
Results
Video
Advantages
 Generate characters without specification
or knowledge about exactly how they
work
 Less likely to get stuck on a local solution
since we are searching on an encoding
 Easy to parallelize
Disadvantages
 The characters could produce incorrect
behaviour that could go undetected because of
the lack of understanding of the underlying
algorithm
 Process is not very reusable
 Can reuse some of the components of the
implementation, for example, the neuron language
 Genetic Algorithms sometimes require a lot of
tweaking to work right
Disadvantages
 Difficult to obtain ideal size for the neuron
language, node types and parameters (joint
types and parameters and connection
parameters), sensor and effecter types
 i.e. Difficult to obtain best size for the search
space
 If the size is too small, then there aren't enough
variations in the population
 If the size is too large, then changes in isolated
parts of the creature do not have a big affect on the
behavior or structure
Questions
?
References
 http://www.genetic-programming.com/
 http://lancet.mit.edu/~mbwall/presentations
/IntroToGAs/
 http://cs.felk.cvut.cz/~xobitko/ga/
Physical Simulation
 Dynamics used to calculate movement of
characters





Articulated body dynamics
Numerical Integration
Collision detection and response
Friction
Option viscous fluid
 Crucial for the physical simulator to be bug
free as the GA will find ways to exploit
bugs