Genetic Evolution of a Neural Network Driven Robot

Posted by: @robotbuilder

↑

I am just a casual observer.

My bad @robotbuilder I thought that you had a long standing interest in Neural Networks.

Tom

Posted by: @thrandell

↑

Posted by: @robotbuilder

↑

I am just a casual observer.

My bad @robotbuilder I thought that you had a long standing interest in Neural Networks.

Tom

I have had a long standing interest in AI in general since my teens and all things like that which includes the self organizing properties of systems which is what evolution amounts to including swarm behaviors.  Neural networks have evolved over time and I have tried to at least keep up some kind of understanding of the latest developments.

The neural net is only part of your project which is also about using genetic algorithms to evolve a set of working weights. There has also been work on evolving the networks themselves.

In fact I was somewhat shaken by inq's tirade and dislike so I stepped away from his project and I think you are both working on the same thing?

Reverse engineering a neural net's solution isn't easy although with the simple two neuron's I think your project is using I had thought about it. I spent some weeks doing simulations of the project. I can't really talk about all my thoughts as apparently that is being "negative" to the person's current project so I will shut up.

I am now just a casual and silent observer of what you are doing to see what you come up with 🙂

John

In trying to reproduce the Floreano-Mondada experiment my metric has always been looking for an upward trend in the fitness graph after running 30 generations.  I figured that if I could get somewhat consistent results at 30 generations then I’d spend the time to run it up to 100 generations a few times.  So far this hasn’t happened for me.  I decided to go back to 

Floreano, D. and Mattiussi, C. (2008) Bio-Inspired Artificial Intelligence: Theories, Methods, and Technologies.  MIT Press, Cambridge, MA.

and look for some ideas in the chapter on Evolutionary Systems.  What I found was a way to evaluate the effectiveness of crossover and advise on exploring the search space from the perspective of the evolutionary operators.  Here are two methods that I decided to try.

1. At the generation level, display the average and maximum fitness for those individuals with crossover and those without.
2. Look for an improvement in fitness of a given magnitude after applying the mutation operator and count the number of steps necessary to obtain the improvement.

To do this I needed to add yet another log file to my robot’s micro SD card.  This new log contains all the details of each individual for all generations.  I’m a guy with a hammer so when I see analysis like this I use a database.  Since I have Postgres installed on my laptop that’s what I used.  The first query was pretty straight forward.

From this bit of the report it looks like crossover is not helping.

The second method turned into a multi step sequence with a couple of temp tables.  For this metic I limited the number of generations to four to get an idea of what I’m looking at.  I’ll need to punch it out to maybe 10 generations to answer the question.  I found it easier to start with the highest generation and work backwards following the two parents and their two parents and their two parents…

The delta columns in this report are the difference between the starting fitness value and the fitness of descendants at each generation.  

Rowid 10 is interesting.  It started with the highest fitness value, had two descendants, and after four generations the fitness value of one descendant was unchanged and the other changed by -0.01.

I’ve played around with a few ways to implement mutation so I’m hoping that the second method will help me understand how they move over the search space.

Tom

Posted by: @thrandell

↑

In trying to reproduce the Floreano-Mondada experiment my metric has always been looking for an upward trend in the fitness graph after running 30 generations.

I'm assuming you're using this one from your O.P. (ACAA) - https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/82611/1/eth-8405-01.pdf ... but not sure. 

Posted by: @thrandell

↑

At the generation level, display the average and maximum fitness for those individuals with crossover and those without.

I'm not sure I'm understanding the nuance here... doesn't every mating have a crossover?  I'm did mine based on the Goldberg book you suggested and everyone has crossover.  I used a standard Goldberg algorithm as laid-out in ACAA...

I started evolving the methodology and algorithm based on what I was seeing in the results. 

(1) Uniqueness

Early on, I found the plain Goldberg algorithm would thrash around and get a too in-bred generation.  In fact, it became clear that most life runs to 100 generations were just re-using the same in-bred genomes over an over.  I implemented a way to insure I don't re-evaluate a Genome that has already occurred.  As soon as I assured uniqueness this became evident.  Here is a run illustrating this.  The list at the lower left shows the uniqueness being enforced.  Every generation reproduces repeats.  It uses Goldberg's "Roulette Wheel" for parent selection.  For any pair that creates a non-unique child, the same two parents reproduce again.  If they reproduce non-unique children 100 times in a row, they're thrown out and two more parents are selected.  This example run shows in generation 95, to get 80 unique children, 372 non-unique children were created and one pair did it 100 times and were replaced.  This also shows the highest Genome was found in Generation 33. 

(2) Natural Gene Selection

The second thing I tried was to replace the One Point Crossover way of producing children.  I tried something more like what I learned in high school Biology.  At each Allele location, I randomly select one from one of the parents.  This seemed to reduce the number of non-unique and covers more of the spectrum of possible permutations, but it didn't seem to improve the best genome.  Basically, I see this as increasing the diversity of the genomes.  It really seems to work similarly to using a high percentage for the mutate chance... as the second ACAA paper.

(3) Refinement of the Fitness Function

Noting that most of the Genomes got into making circles without any real interaction with walls, I played around with changing the fitness function.  Whereas ACAA was using:

fitness = V * (1 - sqrt(dv)) * s;

I eventually (trial and error) settled on emphasizing strait-line performance by:

fitness = V * (1 - pow(dv, 0.2)) * s;

(4) Bias

Noting how the behavior of a Genome seems way to linear and set in its way, I thought some change to the ANN was in order.  ACAA uses a single matrix multiplication for their calculation:

{2 motor speed outputs} = [2 x 10 Genome matrix] * {10 sensor and motor speed inputs}

I added a bias like is more commonly used in the back-substitution ANN's I've read about, so:

{2 motor speed outputs} = [2 x 10 Genome matrix] * {10 sensor and motor speed inputs} + {2 biases}

This gives a Genome of 22 floats instead of 20.

At first, these two changes didn't seem to make that much difference.  At least there was some actual strait line in the beginning.  This one has the best fitness of all generations:  Gen=27, fitness=0.322. 

This is when I started reviewing more of the "best of each generation".  I was hoping to see some trends as the generations passed by.  I really didn't any trends of improvement.  And then in the same run... I see this one at Gen=15 and only a fitness of 0.312.  This is more what I want to see behavior wise, but it eventually goes extinct because of higher fitness Genomes.  This triggered the thought that what about other Genomes in the same generation not having as high as the best of each generation, but is a more desirable behavior.  

At this point, I'm haven't come up with a solution that is only a function of what the bot can sense at the given instant.  I did implement a post processing step to as least weed out the 80 x 100 Genomes in an evolution.  It merely scores a bot's speed around a set of milestones.  In this example, the "pylons" it has to go around are near the 4 corners.  So a bot that squarely goes around the course in one lap would beat a faster one diagonally all over the place, but still reaching the extremities.  This strategy is not bulletproof either.  In this same evolution, running this post processing step, the fastest bot finally ran into a wall... after completing the course in a convoluted manner.

Note in the lower left output, it shows the results of any of the 8000 genomes that (1) completes the course, it gives its fitness, maximum speed and time to complete the course.  This one crashes epically at 21 seconds!  Which leads me to have to manually review the best of the best.  Which on this evolution run was way back at Generation 9 and with a lousy fitness score of 0.2193!

Summary

I'm coming to a conclusion (so far) that this base Goldberg biology with a simple matrix or matrix with bias, is about at its maximum ability for a simple course like this box or even ACAA arena.  Although the last sample above avoids obstacles (walls or obstructions inside) and runs pretty fast, it has a very strong left turn bias.  Here, I force the same Genome to start where it really needs to turn right.

Overall, watching probably hundreds evolutions, I don't really see refinement of a good Genome into a better Genome.  Its more like throwing darts.  Watching the bot's actions and the data trends, I'm feeling that I might want to tinker with the Roulette Wheel for parent selection.  Most of the time, the fitness spread is not very large.  Therefore the best Genome of a generation might only be getting a 5% higher chance of being picked than the worst.  IOW, it isn't getting that much more attention that is deserves to reproduce.  Thinking (now) maybe using some exponential distribution on the Roulette Wheel might show more trends fruit.

Another aspect was brought up when you posted that second paper of https://www.researchgate.net/publication/5589226_Evolution_of_Homing_Navigation_in_a_Real_Mobile_Robot in my InqEgg thread.  With its simplification of the fitness function, yet solved a far more complex problem based solely on a couple of more sensors on the bot and using a Discrete-Time Recurrent Neural Network.  That's something to pull on.

Hope some of these trends and some brainstorming along the way might help.  

VBR,

Inq

Although I haven’t found that nice upward trending fitness graph yet, I have found a few ‘keepers’ along the way.  I put together a graph of the neural network weights for one of them, but I think I should review the neural network that I used first.  So please pay attention because there will be a quiz 😉

The output neurons in this network calculate a value based on the sum of the weighted inputs.  That value is then converted into a motor speed for each wheel.  So for example, every 300ms the robot reads the 8 distance sensors, these inputs are each multiplied by a weight and summed together by the output neurons.  The output neurons have a bias input with a value of 1, so the bias weight is also added to the sum.  In this case the network is a recurrent neural network because it has a short term memory of the previously calculated output neuron values.  Those inputs are also multiplied by a weight and summed by the output neurons.  Clear as mud?

So I took the weights that the Genetic Algorithm created for one of my ‘keepers’ and added them to a figure that looks more like the robot’s sensor layout.

In the figure the Sensors are numbered, the Recurrent neurons are red, and the output neuron Bias is light blue.  The weights from the Genetic Algorithm are all shown.  The robot uses a differential drive and has 6 sensors on one side and 2 sensors on the other.

Quiz time:  Can you tell from looking at the weights in the figure which direction the robot travels in the maze?

Hint #1: the front of the robot is the side with the 6 sensors.

Hint  #2: with a differential drive if the right motor has a +50 speed and the left motor has a -50 speed the robot will spin madly in place in a counter-clockwise direction.

How did you do?

Tom

Hi @inq

I have to admit that I’m somewhat lost as to where you have taken your work on evolving an autonomous robot.  You wrote your own GA instead of using Goldberg’s?  You wrote the simulator that you are using now?  

I’m not sure how I can apply your observations but I do appreciate your feedback and sharing your experiences.

Posted by: @inq

↑

I'm not sure I'm understanding the nuance here... doesn't every mating have a crossover?  I'm did mine based on the Goldberg book you suggested and everyone has crossover.

So here is my C version of Goldberg’s two functions: crossover() and mutation() from his book page 348 figure C.6

/ Re: Figure C.6 page 348

allele mutation(allele alleleval, float pmutation, uint32_t *nmutation, uint8_t *count) {
// Mutate an allele w/ pmutation, count number of mutations
  allele result;
  bool mutate;

  mutate = flip(pmutation);  // flip the biased coin
  if (mutate) {
    *nmutation += 1;
    *count += 1;
    result = !alleleval;
  }
  else
    result = alleleval;
  return result;
}

void crossover(chromosome parent1, chromosome parent2, chromosome child1, chromosome child2, uint8_t *count1, uint8_t *count2,
            uint8_t lchrom, uint16_t *ncross, uint32_t *nmutation, uint16_t *jcross, float pcross, float pmutation) {
// Cross 2 parent strings, place in 2 child strings

  if (flip(pcross)) {           // Do crossover with p(cross)
    *jcross = rnd(1, lchrom-1); // Cross between 1 and lchrom - 1
    *ncross += 1;               // Increment crossover counter
  }
  else {                        // Otherwise set cross site to force mutation
    *jcross = lchrom;
  }
  //  The Original, I added the count parameters
  // First exchange, 1 to 1 and 2 to 2
  for (uint8_t j=1; j<=*jcross; j++) {
    child1[j] = mutation(parent1[j], pmutation, nmutation, count1);
    child2[j] = mutation(parent2[j], pmutation, nmutation, count2);
  }
  // Second exchange, 1 to 2 and 2 to 1
  if (*jcross != lchrom) {
    for (uint8_t j=*jcross+1; j<=lchrom; j++) {
      child1[j] = mutation(parent2[j], pmutation, nmutation, count1);
      child2[j] = mutation(parent1[j], pmutation, nmutation, count2);
    }
  }
  return;
}

Check out the two for loops.  If the probability of a crossover (pcross) is true then a random allele is selected as the crossover point, if the probability is false then no crossover, just potentially a mutation or two… Right?

Tom

Posted by: @thrandell

↑

I have to admit that I’m somewhat lost as to where you have taken your work on evolving an autonomous robot.  You wrote your own GA instead of using Goldberg’s?  You wrote the simulator that you are using now?

The simulator - yes.  For the GA, it depends on your definition of "your own".  Yes I wrote it, but strictly speaking, I wouldn't claim it as an original work of mine.  It is entirely based on the English to C++/C# translation of Goldberg... not the Pascal to C++/C# translation.  I wanted to understand conceptually what was going on instead of translating code and potentially incorporating a bug.  For instance, I took Goldberg (p.12) written word. 

I don't see how I could have interpreted his words in any other way and it says that a crossover always happens.  I translated into C# as:

private void OnePointCrossover(double[] child1, double[] child2, 
    double[] parent1, double[] parent2)
{
    int crossOver = RND.Next((Int32)_genomeSize);
    // Before Crossover Location
    for (int i = 0; i < crossOver; i++)
    {
        child1[i] = parent1[i];
        child2[i] = parent2[i];
    }
    // After Crossover Location
    for (int i = crossOver; i < _genomeSize; i++)
    {
        child1[i] = parent2[i];
        child2[i] = parent1[i];
    }
}

From reading Goldberg, even back in 1989, he offered many interpretations/implementations by... himself and other researchers for the algorithm.  The fact that your and my algorithms can't be compared in a one-to-one manner doesn't negate that trends of any Genetic Algorithm are relatable.  You've obviously had great success with your bot navigating the ACAA arena.  I think that's fantastic.  

I'm curious about what your GA has found.  If you take that same genome of your video going CW and set the start position so that the bot is "seeing" open road facing a CCW preference, does it move as smoothly around in a CCW direction or does it eventually do a 180 and go CW?  

VBR,

Inq

Posted by: @thrandell

↑

 

I remember you proposed using a video camera to track behavior, but how can I correlate that to the neural activations?  Any other ideas?

This was a struggle of mine also.  I felt in my gut finding and tuning the algorithm was dependent on watching the bot going through the motions and generations and "eventually" I might theorize what I could change to improve things.  The unfortunate truth to that is I'd either have to watch it all live or watch a video of it.  In either case real time is a problem.  This is why I finally decided I had to bite the bullet and do the simulator.  During an Evolution, I store all 80,000 Genomes that are evaluated and I can go back to any Genome and at any time step and see it's pose and neural activations.  I can also watch the evolutionary progress at a greatly accelerated rate ~50x.  

But to do it in the real world, real time, you need to know the bot's pose in the arena.  Quantifying that from a video frame would be a hefty project in its own right.  I don't recall seeing a design summary of your bot... did you decide to do the GA on the bot or via a PC and the umbilical?  If you're doing the GA on the PC, then my suggestion would be to:

• hook up a webcam
• Attach it directly over the top, center, square and plumb (to keep the trigonometry simple)
• Put two LED's of top of the Bot, say... front and back, on the centerline.  Two different primary colors would be best, say... Red and Green.
• Don't know if the arena color might be too bright, you might have to spray paint it black. 🤔 

At 300ms between steps should be plenty of time for your PC based data acquisition program to also grab a frame from your webcam.  It should be pretty simple for the program to scan the pixels for a pixel with the brightest Red and Green components.  A little transformation and you could add a location, orientation columns to your data acquisition.  You could also store the image for your human interpretations.  

Just a thought.

VBR,

Inq

Continuing the thought... As long as Goldberg's Pascal code does what his English chapters say, then I'm strictly Goldberg.  Now how the program itself has evolved with me trying things... in example, I added a choice to use NaturalBiology as I understand it from high-school level Biology classes... oh... 50 years ago... 

It just seemed the OnePointCrossover() function concept was not in keeping with the Biology evolution that I learned nor did it have any Mathematical advantage.  I tried this function.

 private void InqMate(double[] child1, double[] child2, 
    double[] parent1, double[] parent2)
 {
     for (int i=0; i<_genomeSize; i++)
     {
         child1[i] = RND.Next(2) == 1 ? parent1[i] : parent2[i];
         child2[i] = RND.Next(2) == 1 ? parent1[i] : parent2[i];
     }
 }

I can't say it is any better.  It did not suddenly start converging, but it did reduce the number of repeated Genomes generated relative to OnePointCrossover.  However, upping the Mutation reduces the number of duplicates also.  

@thrandell 

Quiz time: Can you tell from looking at the weights in the figure which direction the robot travels in the maze?

So what it the answer?

By direction I assume you mean clockwise or anti-clockwise around the center wall?

Questions as an observer of your posts:

What happens if you remove the center wall and run the bot using the same weights that produced the example in your utube post?

@thrandell 

I remember you proposed using a video camera to track behavior, but how can I correlate that to the neural activations?

The weights can only evolve to maximize the fitness function not make you happy with the solutions. So if the fitness function was "don't hit anything" then spinning around in circles would be a win!

The only reason to leave a track (which could be a pen on the robot drawing on a sheet of paper on the floor) is to see exactly what is happening. For example the robot may appear to be going around the same track again and again but on closer examination it might in fact be drifting. This happens in my sim bot and that can actually lead to a dramatic change as the small variations add up over time.

In the example below it happily travelled around the center wall again and again and then after many many many circles it suddenly did a wobbly and changed to what was probably an even more stable state. Although it would have looked like it was taking the same path in a video the thick black line shows it was drifting.

To enlarge an image, right click image and choose Open link in new window.

Well, I’m still chasing the the “good enough” genetic algorithm parameters.  This one turned out a bit less brittle then the others so I thought that I’d post a short video of it here.

Tom

@thrandell 

Have to admire your perseverance and patience in trying to evolve the best set of weights for this simple brain.

Posted by: @inq

↑

I'm curious about what your GA has found.  If you take that same genome of your video going CW and set the start position so that the bot is "seeing" open road facing a CCW preference, does it move as smoothly around in a CCW direction or does it eventually do a 180 and go CW?

@inq this second video was for you. 

I have never found an individual that would navigate around the arena in either direction.  They all have a preference for one direction.  When started facing in the opposite direction some would move forward until they hit a wall, some would just slow down until they came to a stop and a few would make a 180 degree turn like this one.

Of course after I stated that I never found an evolved controller that could travel in either direction I find one!  So if I head the robot to the left it travels counter clockwise and if I start it facing right it travel clockwise.  It doesn’t seem to have a reverse because if I start it facing a corner it just heads straight into the corner.  

Here are the network weights, for what it's worth.

Tom