8 bits are enough to be evolved!

Hi! This is my first blog post, then i'm going to introduce myself.

My name is Flavio Ansovini, i live in Genova (IT) and i'm working at the University of Genova. My interest is focused around the digital electronics and everithing related to it (.. means almost everything ;) ).

The title of the post is strictly related to a project that i've developed in this days.. which is about a robot able to learn how to walk... in some ways he get evolved :)

Something like this was in my mind for long.. but until now it didn't have the chance/time to bring it to life. I've decided to spend my time to build it with the excuse to test a Microchip Pickit3 debug express board, wich embed an 8bit microchip's microcontroller crystall less .

As i said, the final goal is to give the ability to the robot to learn and find out the better way to move in a specific direction. To do that, i've used a genetic algorithm embedded in the microcontroller.

 Well.. here i have to say that sincerly i'm not expert on GA, but it's an interesting topic to me and i've just studied it on few books... i also wanted to try it out in the real world. If someone more expert then me about GA, want to help to improve my algorithm i'll be happy and thankful :)

Now i'm going to explain shortly how the GA works:

First of all the robot is three legged (is spider like...) and every leg can be moved only up or down.

The GA is based on 15 genes for chromosome, wich contain all the information about one step.

Every step consist on the movement of the three legs (in any sequence/speed) and every leg has to be launched and called back. Every leg has a speed, start point, end point and a place in the sequence. To permit every combination of movement , the step has been divided in 6 time steps, 3 for the laucnch and 3 for the call back.. so.. the legs can move all toghether, sequentially or in any other configuration.

All this information are included in every chromosome. The first generation is made of 10 chromosomes and it's totally random.

The GA work like this:

-generate the first generation (10 random chromosomes)

-execute the generation and give a value of goodness to every chromosome (aka fitness)

The fitness is calculated using an accelerometer, integrating the x acc in something similar to the speed. This means that the fitness is better if x speed is higer. The problem with the accelerometer is that if the chip is not orthogonal to the ground you will get also a part of the g acceleration added. I've solved it using the angular position of every leg.. the rest is trigonometry..

This value is very important and delicate, if the fitness is wrong the GA is not going to work at all.

-when every chromosome has the fitness value associated, the generation will be ordered

-then the chromosomes are coupled 2 by 2, the head of the father with the tail of the mother and vice versa.

-the worst chromosomes are mutated. The the position of every gene and the number of the genes to be mutated (with a random number) are related to the fitness value.

At this point a new generation has been created..

The routine loops for a fixed number of generations, otherwise can loop until a specific fitness value is reached, but you must know wich is a reasonable value to reach...

When the learning routine is over, the best chromosome is selected and saved to the eeprom and the learning is done!!

I hope that this explanation is understandable...

To better explain what i've done, i've loaded a video on youtube..

In the video there is the explanation and i've also recorded the robot at work!!
In first there is the learning and then the execution of the selected chromosome. I think it's really funny!!

If you liked it please leave a comment, i'll be happy to reply.

Flavio