Tuesday, May 29, 2007

Racing With Evolutionary Algorithms

There is an interesting comparison among different evolutionary algorithms on the control of three legged robots. From the paper abstract:


Building a three legged robot is an extremely challenging task. Since three legged walking is not yet common neither in nature nor in technology it is not a priori clear what a three legged walking gait should look like. The term paper compares several techniques to find feasible gaits, using different numerical optimization strategies including IDEA, CMA-ES and Lazy Learning. All calculations have been on a specifically developed mechanics model."

See here an animation of the racing of the four robots got by the evolutionary algorithms applied.

The evolutionary algorithms applied were:

1. CMA-ES (Covariance Matrix Adaptation Evolution Strategy).

2. IDEA (Iterated Density Estimation Evolutionary Algorithm, an EDA).

3. Random Search.

4. Lazy Learning.

We can clearly see that the CMA-ES outperformed the other three evolutionary algorithms. CMA-ES is a poweful evolutionary algorithm and uses very small populations - such as two or few individuals. It can deal with problems which exhibit some or all the following features:

01. Ill-conditioning.
02. Non-separability/Non-decomposability.
03. Noise.
04. Rotation (or transformations in general) of the coordinate system.
05. Multi-modality.
06. Non-smooth.

It is well known that genetic algorithms (and other approaches) have difficulty when dealing with problems that exhibit some (or all) of those features above.

There is another animation of a solution (robot) got by the CMA-ES, see here. Click here for a summary upon the subject.

Could CMA-ES also be applied to control much more complex robots? See below some speculations.

More than three legs!

A multi-legged robot roaming through a rocky environment:

Even Martians could use a CMA-ES to control their three legged robots!



Anonymous SoloGen said...

Hello! (:
How are you?! Long time, no see! (;

What about application of EC for adapting the modular robots? I really like to see results like that.

30 May, 2007 13:38  
Blogger Nosophorus said...

Hi, Amir!!!! :)

Where were you, friend!? It's a long time that we do not talk. :)

It's nice to see you again in the so-called Blogosphere! You should do some blogging too. :)

Yes! Evolutionary Computation (EC) could also be applied to control modular robots, despite the fact that this task is more complex (I suppose) than three legged walking, mainly if each module depends on what the others modules are doing. So, choosing a reasonable evolutionary algorithm should be made. So, let me ask you some questions upon adapting modular robots:

01. Are there so much dependencies among the parameters?

02. Is that a noisy task?

03. Is that a decomposable/separable problem?

04. What about multi-modality?

They are just interesting questions that can help us to understand the problem at hand.

I guess that CMA-ES would give us interesting results (even unachieved ones) if we applied it to the task you said.

There is already works upon modular robots and genetic algorithms:

Evolutionary Motion Synthesis for a Modular Robot Using Genetic Algorithm

More here, here, and here.

By the way, it's nice to see you again, Amir! :)

Let's blog! :)

Até Mais!


30 May, 2007 15:08  
Anonymous Anonymous said...

Do you believe a Learning Classifier System would be able to handle the walking task?

01 June, 2007 18:08  
Blogger Nosophorus said...


Well, I really do not know if a LCS could be applied to that kind of problem.

But, would be interesting to see it! :)

Até Mais!


02 June, 2007 05:24  
Anonymous SoloGen said...

Hi! (:

Yes, you are right! I was somehow busy, and also I was somehow lazy! I try not to be so anymore (at least for the "lazy" part).
Anyway, thanks for your answer.
I'm not a good person to answer your questions as I have not worked with those robots, but my answers would be:

01) Yes; joints are coupled.
02) Yes; it is a real-world robotic problem.
03) Probably not; maybe depends on the structure of the robot, e.g. is it a snake or is it a arm on a mobile platform?
04) Probably there are several global (and local) optima. Specially if we have redundancy in our design (which is the case in the snake robot).

03 June, 2007 15:06  
Anonymous viagra online said...

I have researched some about how to solve one of those Algorithms, but it is a bit complicated, sure it is!
I actually still don't get what are they used for. Is kind of confusing for me.

21 July, 2010 18:14  
Anonymous Viagra said...

This was a great explanation.

15 February, 2012 16:57  

Post a Comment

Links to this post:

Create a Link

<< Home

Charles Darwin Has A Posse Check Google Page Rank