Automatic design of Lego NXT robots

Building Lego NXT according to your imagination is lots of fun, but to figure out some really cool stuff is not easy. I was wondering whether there are some ways to automatically design Lego robots (in this blog entry I only concern about hardware) like those windows screen saver generating random forms of artificial life. After some research I found no one has done it yet. However, there are already lots of resources which maybe already enough for a group of very talented people to figure out how to design a Lego robot automatically. I will summarize what I have found in the following.

Background

I think the most promising way to automatically design a Lego robots is to follow the nature, namely using evolutionary mechanism. One uses Genetic Algorithm (GA) to search for a design fit to the need. This field of study is called "Evolving Hardware" or "Evolvable Hardware" (EHW).  This field is still in its preliminary stage. There are now two major directions in this field. The first one is evolvable electronics, which can be either digital or analog circus.   For digital circus, one can first design on a computer  using GA then test it with FPGA or build the evolutionary mechanism directly on the FPGA which can then achieve some adaptive advantage. Search "FPGA" with "Evolvable Hardware" on Google if you want to know about it. For analog circus there are fewer research though I think its also  a very promising direction. Here is a group in NASA who are doing this kind of research.

Another direction of EHW research is the evolutionary machines (objects). It is generally easier to simulate and test electronics than machines, therefore much fewer research can be found in this direction. The Golem project at Cornell is probably one of the most earliest systematic try. A successful story to design antenna using GA can be found here. To automatically design a Lego NXT robots lyes in this direction.

Outline

I don't think I can make an automatic design of NXT work by myself. It needs lots of work and has a high risk to be not accomplished after years of dedicated work.  However, I still list what I will do if I work on this project here. When I find more people I might start it.

Step 1 Map the Lego NXT robot's structure to a DNA like one dimensional representation

Probably one can label different types of the basic Lego building blocks with different id and parameters. I should choose a way of mapping so that the code itself could reflect the actual similarity and difference of the bricks. For example in the Lego NXT kit there are bars with different geometry, length and different types of holes. Let's say we have 4 bars. They are:

No.1 Straight bar with 4 round holes.

No.2 Straight bar with 3 round hole in a row and the last hole is a "+" hole. (If you have a Lego NXT, you know what I mean.)

No.3 Straight bar with 5 round holes.

No.4 L shape bar with one arm like No.2 and the seconde arm is a round hole.

If I name them as "A", "B", "C", "D", both computer and people know nothing about the relation between them. That's a bad code.  A better way to call them is to use these names:

BARoooo

BARooox

BARooooo

BARolooox

BAR is the name of the type. I think to use 3 capital letter for the type of bricks is a good option so you have enough variations to go beyond Lego NXT bricks.

I can either give each bar a unique code like "A" for a straight bar with length 4 holes one it and "B" a straight  bar with 5 holes on it or better call them "BAR4" and "BAR5"

(to be continued)