Course Project
Your project may be on essentially any topic related to the material in the course. The best project idea is one in which you are interested! Please feel free to propose your own idea, or adapt one of the following suggestions.
Logistics
- By Oct 28 - Email me (kautz@cs.washington.edu) a short project proposal, outlining what you intend to do, and your general approach. Come to office hours and/or make an an appointment to discuss and refine your idea.
- Nov 18 - Email me a short status report of how it is going. You should be well on your way by now.
- Dec 5 - Be prepared to present a 10 minute talk to the class about your project. Presentations will continue on the 7th.
- Dec 12 - Turn in hardcopy of your project write up to me via my departmental mailbox. Your work should be written up in the style of a research paper for a conference such as AAAI (but you do not need to format it with AAAI-style macros; by style I mean content, not formatting). The writeup should address:
- Motivation
- Approach
- Experiments
- Results
- Future directions
I will be picking up the projects from my mailbox the next morning (Dec 13).
Project Ideas
- Many classes of randomly generated problems exhibit a "phase transition" in problem hardness. For example, see:
- Generating Hard Satisfiability Problems. Selman, Bart; Mitchell, David; and Levesque, Hector. Artificial Intelligence, Vol. 81, 1996, 17--29.
- Problem Structure in the Presence of Perturbations. Carla Gomes and Bart Selman. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), New Providence, RI, 1997.
- Heavy-tails, Phase Transitions, and the Nature of Cutoff and Capacity. Carla Gomes, Xi Xie, Stephen Wicker, and Bart Selman. In Forney Festschrift, Kluwer, 2000.
Develop a random problem generator for Sudoku problems, and determine the parameter settings that lead to the hardest problems, independent of size. (One approach: start with a pre-exisiting Sudoku generator, and vary the output by erasing a percentage of the clues.) Determine if the hard region is sharply peaked (a first-order phase transition), or more gradual (a second-order phase transition). Consider also the distribution of individual problem hardness at the hardest parameter setting: are all "hard" problems equally hard, or if not, what is the shape of the distribution? Relate your observations to those made in the papers above.
- Create a variation of Walksat that outperforms it on some class of problems. (You may design the class of problems yourself.) Compare performance against walksat on a set of benchmarks, such as:
The following papers are recent examples of interesting improvements of Walksat:
- Evidence for Invariants in Local Search.David McAllester, Bart Selman, and Henry Kautz. Proc. AAAI-97, Providence, RI, 1997.
- Schuurmans, D. and Southey, F. (2001) Local search characteristics of incomplete SAT procedures. Artificial Intelligence 132(2), 121-150. aij01.pdf
- Backbone guided local search for maximum satisfiability, Proc. 18th Intern. Joint Conf. on AI (IJCAI-03), Acapulco, Mexico, Aug. 9-15, 2003, pages 1179-1184. [pdf file ][Software]
One approach that has seen little attention is a genetic algorithm variation (exchanging information between multiple search points).
- If you are into music and have a large collection of mp3's: build a program that generates high-quality playlists (better than random0, taking into account what kind of songs "go together" and are appropriate for different times of the day or activities.
- Create a heuristic search web crawler. Some web crawling software is available at http://www-2.cs.cmu.edu/~rcm/websphinx/ . Variations could include:
- Given two URL's, find a shortest path of links between them
- Given a topic, find pages related to that topic (without using an engine such as Google), keeping the ratio of relevent pages / pages visited as high as possible
- Given the names of any two people who have some "presence" on the web, determine interests they are likely to have in common. See the ReferralWeb project for an example of this.
- One of the first machine learning programs ever written (long before there was a field of machine learning) was a "mind-reading" program for the following game: on each trial you and the machine simultaneously type either 0 or 1. If they match, the machine wins, otherwise you win. The program wins by discovering subtle patterns in your attempt to type randomly. Research, recreate, and possible improve a version of such a mind-reading program. The original paper on this work is: D. Hagelbarger, "SEER, A SEquence Extrapolating Robot," I.R.E. Trans. Electronic Computers, vol. 5, pp. 1-7, 1956. Doing this well will involve a literature review on current techniques for sequential prediction tasks.
- Apply a local search algorithm to the problem of automatic generation of computer programs. For example, Donald Knuth's work on SortNet used genetic algorithms to find small circuits for sorting numbers.
- Build a Prolog natural language parsing system that could work as the front end to a computer game you enjoy. If the game is open-source or has an open API, try getting the parser to work with it in real time.
- Devise a theorem-proving system for some (small) subset of mathematics. The challenge would be to prove an open problem in algebra or mathematics in general. It's unlikely you would succeed in cracking a real open problem, but a course project would give you a better understanding of the issues and may put you on the path of solving an open problem in the future. See McCune's page for some background, and a view of search intensive theorem proving.
- Create a program that solves crossword puzzles given ordinary English language clues. See work by Michael Littman for an approach that was quite successful.
- Create a reinforcement learning system that learns to play a game by playing games against itself. (I recommend a game easier than Backgammon, however.)