讲解MECS 4510程序、讲解MATLAB程序设计、辅导C++语言编程 辅导Web开发|讲解数据库SQL
- 首页 >> Database Assignment #3
Project
MECS 4510
Evolutionary Computation
Lipson & Pollack, Nature 406, 2000
Assignment 3
• 3a Develop a 3D physics simulator
• Demonstrate a bouncing cube and a ͞breathing͟ cube
• 3b Evolve a fixed-shape robot
• Manually design a robot, evolve a controller to make it move
• 3c Evolve both the shape and behavior of a robot
• Demonstrate a moving robot of various shapes and behavoors
• Final Presentation
Mock exam
Review
Project final presentations
How to build a 3D simulator
Basic steps
Existing Physics Simulators
Build your own!
Why build your own physics simulator?
• Simpler than learning to use other simulator
• Simpler to integrate with your EA
• Robust (wont crash) with garbage generated by an EA
• More versatile physics
• An extra line on your resume
Basic primitives
• Masses
• Point masses (no volume)
• Have position, velocity and acceleration
• Springs
• Massless
• Connect two masses
• Have a rest length and stiffness
• Apply restoring forces on the masses
Basic simulator
• Choose a discrete time step dt
• Not larger than a millisecond (dt=0.001).
• Set global time variable T = 0
• At each time step:
• T = T + dt
• Interaction step:
• Compute and tally all the forces acting on each mass from springs connected it
• Integration step:
• Update position and velocitLJ of each atom using Newton͛s laws of motion Fсma͘
Stick to consistent unit system, e.g. MKS
Relaxation Simulation
First: Data structures
• Mass
• Mass m (scalar)
• Position p (3D Vector)
• Velocity v (3D Vector)
• Acceleration a (3D Vector)
• External forces F (3D Vector)
• Spring
• Rest length L0 (Scalar)
• Spring constant k (scalar) (=EA/L for bars)
• Indices of two masses m1, m2
Dynamic Simulation
• Time increment
• T = T +dt
• Interaction step
• For all springs:
• Calculate compression/extension using F=k(L-L0)
• For all masses:
• Tally forces on each mass
• Add gravity, collision, external forces (if any)
• Integration Step
• Calculate a = F/m (from F=ma)
• Update v = v + dt*a;
• Update p = p + v*dt
• Repeat forever or until reaches equilibrium
dt = simulation timestep (0.001)
Dynamic = real time; geometry, mass, forces, velocities, accelerations
Dynamic Simulation
• Time increment
• T = T +dt
• Interaction step
• For all springs:
• Calculate compression/extension using F=k(L-L0)
• For all masses:
• Tally forces on each mass
• Add gravity, collision, external forces (if any)
• Integration Step
• Calculate a = F/m (from F=ma)
• Update v = v + dt*a;
• If mass is fixed, set v=0
• If dampening, reduce speed v=v*0.999
• If colliding with ground, apply restoring force
• Update p = p + v*dt
• Repeat forever or until reaches equilibrium
dt = simulation timestep (0.001)
Dynamic = real time; geometry, mass, forces, velocities, accelerations
How to handle collisions with the ground?
• Apply a ground reaction force FG once a node goes
below ground (z<0)
• FG= (0,0,-z*KG)
• KG is the spring coefficient of the ground, e.g. 100,000
const double GRAVITY = 9.81;
const double damping = 0.9999;
const double DT = 0.0008; // simulation timestep
const double friction_mu_s = 1; // friction coefficient rubber-concrete
const double friction_mu_k = 0.8;// friction coefficient rubber-concrete
const double k_vertices_soft = 2000; // spring constant of the edges
const double k_ground = 200000;// constant of the ground reaction force
double omega = 10;// this is arbitrary, you can use any that you see fit
Create more complex structures
• Add more cubes
• Share vertices and share springs
• Try making structures out of tetrahedra or other primitives
GPU- Accelerated Physis Simulations with CUDA
• GPU (CUDA) accelerated physics simulation sandbox capable of running complex spring/mass simulations in a fraction of the time of traditional CPU- based software while the CPU continues to perform optimizations.
• Capable of simulating 100,000 springs at about 4000 frames per second, or about 400,000,000 spring updates per second
int main() {
Mass * m1 = sim.createMass(Vec(1, 0, 0)); // create two masses at positions (1, 0, 0), (-1, 0, 0)
Mass * m2 = sim.createMass(Vec(-1, 0, 0));
Spring * s1 = sim.createSpring(m1, m2); // connect them with springs
Cube * c1 = sim.createCube(Vec(0, 0, 3), 1); // create fully-connected cube with side length 1 and center (0, 0, 3)
Plane * p = sim.createPlane(Vec(0, 0, 1), 0); // constraint plane z = 0 (constrains object above xy plane)
sim.setTimeStep(0.0001) // increment simulation in 0.0001 second intervals
sim.setBreakpoint(5.0); // ends simulation at 5 seconds
sim.run( ); // run simulation
// perform other optimizations on the CPU while the simulation continues to run, like topology optimization, robotics, etc.
return 0;
}
Interested in CUDA library? Contact jacob.austin@columbia.edu and Rafael Corrales Fatou rc2997@columbia.edu
Titan
Create animated structures
• Dynamically change L0 of various springs
• For example, change
• L0=a+b*sin(ZT+c)
• The coefficient Z is a global constant that determines the frequency
of oscillations.
• Setting Z =1 will result in a period of 2S sec
• Chose a,b,c randomly within a reasonable range, for each spring.
• Keep some springs at a constant rest length by choosing b=0
Simulation efficiency
• Measured in spring evaluations per second
• Per real second, not per simulated second
• Typical values
• Python: 10,000 springs/sec
• C++: 1.5 Million springs/sec per CPU core
• CUDA/GPU: 600 Million springs/sec (TitanX 2500 cores)
• If efficiency is low, keep structures simple
Elements per second
# Elements
Change material property
• Set spring constant to represent hard and soft materials
• k = 10000 Hard material
• k = 1000 soft material
• Change k as a function of spring length (nonlinear material)
• Change k with time?
• Note: Higher k needs smaller simulation dt
3D Graphics
• Visualization is important
• 3D graphics available for python, MATLAB, C++
• Draw all springs and masses
• Draw ground plane clearly (e.g. grid in different colors)
• Draw external forces
• Use color for visualization, e.g.
• Change spring color with stress (e.g. red in tension, blue in compression)
• Change spring color depending on material type, k, etc.
• You don͛t need to draw the springs and masses everLJ time step͘
• For example, you can have a time-step of dt=0.0001 sec but draw the cube
only every 100 time-steps
Boxi Xia -
Solid appearance
• You scan make the robot look solid by shading (filling in) all the
exterior triangles of the robot.
General tips
• Choosing k and dt is trickLJ͘ If the structure is too ͞wobblLJ͕͟ k is too
small͘ If the structure ͞vibrates͕͟ k is too high. If the structure
͞explodes͕͟ LJour timestep dt or k is too large͘ GenerallLJ͕ set dt to a
small step (e.g. 1E-5) and set k to a low stiffness (e.g. 10,000), and
increase them from there*.
• Once you get it to work, you can easily parallelize the loop in 4a and
4b to use all your CPU cores. For example, in C++ use OMP. If you are
really ambitious, you can even use GPU/CUDA.
• Be sure to use double precision numbers for all your calculations.
*Some students reported good results with k=100,000 and dt = 0.0008
Validation
• If there is no damping or friction,
energy should remain constant
• Plot the total energy of the cube as
function of time (kinetic energy, potential
energy due to gravity, potential energy in
the springs, as well as the energy related
to the ground reaction force). The sum
should be nearly constant. If it is not
constant, you have some bug
Add friction
• When a mass is at or below the ground, you can
simulate friction and sliding. Assume µs is a
coefficient of friction and µk is the kinetic coefficient
• Calculate the horizontal force FH=sqrt(Fx
2+Fy
2) and the
normal force Fn
• If Fn<0 (i.e. force pointing downward) then:
• If FH< -Fn*µs then zero the horizontal forces of the mass
• If FHt -Fn*µs then reduce the horizontal force of the mass
by µk
*Fn
• Update the mass velocity based on the total forces,
including both friction and ground reaction forces
Add dampening
• Velocity dampening
• Multiply the velocity V by 0.999 (or similar) each time step
• Helps reduce vibration, wobbling, and snapping
Add dampening
• Velocity dampening
• Multiply the velocity V by 0.999 (or similar) each time step
• Helps reduce vibration and wobbling
• Add water/viscous dampening
• Apply drag force FD=cv2 in the opposite direction of v (c is drag coef).
Anchors
• Anchor points by setting v=0
• Constrain points to a curve or surface, e.g. set vx=0
Add nonlinear behavior
• Replace F=k(L-L0) with some nonlinear behavior
• Cable
• F=k(L-L0) if L>L0
• F=0 if L<= 0
Final submission for 3a: Breathing cube
• For each spring set k and L0 = a+b*sin(Zt+c)
• Z is global frequency. a,b,c,k are spring parameters (k is spring coef)
• Cycle period is 2S/Z
Assignment 3b
• Parametrically evolve spring rest lengths coefficients to make a
manually designed robot move
Assignment 3b
Evolving Motion
• For each spring set k and L0 = a+b*sin(Zt+c)
• Z is global frequency. a,b,c,k are spring parameters (k is spring coef)
• Cycle period is 2S/Z
• Evolve locomotion
• Fitness: net distance travelled by center of mass
• Representation
• Direct encoding: Chromosome with a,b,c,k for each spring
• Indirect encoding: Chromosome specifies how a,b,c,k are determined
Direct encoding
a1,b1,c1,k1
a2,b2,c2,k2
͙
an,bn,cn,kn
Fitness? Mutation? Crossover?
n = number of springs
Incorporating Sensors
• You can change the length L0 of springs also as function of sensors
• Sensor types:
• External, e.g.
• light level
• Distance to goal
• Internal (proprioceptive)
• Actual length of spring
• Ground force (Whether mass is on or below ground)
• Speed
More complex functions
• L0 = a+b*sin(Zt+c)
• L0 = a+b*sin(Zt+c)+d*sin(2Zt+e)
• L0 = a+b*sin(Zt+c)+d*sin(2Zt+e)+f*sin(3Zt+g)
• ͙
• L0 = f(sin(Zt)) Å Evolve f directly
Assignment 3c
• Evolve morphology
Direct morphological operators
• Control changes
• Change actuation parameters a,b,c,k
• Morphological changes
• Add/remove spring between two exiting masses
• Add/remove mass
• Change mass distribution (but keep total mass constant)
• Change rest length of existing spring
• Some operators require ͞cleanup͟ and bookkeeping
• For example, after removing a mass you may need to remove dangling springs
and update indices of other masses
Developmental encodings
Base Tetrahedron
Growing Designs
Nervus Systems Inc.
Generative Blueprints
Project
MECS 4510
Evolutionary Computation
Lipson & Pollack, Nature 406, 2000
Assignment 3
• 3a Develop a 3D physics simulator
• Demonstrate a bouncing cube and a ͞breathing͟ cube
• 3b Evolve a fixed-shape robot
• Manually design a robot, evolve a controller to make it move
• 3c Evolve both the shape and behavior of a robot
• Demonstrate a moving robot of various shapes and behavoors
• Final Presentation
Mock exam
Review
Project final presentations
How to build a 3D simulator
Basic steps
Existing Physics Simulators
Build your own!
Why build your own physics simulator?
• Simpler than learning to use other simulator
• Simpler to integrate with your EA
• Robust (wont crash) with garbage generated by an EA
• More versatile physics
• An extra line on your resume
Basic primitives
• Masses
• Point masses (no volume)
• Have position, velocity and acceleration
• Springs
• Massless
• Connect two masses
• Have a rest length and stiffness
• Apply restoring forces on the masses
Basic simulator
• Choose a discrete time step dt
• Not larger than a millisecond (dt=0.001).
• Set global time variable T = 0
• At each time step:
• T = T + dt
• Interaction step:
• Compute and tally all the forces acting on each mass from springs connected it
• Integration step:
• Update position and velocitLJ of each atom using Newton͛s laws of motion Fсma͘
Stick to consistent unit system, e.g. MKS
Relaxation Simulation
First: Data structures
• Mass
• Mass m (scalar)
• Position p (3D Vector)
• Velocity v (3D Vector)
• Acceleration a (3D Vector)
• External forces F (3D Vector)
• Spring
• Rest length L0 (Scalar)
• Spring constant k (scalar) (=EA/L for bars)
• Indices of two masses m1, m2
Dynamic Simulation
• Time increment
• T = T +dt
• Interaction step
• For all springs:
• Calculate compression/extension using F=k(L-L0)
• For all masses:
• Tally forces on each mass
• Add gravity, collision, external forces (if any)
• Integration Step
• Calculate a = F/m (from F=ma)
• Update v = v + dt*a;
• Update p = p + v*dt
• Repeat forever or until reaches equilibrium
dt = simulation timestep (0.001)
Dynamic = real time; geometry, mass, forces, velocities, accelerations
Dynamic Simulation
• Time increment
• T = T +dt
• Interaction step
• For all springs:
• Calculate compression/extension using F=k(L-L0)
• For all masses:
• Tally forces on each mass
• Add gravity, collision, external forces (if any)
• Integration Step
• Calculate a = F/m (from F=ma)
• Update v = v + dt*a;
• If mass is fixed, set v=0
• If dampening, reduce speed v=v*0.999
• If colliding with ground, apply restoring force
• Update p = p + v*dt
• Repeat forever or until reaches equilibrium
dt = simulation timestep (0.001)
Dynamic = real time; geometry, mass, forces, velocities, accelerations
How to handle collisions with the ground?
• Apply a ground reaction force FG once a node goes
below ground (z<0)
• FG= (0,0,-z*KG)
• KG is the spring coefficient of the ground, e.g. 100,000
const double GRAVITY = 9.81;
const double damping = 0.9999;
const double DT = 0.0008; // simulation timestep
const double friction_mu_s = 1; // friction coefficient rubber-concrete
const double friction_mu_k = 0.8;// friction coefficient rubber-concrete
const double k_vertices_soft = 2000; // spring constant of the edges
const double k_ground = 200000;// constant of the ground reaction force
double omega = 10;// this is arbitrary, you can use any that you see fit
Create more complex structures
• Add more cubes
• Share vertices and share springs
• Try making structures out of tetrahedra or other primitives
GPU- Accelerated Physis Simulations with CUDA
• GPU (CUDA) accelerated physics simulation sandbox capable of running complex spring/mass simulations in a fraction of the time of traditional CPU- based software while the CPU continues to perform optimizations.
• Capable of simulating 100,000 springs at about 4000 frames per second, or about 400,000,000 spring updates per second
int main() {
Mass * m1 = sim.createMass(Vec(1, 0, 0)); // create two masses at positions (1, 0, 0), (-1, 0, 0)
Mass * m2 = sim.createMass(Vec(-1, 0, 0));
Spring * s1 = sim.createSpring(m1, m2); // connect them with springs
Cube * c1 = sim.createCube(Vec(0, 0, 3), 1); // create fully-connected cube with side length 1 and center (0, 0, 3)
Plane * p = sim.createPlane(Vec(0, 0, 1), 0); // constraint plane z = 0 (constrains object above xy plane)
sim.setTimeStep(0.0001) // increment simulation in 0.0001 second intervals
sim.setBreakpoint(5.0); // ends simulation at 5 seconds
sim.run( ); // run simulation
// perform other optimizations on the CPU while the simulation continues to run, like topology optimization, robotics, etc.
return 0;
}
Interested in CUDA library? Contact jacob.austin@columbia.edu and Rafael Corrales Fatou rc2997@columbia.edu
Titan
Create animated structures
• Dynamically change L0 of various springs
• For example, change
• L0=a+b*sin(ZT+c)
• The coefficient Z is a global constant that determines the frequency
of oscillations.
• Setting Z =1 will result in a period of 2S sec
• Chose a,b,c randomly within a reasonable range, for each spring.
• Keep some springs at a constant rest length by choosing b=0
Simulation efficiency
• Measured in spring evaluations per second
• Per real second, not per simulated second
• Typical values
• Python: 10,000 springs/sec
• C++: 1.5 Million springs/sec per CPU core
• CUDA/GPU: 600 Million springs/sec (TitanX 2500 cores)
• If efficiency is low, keep structures simple
Elements per second
# Elements
Change material property
• Set spring constant to represent hard and soft materials
• k = 10000 Hard material
• k = 1000 soft material
• Change k as a function of spring length (nonlinear material)
• Change k with time?
• Note: Higher k needs smaller simulation dt
3D Graphics
• Visualization is important
• 3D graphics available for python, MATLAB, C++
• Draw all springs and masses
• Draw ground plane clearly (e.g. grid in different colors)
• Draw external forces
• Use color for visualization, e.g.
• Change spring color with stress (e.g. red in tension, blue in compression)
• Change spring color depending on material type, k, etc.
• You don͛t need to draw the springs and masses everLJ time step͘
• For example, you can have a time-step of dt=0.0001 sec but draw the cube
only every 100 time-steps
Boxi Xia -
Solid appearance
• You scan make the robot look solid by shading (filling in) all the
exterior triangles of the robot.
General tips
• Choosing k and dt is trickLJ͘ If the structure is too ͞wobblLJ͕͟ k is too
small͘ If the structure ͞vibrates͕͟ k is too high. If the structure
͞explodes͕͟ LJour timestep dt or k is too large͘ GenerallLJ͕ set dt to a
small step (e.g. 1E-5) and set k to a low stiffness (e.g. 10,000), and
increase them from there*.
• Once you get it to work, you can easily parallelize the loop in 4a and
4b to use all your CPU cores. For example, in C++ use OMP. If you are
really ambitious, you can even use GPU/CUDA.
• Be sure to use double precision numbers for all your calculations.
*Some students reported good results with k=100,000 and dt = 0.0008
Validation
• If there is no damping or friction,
energy should remain constant
• Plot the total energy of the cube as
function of time (kinetic energy, potential
energy due to gravity, potential energy in
the springs, as well as the energy related
to the ground reaction force). The sum
should be nearly constant. If it is not
constant, you have some bug
Add friction
• When a mass is at or below the ground, you can
simulate friction and sliding. Assume µs is a
coefficient of friction and µk is the kinetic coefficient
• Calculate the horizontal force FH=sqrt(Fx
2+Fy
2) and the
normal force Fn
• If Fn<0 (i.e. force pointing downward) then:
• If FH< -Fn*µs then zero the horizontal forces of the mass
• If FHt -Fn*µs then reduce the horizontal force of the mass
by µk
*Fn
• Update the mass velocity based on the total forces,
including both friction and ground reaction forces
Add dampening
• Velocity dampening
• Multiply the velocity V by 0.999 (or similar) each time step
• Helps reduce vibration, wobbling, and snapping
Add dampening
• Velocity dampening
• Multiply the velocity V by 0.999 (or similar) each time step
• Helps reduce vibration and wobbling
• Add water/viscous dampening
• Apply drag force FD=cv2 in the opposite direction of v (c is drag coef).
Anchors
• Anchor points by setting v=0
• Constrain points to a curve or surface, e.g. set vx=0
Add nonlinear behavior
• Replace F=k(L-L0) with some nonlinear behavior
• Cable
• F=k(L-L0) if L>L0
• F=0 if L<= 0
Final submission for 3a: Breathing cube
• For each spring set k and L0 = a+b*sin(Zt+c)
• Z is global frequency. a,b,c,k are spring parameters (k is spring coef)
• Cycle period is 2S/Z
Assignment 3b
• Parametrically evolve spring rest lengths coefficients to make a
manually designed robot move
Assignment 3b
Evolving Motion
• For each spring set k and L0 = a+b*sin(Zt+c)
• Z is global frequency. a,b,c,k are spring parameters (k is spring coef)
• Cycle period is 2S/Z
• Evolve locomotion
• Fitness: net distance travelled by center of mass
• Representation
• Direct encoding: Chromosome with a,b,c,k for each spring
• Indirect encoding: Chromosome specifies how a,b,c,k are determined
Direct encoding
a1,b1,c1,k1
a2,b2,c2,k2
͙
an,bn,cn,kn
Fitness? Mutation? Crossover?
n = number of springs
Incorporating Sensors
• You can change the length L0 of springs also as function of sensors
• Sensor types:
• External, e.g.
• light level
• Distance to goal
• Internal (proprioceptive)
• Actual length of spring
• Ground force (Whether mass is on or below ground)
• Speed
More complex functions
• L0 = a+b*sin(Zt+c)
• L0 = a+b*sin(Zt+c)+d*sin(2Zt+e)
• L0 = a+b*sin(Zt+c)+d*sin(2Zt+e)+f*sin(3Zt+g)
• ͙
• L0 = f(sin(Zt)) Å Evolve f directly
Assignment 3c
• Evolve morphology
Direct morphological operators
• Control changes
• Change actuation parameters a,b,c,k
• Morphological changes
• Add/remove spring between two exiting masses
• Add/remove mass
• Change mass distribution (but keep total mass constant)
• Change rest length of existing spring
• Some operators require ͞cleanup͟ and bookkeeping
• For example, after removing a mass you may need to remove dangling springs
and update indices of other masses
Developmental encodings
Base Tetrahedron
Growing Designs
Nervus Systems Inc.
Generative Blueprints