Using Genetic Algorithms to Design and Control Self-Replicating Machines

This project is part of a larger one headed by Hod Lipson which is studying self-replicating machines and evolutionary robotics. This is one part of a an effort to design self-replicating mechanisms manually, automatically and to physically build the solutions.

My part of this effort used genetic algorithms to develop the morphology and command sequence of self-replicating machines. These machines are composed of cubes with electromagnets on each face and an axis of rotation along the diagonal, allowing the cubes to swivel. Two genetic algorithms were used: one to find a morphology capable of self-replicating and the other to determine the exact command sequence that will cause self-replication to occur. In both cases, the machines were modeled in a two dimensional space. To find a morphology, potential structures were evaluated based on our group’s mathematical model, that tries to fit a copy of the original machine within the area reachable by the end effectors. Once a morphology theoretically capable of self-replication was found, the second genetic algorithm was applied to find a command sequence that caused self-replication. A given command sequence was evaluated based on how well assembled the copy was when the commands were finished. At this time, more than 10 designs composed of 10 or fewer blocks were discovered that could theoretically self-replicate. I tried to find command sequences for three of those machines and was successful in two attempts while failing in the third. The overall success of this project indicates that genetic algorithms are an ideal tool for designing self-replicating machines. However, the mathematical model of self-replication developed by our group determines only upper bound on self-replicatability.