CS81 Lab4: Novelty Search

In this lab you will implement novelty search, introduced by Joel Lehman and Kenneth O. Stanley, and combine it with NEAT to conduct an evolutionary search based on a novelty metric rather than an objective fitness function. Lehman and Stanley argue that objective fitness functions can be deceptive, leading the evolutionary search to local maxima rather than towards the goal. In contrast, novelty search ignores the objective and simply searches for novel behavior, and therefore cannot be deceived.

Do an update81 to ge the starting point files for this lab.

Before trying to implement novelty search, review the details of the algorithm on pages 12-14 of the paper Abandoning objectives: Evolution through the search for novelty alone.

In the file noveltySearch.py, create a python class called Novelty. Implement the following methods:

• __init__(self, k, threshold, limit)
  Novelty search stores an archive of examples from the behavior space. It bases the novelty metric on the k-nearest neighbors from that archive. Create class variables to store the archive as an initially empty list, the k to be used in calculating nearest neighbors, the threshold for how novel an example has to be before it will be added the archive, and the limit for the maximum size of the archive.
• distance(self, p1, p2)
  Returns the distance between points p1 and p2 which are assumed to be lists or tuples of equal length. To calculate distance, sum up the squared differences between each component of the points. Return the square root of this sum. This method should work for points of any length.
• distFromkNearest(self, p)
  Returns the distance of a point p from its k-nearest neighbors in the archive. The simplest, though very inefficient, way to implement this is to calculate the distance of p from every point in the archive, sort these distances, and then sum up and return the first k (which will be the closest).
• sparseness(self, p)
  Returns the sparseness of the given point p as defined by equation 1 on page 13 of the paper. Recall that sparseness is a measure of how unique this point is relative to the archive of saved examples. Use the method distFromkNearest as a helper in calculating this value.
• addToArchive(self, p, sparseness)
  If the size of the archive is less than the limit, then always add the point p. Otherwise, when the archive is full, check if the given sparseness of point p is greater than the threshold. If so, add this point and also remove the oldest point in the archive.
• saveArchive(self, filename)
  This method saves the entire archive to the given filename. Write each point on a single line in the file, with spaces separating each value.

• In the main program at the bottom of the file noveltySearch, create an instance of your Novelty class with a k of 10, a threshold of 0.3, and a limit of 100.
• Use a for loop to generate 1000 random 2d points, where each value is in the range [0.0, 0.3], and add them to the archive.
• Use another for loop to generate 1000 random 2d points, where each value is in the range [0.0, 1.0], and add them to the archive.
• After both loops, save the archive to a file called test.dat.
• At the end of the main program print the sparseness of several points:
  • Point (0.5, 0.5) should have a low sparseness since it is at the center of the range of random points you generated.
  • Point (1, 1) should have a higher sparseness since it is at the boundary of random points you generated.
  • Point (2, 2) should have an even higher sparseness since it is outside the range of random points you generated.
  • Point (5, 5) should have the highest sparseness since it is far outside the range of random points you generated.
• Run your program and ensure that the sparseness values match these expectations.
• Graph the points that were saved from the archive by doing:

  % xgraph -P -nl test.dat
  

  The P flag makes each point large, and the nl flag indicates that there should be no lines drawn between the points.
• Run your program a number of times, changing the threshold of the novelty search.
  • Use 0.0 to allow any point to be added to the archive.
  • Use 0.2 to only moderately test the novelty of points that are added.
  • Use 0.3 to have a more stringest level of novelty for points.
  • Finally try 0.4.
  Look at the graph of the test.dat file after each run. How does the graph change?
• Run your program a number of times, this time keeping the threshold fixed at 0.3, while varying k. Again look at the graph at the end. How does changing k affect the results?

• Open the file neatXOR.py. This is almost identical to the file evolveXOR.py from last week. The main difference is that the eval_fitness function includes an if at the end to check for when a solution has been found. It then sets the fitness for that chromosome to a high enough value to trigger the max_fitness_threshold ending the evolution. It also saves the network that solved XOR in a file called neat_chromo.
• We will compare standard NEAT to novelty search combined with NEAT for solving XOR. Let's test standard NEAT first. Run the program neatXOR.py 10 times and save the results in the file experimentsXOR. Record the generation in which a solution was found or 70 (the maximum number of generations) if not found. Also record the complexity of the solution, which is printed in the form: (number of hidden nodes, number of connections), at the end of each run. You can use the program evaluateXOR.py to test any of the neat_chromo solution files. You can use xv to look at any of the avg_fitness.svg plots that are produced. Notice that when using standard NEAT both the average and best fitness tend to increase over the course of evolution.
• Copy the file neatXOR.py to a file called noveltyXOR.py. Edit the noveltyXOR.py file as follows:
  • Import your novelty search code.
  • Create an instance of your Novelty class that uses a k of 10, a threshold of 0.3, and a limit of 150.
  • Re-write the function eval_fitness so that it produces a novelty metric rather than an objective measure. In order to do this we need to create a representation of the behavior. For XOR this will be a 4d point containing the output produced by the network on each of the four inputs. For each chromosome in the population, create this point, calculate its sparseness, add it to the archive of novelty search, and then set the fitness of the chromosome to the spareness. Continue to calculate the error and use it to determine when a solution has been found. Save the solution in a file called novelty_chromo.
  • After the call to pop.epoch(...), save the archive from novelty search into a file called archive.dat.
• Before doing experiments with the novelty version, test it to see if it is giving reasonable results. It should find a solution most of the time. Use the program evaluateXOR.py to test a few solutions. Also look at the file archive.dat to see if it contains a reasonable variety of example behavior. Once you are conviced it is working, you are reading to run experiments.
• Run the program noveltyXOR.py 10 times and record the same information as for the previous experiments. Look at some of the solutions produced as well as the plots of average and best fitness. Notice that in the fitness plots, novelty search does not display the same trend of increasing fitness values over time.
• At the bottom of the file experimentsXOR compare the results. Which method finds solutions more consistently? Which method finds solutions more quickly? Which method finds less complex solutions? Is the XOR problem better suited for objective-based or novelty-based search, why?

Before trying to implement maze traversal, read through the details of the maze experiment that Lehman and Stanley conducted on pages 14-16 of their paper Abandoning objectives: Evolution through the search for novelty alone.

• They used a robot with 6 range sensors for detecting obstacles and 4 radar sensors for detecting the goal location. Rather than trying to replicate this experiment exactly we can use the existing framework of pyrobot to create a similar experiment. The goal location can be marked with a light. The robot can be equipped with sonar sensors to detect obstacles and light sensors to detect the goal.
• There is a series of maze-like worlds that already exist in pyrobot called: LightBehindWall, LightInCorral, LightBehindCorral, LightEnclosed, and LightInMaze that could be used as a testbed for maze traversal. These are located in /usr/local/pyrobot/plugins/worlds/Pyrobot/. You are also welcome to create your own maze worlds.
• Using the files evolveEnergy.py and evaluateEnergy.py from last week's lab as models, create files called neatMaze.py and evaluateMaze.py. In the file neatMaze.py create a standard objective fitness function based on the formula given at the bottom of page 15. Remember that you can use the pyrobot commands setPos to position the robot at the start of a trial and getPos to find the robot's position at the end of the trial. Look at the parameter settings in the appendix of the paper to determine how to configure NEAT. Test this program. Based on the results presented in the paper, we would expect that this would only very rarely solve a maze.
• Copy the file neatMaze.py to a file called noveltyMaze.py. Modify the fitness function so that it is now a novelty metric based on the robot's end point at the end of a trial. Look at the appendix of the paper to determine how to configure novelty search. Test this program. Based on the results presented in the paper, we would expect that this would find a solution to the maze almost every time.

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