3
$\begingroup$

I have been reading quite a few papers, on genetic programming and its applications, in particular, chapter 10 of "Genetic Programming: An Introduction and Tutorial, with a Survey of Techniques and Applications" (Langdon, Poli, McPhee, Koza; 2008) Unfortunately, I can not wrap my head around how one could apply genetic programming to robotics, for example, in path planning.

Can anyone explain this in the most simple manner? I know that it all depends on the fitness function.

Improve this question
$\endgroup$
5
  • $\begingroup$ You generally don't use genetic algorithms for things that have to be done real time. Like in Phillip's answer you would have to set up and run through the maze tens of thousands of times before seeing any relevant results. This is expensive both in terms of both time and money. Generally, this is why you don't see GA in robotics. $\endgroup$
    – Andrew Butler
    Commented Apr 13, 2018 at 18:17
  • 1
    $\begingroup$ @AndrewButler so what if I simulated the environment (to my best knowledge) a million times and then threw my robot in the real world problem, would it end up failing the task miserably? I imagine just like in neural networks, the model would be saved for the robot to use in real world. $\endgroup$
    – Gabriele
    Commented Apr 15, 2018 at 10:08
  • $\begingroup$ No, you've got it. This is exactly how it is done. Notice, however, that your simulated environment may not be perfect and so your resulting model won't be accounting for certain things. $\endgroup$
    – Andrew Butler
    Commented Apr 15, 2018 at 16:24
  • 1
    $\begingroup$ The link to the PDF file is broken. $\endgroup$
    – Flux
    Commented Apr 14, 2021 at 12:08
  • $\begingroup$ @Gabriele The links to this paper broke, and I couldn't find a free PDF, so changed to a simple citation. Is Chapter 10 in the paper the correct chapter? $\endgroup$
    – DukeZhou
    Commented Apr 19, 2021 at 22:35

1 Answer 1

Reset to default
6
$\begingroup$

Take a robot that we want to be able to move from the bottom right corner to the top left corner of a 4x4 matrix full of random holes it should avoid. With holes represented by 1s, it could look something like:

exit
\/
[0,0,0,1]
[0,1,1,0]
[0,1,1,1]
[0,0,0,0]
      /\ 
      enter

As we want it to get to an exit from a start, we have a natural fitness function: closeness to exit door in smallest number of moves.

The genetic programming approach to solving this is to create random computer programs (the second chapter of your link does a pretty good intro to the tree like nature of this process) and let them loose. The vast majority of these strategies will be/are utterly terrible, things like 'go right once' or 'go left ten times'.

Say we make 100 random programs on our first run. We firstly score them on how well they did according to our fitness function (the random programs that did the best). We take a set % of these to survive and get rid of the rest, lets say 10% survive.

We take these surviving 10% of the best performing programs and use them to create new programs for the next generation by modifying them randomly again, but not completely. Say we randomly modify half their structure and leave the other half as is across however many we want for the next generation. We now let this generation loose again, and again rank, score, take the top 10% and breed a new generation from them and so on for n number of generations.

In this case, if we say left the grid as is, the program would generally come up with a rule roughly like 'go left x4, go up x4) as it solves this problem in the easiest way, but if we were to say, continuously randomise the position of 1s in the grid during this evolutionary process, we will force the program to come up with much more generalisable rules, such as checking the cells it can move into for 1s and not moving into any space containing a 1 etc.

Thus we can build a program with a flexible strategy able to cope with different environments for our robot in terms of number/configuration of holes - much more useful than having to program it for every configuration.

Just like with regular evolution, over millions of trials of taking the top performers and modifying them slightly, these programs become very specialised and high performing, able to solve highly complex games, paths with highly complex features etc.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Could you give an example of a fitness function in your example? Choosing the fitness functions is the part that boggles my mind the most. $\endgroup$
    – Gabriele
    Commented Apr 15, 2018 at 10:05
  • $\begingroup$ Additionally, what should the robot do if it steps into a space that has a 1 in it? $\endgroup$
    – Gabriele
    Commented Apr 15, 2018 at 10:13
  • 1
    $\begingroup$ In this answer he says "As we want it to get to an exit from a start, we have a natural fitness function: closeness to the exit door in the smallest number of moves" $\endgroup$
    – Andrew Butler
    Commented Apr 15, 2018 at 16:26
  • 2
    $\begingroup$ @Gabriele The fitness function here could be pretty simple: Just sum number of moves taken and number of squares away from exit (with a zero for this half of the score if they make it there), lowest scores are fittest. Robots that hit a space with a 1 in would be scored with a highly punitive 'death score' (say +1000 or more in this example) that puts them straight to the bottom of the fitness scoring every generation. $\endgroup$
    – Philip
    Commented Apr 18, 2018 at 8:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .