Transcript PowerPoint
CS 551 Computer Animation Lecture 15 Evolved Virtual Creatures For next week Video Textures: Schodl et al. Retargeting Motion to New Characters: Gleicher Karl Sims Panspermia (1990) Particle Dreams (1988) Karl Sims Evolved Virtual Creatures (SIGGRAPH 1994) Evolving 3D Morphology and Behavior by Competition (ALIFE 1994) Motivation Automatically generate physically simulated characters without fully understanding the procedures used to build and control them • Morphology • Control Creating animation from scratch Typical Scenario • 20 seconds of animation • 17 controlled DOFs • (20 * 30 * 17) = 10,200 torque values to determine • No approximations to best answer are known – Spacetime constraints would use initial guess to find local maximum Creating animation from scratch Searching for 10,2000 unknowns • We cannot prescribe initial values with confidence • We can prescribe some behaviors and principles we think the motion will demonstrate – The movements at some DOFs are functions of movements at other DOFs Sun and Metaxas – Automating Gait Generation, SIGGRAPH 01 So we’re not really working from scratch Searching for 10,200 unknowns • How to incorporate our motion heuristics into search? – Simulated annealing? – Neural networks? – Spacetime constraints? – Genetic algorithms? But we don’t know the morphology The previous example assumed a known morphology • We’re searching for best architecture AND best control simultaneously! Our search space just grew to an unknown degree! Genetic Algorithms Imitate the processes of evolution and natural selection in biological world to generate/evolve the best solution (not to scale) Genetic Algorithms Inject user knowledge • Objective function • Genetic representation – Let’s search for collection of joints – Let’s not search for n * 30 * 20 unknown joint torques – Instead, search for n equations that are logical combinations of virtual sensors of creature state – These equations are reused for all timesteps • Genetic operators – Recombination and mutation Sensibility of GA for this problem Motion principles described as heuristics • Minimize angular disturbances by swinging legs in opposite directions • Maximize balance by keeping center of mass above platform of support • Kinematics of arm are similar to kinematics of leg So let’s find those heuristics and permit them to be shared across limbs Related work Ngo and Marks – Spacetime Constraints Revisited (SIGGRAPH 88) van de Panne and Fiume – Sensor-actuator Networks (SIGGRAPH 93) Dr. P’s L-system trees – published everywhere Juan Buhler Genetic Algorithms • [Start] Generate random population of n suitable solutions for the problem • [Fitness] Evaluate the fitness of each solution in the population by running physical simulation • [New population] Create a new population • [Replace] Replace current population with newly generated population • [Test] If the end condition is satisfied, stop, and return the best Genetic Algorithms Create a new population • [Selection] Select two parents solutions according to their fitness • [Recombination] Combine parents to form offspring • [Mutation] Potentially new offspring at each position Application of Genetic Algorithm • Objective function • Genetic representation • Genetic operators Objective Function • 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 effector controls a degree of freedom in a joint Each effector’s 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 – Useful heuristic for creating global timing mechanisms • Can be connected with local neural systems Neural System • Sum, product, divide, threshold, >, sign, min, abs, if, interpolate, sine, cosine, atan, log, exponent, sigmoid, integrate, differentiate, smooth, memory, wave, sawtooth Physical Simulation • Featherstone’s articulated body method • Runge-Kutta-Fehlberg – Adaptive timestep typically 1-5 steps per 1/30 second • Bounding boxes to reduce collision checks – Connected pairs can interpenetrate but cannot rotate entirely through one another • Impulses and springs used for collision corrections • Viscosity used for underwater Genetic Operators: Mutation 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 Add a new node at random Leg Segment Body Segment Head Segment Genetic Operators: Mutation Parameter of each connection can change Leg Segment Body Segment 45 90 Genetic Operators: Mutation Add/remove connections Leg Segment Body Segment Head Segment Genetic Operators: Mutation Delete unconnected nodes Leg Segment Body Segment Head Segment Genetic Operators: Crossover Genetic Operators: Grafting 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 traveled 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 behavior 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 effector 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 effect on the behavior or structure Additional References http://www.genetic-programming.com/ http://lancet.mit.edu/~mbwall/presentations/IntroT oGAs/ http://cs.felk.cvut.cz/~xobitko/ga/