Answers.Body: <p>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:</p>
  
  <pre><code>exit
  \/
  [0,0,0,1]
  [0,1,1,0]
  [0,1,1,1]
  [0,0,0,0]
        /\ 
        enter
  </code></pre>
  
  <p>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.</p>
  
  <p>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'. </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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. </p>
  
  <p>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.  </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-15T10:05:49.477Z
Answers.Text: 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.
Answers.UserDisplayName: Gabriele
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-15T10:13:11.217Z
Answers.Text: Additionally, what should the robot do if it steps into a space that has a 1 in it?
Answers.UserDisplayName: Gabriele
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-15T16:26:16.427Z
Answers.Text: 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"
Answers.UserDisplayName: Andrew Butler
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-18T08:32:05.543Z
Answers.Text: @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.
Answers.UserDisplayName: Philip
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-13T13:21:30.123Z
Answers.LastActivityDate: 2018-04-13T13:56:59.293Z
Answers.LastEditDate: 2018-04-13T13:56:59.293Z
Answers.UserDisplayName: Philip
Body: <p>I have been reading quite a few papers, on genetic programming and its applications, in particular, chapter 10 of  &quot;Genetic Programming: An Introduction and Tutorial, with a Survey of Techniques and Applications&quot; (Langdon, Poli, McPhee, Koza; 2008)   Unfortunately, I can not wrap my head around how one could apply genetic programming to robotics, for example, in <em>path planning</em>.</p>
  <p>Can anyone explain this in the most simple manner? I know that it all depends on the fitness function.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-13T18:17:41.230Z
Comments.Text: 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.
Comments.UserDisplayName: Andrew Butler
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-15T10:08:44.650Z
Comments.Text: @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.
Comments.UserDisplayName: Gabriele
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-15T16:24:48.057Z
Comments.Text: 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.
Comments.UserDisplayName: Andrew Butler
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-14T12:08:28.237Z
Comments.Text: The link to the PDF file is broken.
Comments.UserDisplayName: Flux
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-19T22:35:37.347Z
Comments.Text: @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?
Comments.UserDisplayName: DukeZhou
Tags: <applications><evolutionary-algorithms><robotics><genetic-programming><path-planning>
Title: How can genetic programming be used for path planning?
UserDisplayName: Gabriele
ThreadText: # How can genetic programming be used for path planning?
  
  (Asked by: username_0 on 2018-04-11)
  
  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.
  
  **Tags:** applications, evolutionary-algorithms, robotics, genetic-programming, path-planning
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @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.  
  > **username_1**: 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.  
  > **username_2**: The link to the PDF file is broken.  
  > **username_3**: @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?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2018-04-13. Score: 6 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: Additionally, what should the robot do if it steps into a space that has a 1 in it?  
  > **username_1**: 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"  
  > **username_4**: @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.  
  
  ---
  
  