Results

For the simple bipedal model (legs and torso, but no arms), walking behavior, such as seen in this animation (DivX or QuickTime) has been found by the 600th generation in all of the twenty or so runs so far.

These runs were with 512 individuals, with each individual evaluated twice, since randomness in the physical and neural simulation can effect the fitness. A generation on an 2GHz Athlon takes between 15 to 30 seconds (longer as fitness improves).

Unexpected Outcomes

Occasionally, the controllers sometimes evolved toward behaviors that achieved a good fitness quickly, but had limited ability to grow. With the "muscles" too strong, one such local minimum is seen in this animation (DivX, 93KB) of standing-jump behavior. Note that the evolved behavior here manages a jump of about 3.3m, which is around the gold-medal range for Olympic standing-long jumpers.

Motivation

Bipedal locomotion is an interesting problem from two perspectives. First of all, it is a difficult problem that can help evaluate new techniques in machine learning, augmenting other, often easier, problems, such as pole-balancing. Further, biomemetic approaches, such as evolving CPGs, have been known to work, and so a biologically-based benchmark has been established. Thus, bipdeal locomotion is tough enough to be interesting, while being easy enough to be solvable.

The second perspective is one of utility. Millions of dollars have been invested in more traditional approachs towards getting life-like walking behavior from robots (e.g., Honda has invested over $100 million on the ASIMO alone). Realistic and robust walking, especially over difficult terrain, is a useful problem to solve.

Potential Application

One pontential application I'm interested in is creating one-the-fly physically-based motion for characters in computer games and virtual realities. The current approach of blending separate pre-generated animations is limited in expressiveness and flexibility. If one could generate physically-accurate controllers that were adaptable to the environment, one could substantially improve the believablity of the character.

Theory

Currently, ELSE uses the NEAT (NeuroEvolution of Augmented Topologies) algorithm developed by Kenneth Stanley at University of Texas at Austin. I'm working on a reinforcement learning technique derived from Echo State Networks, by Herbert Jaeger from Fraunhofer Institute for Autonomous Intelligent Systems. Although this is a somewhat different domain than the usual application of Echo State Network theory, I believe two factors make ESNs appropriate. First of all, the solution domain is known to be cyclical, as highly-recurrent CPGs are found both in biology and in successful ANN solutions. Second, relying on the symmetry of the morphology allows a drastic reduction in the number of outputs required. This leads to the possibility of reasonable reinforcement learning (via evolution) times by reducing the search space. The success of the Evolved ESN approach can be measured by comparing it to the NEAT algorithm on identical morphology.