CS81 Lab2: Evolving neural network brains for robots

In this lab you will experiment with an evolutionary computation method called NEAT (Neuro Evolution of Augmenting Topologies) developed by Kenneth O. Stanley. NEAT operates on both the weights and the structure of the neural network, allowing connections and nodes to be added as potential mutations. We will be using a python package that implements NEAT.

• To begin, run update81 to copy some starting point files into the directory cs81/labs/2/.
• If at any point you are interested in seeing how NEAT has been implemented, the source code is available here:

  /usr/local/stow/cs81/lib/python2.6/site-packages/neat
  

In Lab 1 we used the back-propagation algorithm to learn the weights of a fixed architecture neural network. Now we can use NEAT to evolve both the weights and the architecture of a neural network. We will begin exploring NEAT by using XOR as a testbed.

• Go to your cs81/labs/2/xor/ directory and open the file evolveXOR.py in an editor. Notice at the top of this file that it imports a number of different classes from the neat package, including population, chromosome, genome, and nn (for neural network).
• The evolveXOR.py file loads a configuration file. Open this file, called xor_config, in an editor. This is where all of the parameters are set for the evolutionary run. You must define the number of input and output nodes in the neural network as well as the activation function that will be used. You must also determine the population size and a maximum fitness threshold that if reached will terminate evolution. There are many parameters that must be set for NEAT. If you are curious about particular parameters, refer back to the NEAT paper we read or go to the source code to see how they are used. A few key parameters are:
  • nn_activation: sets the activation function for neurons in the network. The choices are exp which is the standard sigmoid that outputs in the range [0, 1] or tanh that outputs in the range [-1,1].
  • feedforward: determines whether the connections in the network must be strictly feedforward or whether they are allowed to be recurrent.

• The user must define an appropriate fitness function for the problem being solved. In this case, fitness is defined in the eval_fitness function in the file evolveXOR.py. For each chromosome in the population, the chromosome is first translated into a feed-forward neural network. Then that network is tested on the four standard XOR patterns, and the total sum-squared error is calculated. Finally the error value is used to create a fitness value that increases as error decreases. You should always define your fitness function so that higher values equate with better solutions. Notice that because we are using a feedforward-style network that we instantiate the network using the method create_ffphenotype and we propagate the inputs through the network to get outputs using the method sactivate. Here the "s" stands for "serial".
• The line pop.epoch(...) is what starts a NEAT evolution. The first parameter specifies the maximum number of generations to run, which in this case is 30.
• Go to a terminal window and try solving the XOR problem:

  % python evolveXOR.py
  

  This will produce a number of messages detailing the progress of the evolutionary process. For each generation you will see the average fitness, best fitness, number of species, and information about each species. If evolution found a particular network that surpassed the maximum fitness threshold it will terminate early. Otherwise it will complete the entire 30 epochs.
• Executing evolveXOR.py will generate two files with a .svg extension. These can be viewed using xv:
  1. A graph of the average and best fitness over time: avg_fitness.svg
  2. A depiction of how the speciation changed over time: speciation.svg

  Look at these graphs. Note the best fitness achieved and in what generation it was found.

• Executing evolveXOR.py will generate files storing the chromosome of the best network from every generation of evolution. We can test out any one of these networks by doing the following and replacing n with the appropriate generation number:

  % python evaluateXOR.py best_chromo_n
  

This will print a description of the nodes, the connections, and the network's output (both the target values and actual output). Evaluate the best network found by NEAT. Look at how many nodes and connections the best network has. Sometimes these networks can be quite complex.
• Executing evaluateXOR.py will generate a file to help you visualize the network structure. To see a visualization of the network from generation n do:

  % xv phenotype_best_chromo_n.svg
  

  Look at the visualization of the best network's architecture.
• Try executing the XOR evolution several times. How variable are the results? Does the complexity of the resulting networks seem to match the difficulty of the problem? Back-propagation can easily find solutions to XOR with one hidden layer of two units. How do the NEAT architectures found for XOR compare to this?
• Try playing around with some of the parameters in the xor_config file. What happens if you decrease the population size or increase the probabilities of adding connections or adding units?

We know that neural networks can more easily learn linearly separable functions. XOR is an example of a function that is not linearly separable, while AND is an example of a function that is linearly separable. Let's see if NEAT can more easily find solutions to the AND problem.

• Creates files called evolveAND.py and evaluateAND.py that are based on the original XOR files. You'll just need to change the outputs used to evaluate fitness. You can use the original xor_config as is rather than creating an additional configuration file.

• Try evolving networks to solve AND. Does NEAT find solutions faster to AND than to XOR? Are the solutions found simpler for AND than for XOR?

The NEAT paper we are discussing this week uses a very time consuming fitness test intended to create a co-evolutionary arms race. We will experiment with a simpler scenario in this lab. Rather than a robot duel, we will focus on a single robot foraging for food. We will place the robot in a world with 10 randomly located lights, representing food, and allow it to explore and eat as long as it has energy to move. We will test the robot with three different random placements of the food. The network has three input units representing the left and right light sensor values as well as an energy warning value. As its energy level gets low the warning value increases. The network has two output units representing the motor speeds of the left and right wheels of a simulated Pioneer robot. The fitness value is based on the total number of steps the robot survives in the three trials.

• Go to the cs81/labs/2/energy/ directory and open the file energy_config. Notice that for this robot task that the feedforward parameter is now set to 0. We are going to allow recurrent networks to be formed. When using recurrent neural networks we will create them with the method create_phenotype and propagate them with the method pactivate where "p" stands for "parallel". Also notice that we are using tanh as the activation function so that we can have inputs and outputs in the range [-1,1].

• Now open the file evolveEnergy.py. This file is similar to the evolveXOR.py file, but has additional code to run the pyrobot simulator. Read through the next step, start the evolutionary process running, and then come back and look through this file.
• Go to a terminal window and start the evolution process running:

  % python evolveEnergy.py
  

  This program uses the pyrobot simulator, but does not display it in order to speed up the fitness evaluations. This will still take some time to complete. The evolution is set to run for just 11 generations, using a population of 20 individuals. A more reasonable test would be to use a larger population (at least 30-50 individuals) and more generations.

• As in the XOR problem, at the end of each generation the chromosome with the highest fitness will be saved in a file called best_chromo_n where n is the generation number. You can test these chromosomes while evolution is still running by doing:

  % python evaluateEnergy.py best_chromo_n log_file
  

  The second parameter is the name of a log file (of your choice) where details of the evaluation will be saved. Observe the behaviors of the best networks from each generation and look at the log files that are produced. Are robots from later generations able to survive longer than their predecessors? Does NEAT complexify the networks in order to achieve this increased rate of survival? What kinds of behaviors are developed?

There are many different ways of implementing a food foraging task. Each of the choices made in the above program could affect the types of behavior that resulted. Here are just some of the issues that must be considered:

• How should energy be handled?
  • How much initial energy should the robot be given?
  • How much energy should eating a piece of food provide?
  • How much food should be provided in the environment?
  • Should each step consume an equal amount of energy?
  • Should staying still consume less energy than moving?
  • Should moving quickly consume more energy than moving slowly?
• What sensors should be provided?
  • How should the robot's energy level be represented?
  • Should the robot be given range sensors for detecting walls?
  • How should the robot detect food? We could create virtual sensors that would give range and distance to the nearest food.
• How should fitness be measured?
  • Should networks be tested in random environments?
  • Should networks be tested in identical environments to ensure fair comparisons?
  • How many trials per fitness test are sufficient?
  • What should happen when the robot stalls during a run?
• How should the NEAT parameters be set?
  • Should more speciation be encouraged?
  • Should the probability of adding nodes or connections be changed?

Look carefully at the files given for this task and list each of the choices that were made for each issue given above.

Then in the directory cs81/labs/2/ modifiedTask create your own version of the food foraging task that makes some different choices. In the text file experimentalLog keep a record of the options you tried (even if they failed). Be sure to explain each idea you explored, how you tested its effectiveness (list key parameter settings such as population size, maximum number of generations, etc.), and the results.

For example, you might decide that testing each network in random environments is too noisy, and that a better test would be to use a fixed environment similar to the one in the robot duel. Re-write the code to do this, run it, and report on what happens.

When you are done run handin81 to turn in your completed lab work.