Evolving Robot Gait Through Simulated Evolution

Interesting story brought to me via my news webservice:

Students - And Robots - Learn In Professor´s Robotics Lab.

The genetic algorithm applied is the CGA - Cyclic Genetic Algorithm. Not to be confused with the cGA - Compact Genetic Algorithm, an EDA.

The main ideas behind CGA are the following:

Parker made modifications to the standard genetic algorithm to invent the cyclic genetic algorithm (CGA), a method by which cycles of behavior can be learned. The CGA is a method where the computer can self-generate code. In real life, this means that a robot who encounters mud, for instance, might adapt with a different gait. A robot that loses a leg could learn to walk without it.

To demonstrate, Parker changed the parameters on the computer to tell one robot that it was suddenly carrying a heavy load. The robot took on a new walk - slow, deliberate and heavy on stability. In further tests, he showed how the CGA could adapt the robot control codes for partial and full loss of one or two of its legs. "The original CGA method was very limited because it couldn´t react to sensory input," Parker said.

More formaly it can be put as:

"Cyclic Genetic Algorithms were developed to allow for the representation of a cycle of actions in the chromosome. They differ from the standard GA in that the chromosome is in the form of a circle with two tails. The tails of the CGA chromosome are provided to allow for pre and post-cycle procedures. They provide a means for completing tasks before and after entering the cycle. For gait sequence generation, the pre-cycle can position the legs in a ready to walk posture and the post-cycle can return the robot to a stable at rest posture. In our application, we used only the pre-cycle tail. TheCGA genes can be one of several possibilities. They can be as simple as normal genes that represent traits of the individual or they can be as complicated as cyclic sub-chromosomes that can be trained separately by a CGA. For our purposes, the genes represent tasks that are to be completed in a set amount of time. The trained chromosome will contain the cycle of primitive instructions that will be continually repeated by our robot's simple controller to produce a gait.

CGAs can have both fixed and variable length chromosomes. In either case, the system must be able to allot the proper number of tasks to each phase and be flexible enough to allow the CGA to form a complete cycle. When fixed length are used, the tasks at each gene can be repeated. The number of repetitions is encoded in the gene. In this way, fixed length chromosomes can take on the desirable characteristics of variable yet maintain the increased control of training fixed.