CS81 Midterm Project

Due by 8am Friday, March 6 2009
Introduction

For the midterm project you will explore the NEAT model as described in the paper Competitive Coevolution through Evolutionary Complexification by Kenneth O. Stanley and Risto Miikkulainen. You will design an experiment, run the experiment, analyze the results, and write a paper to explain what you found. You are strongly encouraged to work with a partner on this project.

You are also expected to conduct a limited literature review. Find and read at least two articles that are related to your experiment. A good source of related work are the bibliographies of the papers we have been reading in class. If you are having trouble finding related work, please come see me.


Getting started

Because the evolutionary process is time consuming you will probably want to conduct your experiment in simulation. However, if you have an idea about how to effectively use a physical robot, you may try this as well. Whether you use a physical robot or a simulated robot, you will need to carefully consider the environment and the task. What actions and sensory information should be available to the robot? What is the robot's goal?

Once you decide on an appropriate environment and task, you'll need to encode the robot's goal in a fitness function. One possible experiment could be to compare the effectiveness of various styles of fitness functions. Is it better to have a specific fitness function that rewards particular behaviors or is it more effective to have a general fitness function that rewards outcomes without regard for how they are accomplished?

There are a number of parameters that are involved in using NEAT. It is not obvious how these should be set. Another possible experiment would be to compare the results obtained when varying particular key parameters. There are several parameters that you must set in the NEAT config file in order for your experiment to work properly. These are:

When conducting research, it is beneficial to work incrementally towards your ultimate goal. In other words, start with the simplest version of your idea that is likely to yield interesting results. If that works, then you can then add another level of complexity. This approach is more effective then beginning immediately with a very complex set up.


Project etiquette

Your NEAT experiments may require several hours to run. Please read the following suggestions for how to conduct your experiments so as not to disrupt the work of other students. Pay special attention to the use of nice and screen.

Recall that pyrobot communicates to both physical and simulated robots through ports. Only one program can use a particular port on a given machine. We may want to designate certain machines in the robot lab to be reserved for a given team. Then each team will have a computer where all the ports are available to them.


Format of the paper
Your paper should include the following:

Most computer scientists use a program called LaTeX to write research papers. I encourage you to give it a try. You can see an example of a LaTeX paper including bibliography and figures in /home/meeden/public/latex-example

It is a good idea to start writing the paper before your experiments are completed. You can begin with the introduction, related work, and bibliography without having results.

Your grade will not be based on whether or not your experiment succeeds. Negative results are also useful. Your grade will be based on the design and execution of the experiment as well as the thoroughness and readability of the paper. You do not turn in any programs. Email me a pdf version of your paper by the deadline.


Creating images for you paper

You can include the pictures generated by NEAT (showing average and best fitness across all generations, the best network architecture, and the speciation) within your paper. However, you must first convert them to postscript format. This can be done within the inkscape program.

You may want to save a screen shot of the simulator to include in your paper. Here's how to do it:

  1. Invoke the program xv in a terminal window, and then right click the mouse to get the program menu.
  2. From the menu, choose Grab. This will bring up another window. Choose Grab again, and then left click on the window you want to save an image of. A copy of the window will appear.
  3. From the menu, choose Save. Then from the Format menu, choose Postscript. Enter a file name, and choose Ok. The file is now saved and you can Quit the xv program.


Citing related work

The purpose of writing a research paper is to communicate your discoveries to others. It is important to explicitly acknowledge how your work relates to other work. This can be done either with a direct quotation from another source or by summarizing the key points from another source. You should avoid paraphrasing another source as this can border on plagiarism. When summarizing another source, explain the essential information in your own words.

When using the exact language from another source, you must use quotation marks. Or if you are using a passage that is more than four lines long, indent and single space the passage without quotation marks. For a direct quotation, provide a reference with a page number. When summarizing another source, you should also provide a reference, but a page number is not necessary.