Learning to walk with a genetic algorithm

Inspired by some artificial life papers, I implemented a genetic algorithm to evolve locomotion skills in virtual creatures with deformable bodies. Despite using a somewhat simple model, some interesting behaviors emerged.

The body

Many projects about simulated evolution of virtual creatures use rigid parts connected with joints for the creatures’ bodies. In these models, movement is achieved by applying torques at the degrees of freedom of each joint.

Rigid parts connected with joints are a good abstraction of the structures that nature has produced after many years of evolution like bones and muscles, but I wanted to experiment with more basic building blocks. In my model, the building blocks are deformable triangles and movement is achieved by contracting the edges of a triangle. I refer to the edges as the creature’s muscles. In the video above, a highlighted edge is a contracted muscle.

The brain

The brain that controls the muscles is very simple. In fact, some people wouldn’t even call it a brain. I just find it convenient to make a distinction between the deformable body and the algorithm that controls it.

The brain contracts each muscle with a fixed frequency. Although it’s a simple mechanism, different combinations of frequencies can produce interesting locomotion patterns. I see it as a very primitive brain with only one input (time) that, with a simple function parameterized by a frequency, gets converted into several outputs that control the muscles of the creature.

The genome

Each creature has a genome that encodes the frequency at which every edge of the body contracts. In other words, the genome encodes the brain of the creature. The body doesn’t change during evolution, but the brain gets better (locomotion-wise) each generation.

The algorithm starts with a population of creatures with random genomes and lets them walk for a short time to see which genomes are better suited for locomotion. The best adapted creatures are chosen for reproduction and via a process of chromosomal crossover and eventual random mutations, new creatures are born. The less fit creatures are discarded from the population, leaving us with a new population of expectedly better adapted creatures. This process is repeated many times until it converges to a solution.