Here is the result after 43 generations. It follows the grandfather program (from generation 36) pretty closely. I can see mutants appear occasionally. I think they "look better" than grandfather#36. There is some "adjusting" on fitness values which now may not be appropriate. In addition the programs trees have grown to about 150 nodes, with ~120 calls to the servo in evaluating 1 program. The calls are not being processed because the ~120 calls to the servo make no relevant changes. They basically overrun the servo. I was thinking in modifying the program tree building functions so that there could be only 1 call to each servo (knee & hip). The actual values can be modified 120+ times, but it will only be 1 call to each servo.
Telefox and Rik mentioned the amount of "useless" material in DNA, but I think there is plenty diversity for the values of the servos versus the actual call to the servos. For example moveKnee( (x + 10) - 10) would still be possible or moveHip ((x + 0) - 1) + 1) , moveHip(x / x * x ) ... etc So, there is plenty of room to create garbage.
2010.12.27 - A few goofy things
Fitness Too Constrained
I came to the realization that the fitness factor is evaluating the points in exact order. But if the generated program created a movement which "matched" exactly but was rotated. For example, if the generated program created a movement where step 1 was at point 2, and step 2 was at point 3, step 4 was at point 1 - it would throw the solution out, even though as a cyclical movement it is perfect. Since there are 4 possible rotations, does this mean I'm throwing out 3/4 of the possible solutions?
Something is just plain wrong in the fitness evaluation - I believe I have goofed something up - I hand calculated some of the "Best of Breed" Programs and can see ones being rejected that are better values. Humbug, time to debug.
In Synch But Out of Whack
I have a locking mechanism in the system which will wait until the video frames can send two identical positioned captures. This is so an accurate reading can be taken of the LED's position.
I thought I was doing this
wait until image is stabilized by constantly comparing video feed
when image is stabilized continue processing
I think its still a good routine - the part I miss calculated was the fact that even though the program commands the servos to move the delay between when they are actually moving and when the servos get the command is enough time to snap 2 stable pictures.
I will add a delay before checking the video stream, to at least get the servos "moving"
2010.12.28 - Found goofy thing behind keyboard
I seemed to be getting erroneous results. A cycle through a generation was producing programs and I could see when "The Best" was selected. But when this "best individual" program was executed by itself, its result was not the same when it was peviously evaluated.
There was a nagging feeling I had previously regarding setting the servos to an initial state. It turned out the nagging feeling was correct. I stepped through the code, when a "Best" was selected which had a single knee move. That would mean the program was completely dependent on some previous individual setting the hip ! Ooops!
2010.12.29 - Summary
Genetic Programming is very appealing because of its organic design.
Unfortunately, I needed to slow the video capture / genetic processing loop down to 1 second per iteration. This was necessary to capture accurate positions of the LED. There are 4 points of evaluation in each Individual fitness test. It is also necessary to set an initial state, for each individual. This comes to 5 seconds per each evaluation. So if we would like to do 999 generations at 100 individuals each with 5 seconds per evaluation, the time involved would be nearly 6 days ! I don't have the patience. Although it was fun to walk away from the computer, and have it busily "crunching" possible solutions. But, the servo noise was quite annoying.
It is important with genetic programming the evaluation of each individual program happens very quickly, otherwise the time needed to create something useful becomes way too long.
Genetic programs working in simulations can work considerably faster, but at a possible cost of not modeling the real environment satisfactorily. Also, creating or interfacing with a simulator may not be worth the effort in some situations. Telefox, shared some links on a project which has done genetic programming/simulator integration. The Starfish robot uses a simulator to run through possible walking modes - here is an example.
The following images are the results of letting the program and feedback system process for 1/2 a day. Not spectacular, but not bad either. I now would like to try something with accelerometer feedback. The feedback system of the accelerometer should be considerably faster than the video system. Balancing should be challenging. The amount of time balanced should be part of the fitness program. I've been kicking around a few ideas but nothing concrete, and now i want to spend some time on WiiDar (wii LIDAR) since Santa gave me a blue-tooth dongle.
I would welcome feedback, or anyone wanting to experiment with a similar setup.
Series of screenshots from 30 generations of the GP trying to find a program
who's optimal solution was the yellow trapezoid. The red letters & red path represent the
current best. The grey text and grey path represent the current individual program