OK, so I am reflecting my age with the song lyric that I chose for the title. For my first science blog post I have selected a story about genetic algorithms, which have been used by a research team at Cornell University’s Creative Machines Lab to create virtual robots. These computer-animated robots demonstrate various solutions to the problem of robotic walking. I chose this story in part because I am interested in genetic algorithms and their potential for finding unexpected solutions to engineering problems. But mostly I enjoyed the amusing video the researchers produced showing the robots. (More on the video in a moment.)

Genetic algorithms are biomimicry of a sort, at a very fundamental level. They use DNA, genetics, and evolution as the inspiration for a means to create computer code that models complicated engineering problems and arrives at  interesting solutions.

The diversity and complexity of solutions created by genetic algorithms–in a relatively small number of generations–is suggestive of the possibility that life on earth might have evolved by similar processes. It is hardly proof of evolution, though. Research in other fields provides much stronger evidence supporting the theory of evolution. Genetic algorithms are of interest primarily for their application to solving engineering problems.

In this case, the problem is that of making robots walk. Anyone who has followed the robotic rovers that NASA has developed, for exploring places like Mars, knows that robotic walking is complicated. Just getting them to move can be hard enough. Going over or around obstacles without flipping over or getting stuck is even harder.

The starting point for a genetic algorithm is a collection of entities, in this case robots, created with random configurations of components. Four types of components were used in these robots: hard tissue representing bone, soft tissue, and two types of  “muscle” tissues that either expand first and then contract, or contract and then expand. Each of these components is represented by cubic voxels that are arranged in various configurations in relation to each other.

Once the first generation is created, all of the robots are tested to identify which ones walk the best. The most important test of fitness is the distance a robot can travel, but penalties are also built in. A robot can be penalized for being made up of large numbers of voxels, representing an inefficient weight that requires more energy to carry. It can also be penalized for having too many muscle voxels, which consume higher amounts of energy. A penalty is also assessed for the number of voxels surrounding other voxels, because a solid mass with a lot of interconnected voxels has a lower surface area than a set with few adjoining connections. Such a configuration can reduce the effectiveness of cooling and cause them to overheat in a warm environment.

It is at this point when the genetic modeling comes into play. The highest-scoring robots are allowed to reproduce, but reproduction is not just creating copies. In a sort of numerical mating ritual, the most successful robots are paired off. Each has its genetic coding split at a random location and combined with the complementary string of the other. Multiple offspring are created in this way, each with a different random mash-up of the parents’ genetic codes. The idea is that some of the offspring will inherit the code segments that made their parents good walkers. Better still, some might inherit the code segments from both parents that made them successful. Typical genetic algorithms also have a built-in probability of occasionally introducing new random components, intended to be analogous to mutation.

The new generation is then put through the same set of tests.

The result, spanning 1000 generations, is portrayed in their video, http://www.youtube.com/watch?v=z9ptOeByLA4&feature=youtu.be.

Of course, these are computer animations, not real robots. In particular, they are built from unspecified “muscle” tissues that expand and contract by 20% cyclically. As far as I know, this sort of material does not exist, and the obstacles to creating such materials are among the factors that prevent engineers from building robots as agile and efficient as living creatures. (That’s just the sort of observation that is sure to bring about comments telling me how wrong I am.)

An intriguing aspect of genetic algorithms is that the best coding from one generation is passed on to some members of succeeding generations, without any need to examine the code along the way in order to identify what is good, or what characteristics of the code make it good. The only thing that matters is that the code produces effective walking. It is that approach that leads to unusual and counterintuitive solutions.

One aim for the Cornell researchers was to experiment with using several different types of tissues in each robot, with varying amounts of stiffness and built-in muscle-like activity. Genetic algorithms were first applied to robotic movement almost 20 years ago by Karl Sims, using rigid objects connected by hinges with varying degrees of freedom. Examples can be seen here: http://www.youtube.com/watch?v=bBt0imn77Zg. The unique approach in the Cornell team’s research was to obtain the flexibility from soft and “muscle” tissues instead of hinged connections.

Another interesting aspect of the Cornell research was that they challenged human engineers to come up with robotic designs using the same components. The engineers were unable to achieve results that were as successful as those reached by the genetic algorithms.

The paper, to be published in Proceedings of the Genetic and Evolutionary Computation Conference, can be downloaded here: http://jeffclune.com/publications/2013_Softbots_GECCO.pdf