You are going to reproduce an experiment first conducted at Harvard University in 1968. This assignment is a bit different from the other homework assignments in this class because there are no specifica- tion bundles for this. You either make it work or you don't. You are going to study the effects of evolution on a population of robots. The robots need to maneuver around a grid collecting energy. The robots must collect more energy than they expend to survive. Your robots will maneuver around a 10 x 10 grid looking for batteries. A battery gives the robot five more power. Moving a square costs 1 power. The sensors are always on and cost no power. Robots have five power when they first emerge on the map.
The key is the robot behavior. Each robot has a collection of di- rection sensors and a motor. Robot success depends upon the map between these two elements. We do not hard code the map between the sensor data and the motor actions, however. The robots start with a random mapping, but over time, the mappings evolve into successful strategies. We'll get to how they do this in a minute.
The robot has four sensors - each facing in a different direction. This way, the robot can detect what is in the squares adjacent to the North, South, East, and West. Each map feature will generate a different code for that sensor. See figure 1 for four examples. The codes you see here are examples, you can use whatever codes you wish.
Figure 1: Example of sensor readings with various obstacles on the map. see image.
Robot sensor states:
Each robot will have 16 genes. Each gene is an array containing five codes. See figure 2 of a single gene. The first four codes correspond to possible sensor states. The last code instructs the robot what to do in the event the current sensor state matches the four states on the gene.
Figure 2: Example of an individual robot gene. see image.
Robot actions:
This means that every turn the robot is comparing the current sensor state with it's genetic code in an attempt to find a match. A gene must match exactly for its behavior to be executed. If it does not find an exact match, the robot will execute the last gene (number 16). Robots will continue to do this until they run out of energy. KEEP TRACK OF THE NUMBER OF TURNS A ROBOT SURVIVES. This will become very important later. A robot gains energy running into a square containing a battery. The battery is consumed in the process. Figure 3 is an example of 1 robot turn.
Figure 3: Example of a robot moving along the map for 1 turn. see image.
Randomly place each robot on a spot on the map. Populate 40% of the squares with batteries. Generate a new map for each robot. We run one robot through at a time. Moving each square consumes 1 energy unit - even if it's not a valid move (a wall). Invalid moves consume energy, but keep the robot on the original square. This is usually the death knell for that robot unless the move action was move in a random direction.
You don't need to display the map on the console. Its interesting to watch if you want to do so, however. Perhaps display the map of the best performing robot or the worst performing one.
Evolution works on populations, not individuals. You need a population of robots to run through your maps. Create a population of 200 randomly generated robots to start. That is, you randomly generate the mappings between allowable behaviors and sensor codes for the first generate of robots only. Each robot is run through a random map and the number of turns they survive is recorded.
Once all the robots in a population have had a turn (and acquired energy scores), record the total energy harvested by the entire generation and breed your robots. Sort your population by energy harvested and kill off the lowest 50%. Then pair up the top 2 robots and produce 2 children by combining genes from both parents. The children enter the gene pool with the parents in the next round. Then, breed the 3rd and 4th highest scoring robots. Repeat until all the parent robots have reproduced. Keep the number of robots at a fixed number for the entire simulation. Genes are randomly created for the first population only - the robots breed after that.
Each parent supplies 50% of the 16 genes for a child. The simplest way is for one parent to supply the first 8 and the other to supply the last 8. You will not want the siblings to have the same genes (unless you are investigating the effects of identical twins). However, you can use a different swap scheme if you would like.
Swapping genes is a tricky business and mistakes happen. In 5% of the individual genes swapping there is an error - a mutation. Randomly change one character on the gene the child has inherited from it's parent. Just generate another value and insert that value over the old one. You can also shift all genes down 1 and the 16th gene moves to the top.
The degree to which the robot successfully harvests energy from the environment is called 'fitness. We measure that by the total amount of power harvested when each individual robots time ends. When we finish with the entire population of 200, we calculate an average fitness score for the population. Save the average fitness for each generation. You will most likely see slow and steady improvement over time - evolution at work. When the simulation completes, print out the average fitness scores on the console. This is even more effective if you are able to draw a console graph (not a requirement).
The fascinating thing about this experiment is your robots will get better and better at navigating the map over time. They will evolve strategies dealing with walls and corners. The most exciting part is it doesn't require any further participation from you - just set it in motion and watch it go.
No bonus features are needed with this assignment. However, past students have: