Genetic Simulation of a Luxo Lamp

Luxo in action

The Project

Initially, my project was to simulate a luxo lamp jumping using spacetime constraints (as done in the Spacetime Constraints paper by Witkin and Kass). After hearing the presentation on Genetic Algorithms and Controller search, where the ideas of the Witkin and Kass paper were re-implemented using several forms of genetic simulation rather than constraint optimization, I decided to change to a genetic approach both because I had access to several large clusters of machines and because I felt that a genetic simulation would be much easier to debug.

In the end, the project consisted of three pieces, the physical simulation engine, the genetic evolution engine, and the frontends.

The Simulator

The simulator is a second-order 2D simulation engine that takes 1D rigid bodies connected by joints in any topology. Joints connect two rigid bodies and serve two functions: first, to keep the bodies connected, and secondly, to maintain the angle between the bodies at the current target angle of the joint. Joint target angles are animated through lisp-like expressions that can have time dependence only.

The simulation loosely follows the form of a second order predictor-corrector using Euler integration:

• Constant/global forces are applied to the bodies (gravity, etc.)
• The world is test integrated forward with the given timestep.
• The constraints are walked, generating corrective forces.
• The world is integrated forward taking into account the constraint forces.

Genetic Engine

The genetic engine goes through four main stages for each generation of simulation: evolution, simulation, fitness evaluation and liquidation. The engine state is a list of genomes, groups of expressions that target the joint angles of the luxo lamp, which when applied to the rigid body system, can be simulated using the simulation engine.

Evolution

Each generation, the genetic engine takes the current genome pool, creates a number of children equal to a certain percentage of the population (reproduction rate) by taking two random parents (with fitter parents chosen with higher frequency) and performing a crossover. This crossover occurs only for the top level expressions. The population is then padded to the maximum population size by creating genomes randomly.

The genome pool, now at its maximum size, under goes a mutation specified by the mutation probability. Mutations travel down the expression trees of a genome and manifest themselves in typically three ways:

• Nodes with children can delete up to one of their children and replace them with a randomly created expression tree.
• Constant values can be perturbed with magnitude relative to themselves.
• Nodes with two or more children can swap the positions of two children.

Simulation and Fitness Evaluation

After updating the population pool, all of the genomes are then simulated using the simulation engine described above, and statistics such as maximum height, final position and orientation, whether self-intersection occurred, etc. are logged and evaluated by the fitness function (currently hard-coded into the genetic simulator). The population of genomes is then sorted by fitness.

Liquidation

Frontends

There are two programs that were written for this project, the first is Viewer, a program that takes a config file, simulates and displays it in real time using the first block of expressions as the joint angle target expressions. The other is GenSim, the genetic simulation engine that takes a config file, parses the population and runs the genetic simulation as described above on the population.

Both take the same format of config file:

// Bad ASCII drawing of a luxo lamp with the bodies numbered
//
//       /\4   
//     3/  \ 
//     /
//     \
//     2\  
//       \ 
//       1|
//  0 ---------
//
bodies
(body (-0.5, 0) (0.5, 0) 1)
(body (0, 0) (0, 0.1) 0.4)
(body (0, 0.1) (-0.5, 0.6) 0.4)
(body (-0.5, 0.6) (0, 1.1) 0.4)
(body (0, 1.1) (0.25, 0.85) 0.2)
joints
(constantjoint (0, 0) (1, 0.05) -1.5708)
(joint (1, -0.05) (2, 0.353553) -0.471239)
(joint (2, -0.353553) (3, 0.353553) 1.5708)
(joint (3, -0.353553) (4, 0.176777) 1.5708)
exps
(* (-0.5) 
   (* (sin (* (10) (t))) 
      (sin (t))))
(* (-1) 
   (* (sin (* (10) (t))) 
      (sin (t))))
(* (-1) 
   (* (sin (* (10) (t))) 
      (sin (t))))
// optionally more blocks of expressions follow

Viewer

Usage: ./Viewer <simfile> [loop time] [strobe]

• simfile is the name of the config file to simulate.
• loop time sets the simulation to loop after a certain number of seconds.
• strobe sets the simulation to display a composite of images from 0 to loop time with interval strobe

In the Viewer window, 's' and 'a' zoom in and out (respectively), and dragging with the mouse adds a force to the center of mass of the 0th rigid body (the base, in the case of luxo).

GenSim

Usage: ./GenSim <input file> <output file> <num_gen> <max_pop> <sim_len>

• input file is the config file to use as input
• output file is the config file to output to (this is done every generation)
• num_gen is the number of generations to simulate
• max_pop is the maximum population to use for the genome pool
• sim_len is the amount of time to run the simulation for

GenSim outputs the current state after every generation to output file, also the best simulation to date is kept in .best.file.

Results

Here is an animated gif of the results of a simulation where the fitness function was hight. The frames of the animation are taken from every time that the simulation showed a significant improvement (usually about every 5-10 generations or so).

Interesting Avenues for Future Exploration

The first thing that should probably be done to the luxo simulation is to make the fitness function for the genetic simulation a config file rather than hard-coded. Another thing that I probably should have done at the beginning is to make the joint angle target expressions B-Spline curves rather than S-expressions. This would probably speed up the simulation greatly, have a better semantic for what mutations do. Also, crossovers for the expressions at points other that a top-level selection would be trivial to implement and they would actually have a reasonable physical meaning.

Source

Source code for the luxo simulator is available here. The simulation would once work under windows, but after I wrote the expression code it no longer compiles due to a bug in the Visual Studio 6.0 compiler^*.