Final Project

For the 473 final project you will investigate a topic in AI of your own choosing in some depth. The project will involve

Independent background reading. You should find and read at least one relevent paper on the topic of your project. The textbook has an excellent bibliography, and for more recent papers you can use Citeseer and Google.
Implementation and experiments.
A good writeup, that outlines the problem, your approach, the results of your approach, ideas for future work, and a bibliography.

You will create the final project in a team of two or three students.

Deadlines:

By Monday May 8th in class: Turn in a 1-paragraph project proposal that says what you will do. It should include the names of the team members..
By Wednesday May 31st in class: Turn in a hardcopy of your project writeup, and a printout of your implementation (double-sided, two columns per page).

In between these times you are encouraged to talk about your progress on the project with Prof. Kautz, Ravi, and/or the cse473-discuss mailing list.

How Projects Will Be Graded

Projects will be graded 65% on content and 35% on the write-up. They will be graded by Prof. Kautz, not the TA. A good project will:

Clearly describe the problem that is being solved.
Choose a reasonable method to attempt to solve the problem, and in the writeup justify the chosen approach.
Make a serious attempt to implement the method and solve the problem.
Take care in evaluating how well you solved (or failed to solve) problem. For example, if your method includes an element of chance, you should do enough experiments to be sure your results are statistically meaningful. If your method takes input parameters (for example, the parameters of a local search method), your experiments should try a range of different parameters values.
Present the results and a thoughtful discussion of the results in the writeup. Use graphs and charts effectively to display numeric results.
Include a conclusion section in the writeup that describes what you discovered and what other problems the project suggested would be interesting to investigate.
Include citations in your writeup as necessary to papers and books (physical or online) that you used in creating your project. This should include at least one source in addition to the textbook.

Note that is possible to get 100% on your project even if the approach you try does not work, as long as you made a solid effort and tried to understand why the approach was not a good one for the problem. However, if your system does not work because of programming bugs, or because you left it until the last minute and it was never finished, then you will, of course, be penalized.

The project will count for 20% of your final grade.

Project Ideas

The project ideas below are only suggestions. These suggestions are deliberately open-ended; there is no one right way to carry them out! You are encouraged to come up with other project ideas if you like.

New! In class we showed the traveling salesman genetic algorithm demo and said that it was unknown whether the crossover operator really gave any power over just using mutation. You could do a careful study to determine what is the best combination of crossover and mutation settings to solve TSP. To get meaningful conclusions you'll need to do thousands of runs, systematically varying the length of the run, the kinds of operations allowed, and the probabilities used for random mutations. Instead of doing this by hand, you'll want to take the source code for the TSP demo and write a program that directly calls its methods. To analyze the results, you'll want to normalize the fitness of the solution found in each run as a percentage of the optimal solution for that instance, and compute the mean, standard deviation, and median of the percent of optimal. Finally, you will also want to try several different problem size, for example, 100 cities, 1000 cities, and 10,000 cities. Create nice graphs summarizing what you discover.
New! Write a spam filter - a program that classifies email messages as spam or not spam. Here is a link to an assignment from a previous 473 class that describes how you might do this using a Naive Bayes classifier (you can read ahead on this in the textbook) and/or a neural network. Here are some slides on Bayesian learning that describe how a Naive Bayes classifier works.
Extend your Othello program in a significant way, such as by incorporating machine learning or creating a database of end games.
New! Write a program that plays any game. See the General Game Playing competition website for information and starter code.
Write a program that plays a game of incomplete information and/or chance. Test it against human players and other computer programs. Encourage another group of students to select the same game for their project, and hold a mini-tournament. Ideas:
- Battleship
- Poker
- Backgammon
- Monopoly
- Stratego
Write a forward-chaining heuristic search planner for deterministic domains that takes PDDL (planning domain definition language) input:
- The original 1998 version, PDDL 1.7: read this first.
- The 2002 version is called PDDL2.1, and contains many new features, mainly connected with adding time and objective functions to the language.
- The 2004 version is called PDDL2.2. It adds derived predicates and timed initial literals.
Start with the basic STRIPS subset of PDDL, and see how far you can go in handling conditional effects, defined predicates, metric resources, etc. Test you system on some of the problems from the AIPS plannng competitions.
STRIPS planning problems can be translated to Boolean satisfiability problems in CNF form using the approach described in this paper:
Encoding Plans in Propositional Logic Henry Kautz, David McAllester, and Bart Selman, Proc. KR-96.
Determine how actions that involve metric resources can be translated to satisfisfiability. Implement your approach by building a system for a specfic planning domain of your choice, that takes as input the initial and goal states, and number of time steps. For an even more challenging project, write a domain-independent translator that also takes as input the operator descriptions in PDDL.
This paper describes how a very simple neural network can recognize the emotional expression in photographs of human faces:

Dailey, M.N., Cottrell, G.W., & Adolphs, R. (2000), A six-unit network is all you need to discover happiness. In Proceedings of the 22nd Annual Cognitive Science Conference, Philadelphia, PA, pp. 101-106, Mahwah: Lawrence Erlbaum.

The output of a speech-recognition system can be improved if the system knows something about the topic being talked about - what words to expect, and what words commonly follow other words. Obtain a commercial or freeware speech recognition system, and build a post-processor that takes as input the output text of the speech recognizer, and outputs a "corrected" version of the text, for a particular topic of your choosing (e.g., sports, weather, movies, etc.).
Local search algorithms (walksat and gsat) are very good at solving some classes of satisfiability problems, such as random 3-CNF and encodings of graph coloring. Create your own local search algorithm - for example, a genetic algorithm, or an ant algorithm - and compare it against Walksat on some satisfiability problems. A good set of benchmark problems is SATLIB. You can download Walksat from here.
The following paper shows how a "portfolio" of algorithms for satisfiability testing can be made to outperform any one algorithm:

SATzilla: An Algorithm Portfolio for SAT. Nudelman, Devkar, Shoham, Leyton-Brown, Hoos. Presented at the Eighth International Symposium on Artificial Intelligence and Mathematics (AI+Math 2004).

Try a similar approach on some other interesting search problem.
Design and implement agents that learn or evolve to live successfully in a simulated world. For examples of simulated worlds, Google "artificial life" or "bots".