Wednesday, October 22, 2003

On Genetic Methods of Robot Design

In class today, we discussed the general method of solving problems using genetic algorithms which are loosely derived from the concept of natural selection in evolution. The idea is that you create a population of "genes" which serve as the basic building block in which you operate. These genes are interpreted in some way to attempt to solve a problem. Then you apply a fitness function to evaluate how well it solved the problem. Based on the fitness value, you apply a selection process for the fittest of your population of genes, do cross-over operations and mutations akin to the natural process of reproduction, and create a new generation of genes to form solutions. Then repeat ad infinitum.

One of the general drawbacks to this approach is that we have a very poor understanding of the dynamics of the system. There are lots of attempts to produce directed evolution to converge on a solution, but the fundamental drawback is that you must describe how the genes are interpreted to represent a solution, devise a suitable fitness function to weed out the underperforming solutions, do parameter tuning to balance your reproduction and mutation rates, and provide lots of computational resources and time.

That last one is a huge drawback. Natural evolution has operated on the order of millions of years and it has only produced sub-optimal solutions (humans, flora and fauna) to the problem of survival. Consumption of resources is also a big problem since if you want to find useable solutions in a reasonable amount of time, you want to have very large populations. If you want these solutions to work in the physical world, you need to provide physical resources in which to test it.

We mainly looked at these problems with respect to their applications to robotics. There have been stunning successes in the application of genetic methods to purely software worlds, but these don't transfer very well to physically realized systems such as robotics. So the question is, how can we model the real-world closely enough so we can evolve our robotic systems in simulation, or how can we closely couple the physical world and marshall the resources necessary to evolve physical solutions that are guaranteed to be a) applicable to the real world and b) tractible in time and cost.

The former may be more practical but the latter is more interesting. The basic idea is that you are simultaneously producing mechanical designs with sets of actuators and sensors and the control system that drives it in its interactions with the world. Then you are applying a fitness function on it to determine its level of "goodness" and mixing it with other solutions to come up with similar but different candidates that hopefully extend whatever general strategy that the parents had devised.

The question is, how far do you go in the allowed variance of the physical design and how do you facilitate the rapid fabrication and testing during the evolution of many generations of solutions?

One of the key features of artificial designs is that they require a huge industrial infrastructure to be produced. You need manufacturing plants, special materials and the factories to produce them, harvest of natural resources, swarms of engineers and factory workers, sophisticated operation methodologies, information management, etc. Can you really line these up in a row and start tweaking the parameters to come up with different materials, different designs, unique applications of existing technologies, and unforseen optimizations in production?

What would be really neat is to come up with a "backyard industrial complex" in which you can control and tweak the whole process from basic materials to final design and somehow integrate this into an automatic guess-and-check system to facilitate computational genetic methods to come up with new and interesting solutions to a posed task. Perhaps this could be made a little easier by restricting ourselves to reusable parts that can be assembled and disassembled without the costly waste of resources. Something akin to Legos would suffice, but we'd still need a way to assemble the test design rapidly enough to make the process worth doing.

Just thinking out loud here.

To see some previous research relevant to genetic methods in robotics, see Karl Sims or Jordan Pollack.

Jacob Everist


Post a Comment

<< Home