learning motion: evolutionary techniques for developing character controllers

robert rose, under the guidance of dr. ron metoyer.

summary

The goal of my research is to develop a controller for a real-time physically simulated humanoid character that can balance and walk in "harsh" environments. The character should be able to remain balanced and/or walking when random forces attempt to knock it over.

Think "Dead or Alive 3" with realistic game physics--when you punch your opponent in the chest, they actually lurch back to remain balanced rather than cut to a mocap sequence.

I am attempting to solve this problem using a variety of evolutionary programming techniques. My first attempt used a static neural network with weights decided by a genetic algorithm. My second attempt used a virtual register machine with an extremely reduced linear instruction set with operations decided by a genetic algorithm. In the near future I hope to attempt an evolutionary technique that develops a neural network by evolving not only the weights but also the structure. I also hope to try a non-linear instruction set virtual register machine.

Today, my research is showing some promise but is far from complete. Using the first technique (above) I have successfully developed a controller for a simple 2 DOF character that can balance itself, but it is far from robust enough to handle the "harsh" environments I hope to put it through. You can read more about my current status more below.

related work

• Krister Wolff has developed a walking controller for a 12 DOF character using genetic programming. Wolff's approach uses a linear instruction set virtual register machine and a character simulated in ODE.
• Stephane Mojon has developed a walking controller for a 25 DOF character using genetic algorithms to optimize the solution to a sinusoidal locomotion function. Mojon's character is simulated using Webots.
• Yariv Bachar has developed a walking controller for a 25 DOF character using Zero Movement Point control. Bachar's character is simulated using Webots.


In all of the related work that I have found, we are yet to see a robust, realistic looking controller that can survive in a "harsh" environment. Existing work today appears to rely on precise initial conditions and no external forces being applied to the character.

status

06.07.04 : Initial writeup

It's the end of the term and I owe my professors a writeup of what I've done so far. You can download the paper here. The presentation materials are available here.

05.17.04 : Give 100 monkeys 100 generations...

Last week I scrapped the wheeled robot approach and went with a three segment robot. At first this caused a lot of headaches because ODE doesn't handle interpenetrating objects very well at all if they are connected by [hinge] joints. I wasted hours trying to get it to work, and I almost had something that was very realistic by modifying ODE's ERP and CFM parameters, but it would only be stable (for the same initial conditions and time steps!) about 9 out of 10 trials. That other 1 trial would just blow up on me. So I scrapped handling interpenetrations in the robots and just set up joint limits. Sigh.

I also scrapped my neural network code and rewrote it all. Doesn't work any better, but now I'm modeling the network as a directed graph, so eventually I'll be able to evolve the structure of the network a la Karl Sims' paper. I also added support for different activation functions, I think eventually I'll want to throw in some sine neurons instead of just sigmoids. (Yup, Sims did that too)..

I have a cool demo to share now, this video shows 100 agents all trying to remain standing. Their fitness function is the height at which they are standing. The robot with the best fitness is highlighted in green. Their neural network is a simple recurrent network with two outputs: knee and ankle torque (scaled from 0..1 to -2500..2500) and six inputs: knee angle (-Pi..Pi), ankle angle (-Pi..Pi), current height (0..inf), "touching" the ground (-10 or 10), and the previous knee and ankle torques the net choose to apply (0..1). Figuring out these input ranges took hours and hours of guesswork and observation. Eventually when I get around to the "evolutionary" part of this project I'll start evolving these I suppose. Here's the video.

I also have a rough draft of my presentation.

05.07.04 : Wheeled robots and a framework for neural networks

Week two of school I began coding away on this project. I thought a good place to start would be to develop a framework that allowed me access ODE in a more object-oriented manner, as ODE straight out of the box is plain C. I wanted to be able to capture lists of ODE "objects" as C++ objects and work with them with STL lists and vectors. I structured my code so that all objects extended from DObject. I created several subclasses of this type like DSphere, DPlane, DCylinder, etc., each basically relied on DObject to do the ODE stuff (collision, positioning, rotation) but differed in it's Render() method implementation. I experimented with this framework until I was satisified it would fit my needs. Mostly it has, with a few tweaks here and there.

Next I wrote a small framework for handling neural nets. Never written a neural network program before, but it didn't seem that hard so I just flipped open my AI book and started coding. I created a base class NNode to represent a neuron and a class NNetwork that stores a multi-dimensional array of NNode's. I simply hard-coded NNode to have a fixed number of inputs (100) and initialized them all to 0.0, so no matter what the weights these inputs won't have any effect on the neuron until given an input other than 0.0.

I'm new to neural networks, and since I'm not writing a back-prop network I still don't have any idea if I did the neural network correctly. It's really tough to step through in a debugger and verify it's behaving correctly. I'm tempted to strip the code out, put it in it's own program, write a back-prop algorithm and test it properly, but, eh, that's more work. ;-)

Since I'm supposed to eventually drive the weights in the neural network using genetic programming, I designed the neural network so that the weight of an input on each neuron can be specified using an integer instead of a float/double. The integer is transformed using some constant to a floating point value usable by the neuron; I can also query the neuron for it's weights either as integers or the "true" floating point value. Using the integers I can query all of the neurons for their values and build up a big chromosome that represents all of the weights in the neural network.

Once I [thought I] had the neural network in place I constructed what I thought would be a simple task of building a small robotic model. I started with two wheels hooked together with a big board connecting them at the front of the board. I thought what would happen would be the wheels would move and drag the end of the board around behind it. What ended up happening wasn't at all what I expected. No matter how I tweaked the collision parameters with ODE the board that was supposed to cause drag on the robot bounced repeatedly until it violently bounced the robot over onto it's other side. Sadly, the system seemed to mysteriously gain bouce the more I moved it until it would bounce over so much it would fly out of the simulation (pos = #inf) and then crash ODE.

I tried several other approaches using two wheels and the only one that seemed to work at all was to have three wheels -- two big ones in the front and a small balancing wheel in the back. The small wheel in the back would prevent the center block from colliding with the ground; this made the simulation much more stable. I also had to simulate the wheels not as cylinders but as spheres; many people on the ODE mailing lists suggested spheres work better for this application. But now I had a new problem: the robot could move forward and backward, but couldn't turn! For reasons beyond me I could not get ODE to simulate the friction that occurs when the wheels rotate in opposite directions, which should intuitively rotate the robot. It didn't. Instead the robot would just sit there frozen, and then jump up and fly out of the simulation to infinity, and crash. Sigh.

This week I scrapped the wheeled robot approach and I'm trying to build a robot that consists of three blocks with two hinge motors connected them. I'm having little success so far, but I think I can get it to work. I'm not handling collision detection between the blocks, whenever I try and simulate that they start bouncing wildly until the simulation crashes. Sigh. Sigh.

05.01.04 : The beginning of a new project...

Motion capture offers a quick solution to provide realistic human motion for animation applications. By recording the human body in motion, it can be ``played back'' by a computer to mimic the body that was recorded. Working with motion capture data however is cumbersome: transitioning between sequences, modifying the motion, and scaling the motion to a different-sized character are all difficult tasks.

A new area in computer animation that is beginning to become popular is interacting motion captured movement with physically simulated movement. ``Rag-doll physics'' used in many video games (Unreal Tournment, Half-Life, etc.) involve using motion capture for the ``living'' character animation and then transitioning to a physically simulated character when the character ``dies,'' to give a more life-like feel to the character's suffering when their health meter went below zero. Real-time back-and-forth transitioning between physically simulated movement and motion capture movement is an area the author is yet to see in computer animation, for example, transitioning to physically simulated movement every time the character takes damage, rather than only when they die. update: Michael Mandel is doing exactly this for his thesis at CMU.

A far more realistic approach to generating human character motion for computer animation would be to completely physically simulate all of the motion. Physical simulation of all character movement requires development of bones, joints, skin, muscles, and a ``virtual brain'' to accurately control the character. This approach has been tried with varying degrees of success by several groups over the last few years. Previous attempts have used genetic algorithms to evolve a neural network to control muscle movement. Other work has evolved even the creature itself.

For my project, I propose to evolve a bipedal articulated character that can walk. To develop this character I will create a dynamically sizable neural network to control the character muscles, described by an array of integers that will make up the chromosomes for genetic evolution. I will begin with a fixed-body creature (the body will not change between evolutions), but given time I would like to make the creature body itself evolving as in Sim's work. The character will live if a physically simulated environment using the Open Dynamics Engine.