Assignments

The coursework includes:

• 4 written assignments, covering basic technical material. Some assignments will include running and evaluating experiments using software tools such as C4.5, Walksat, and JavaBayes.  See the Computing information page.
• A programming project, that will involve significant design, programming, evaluation, and write-up. You may choose one of the suggested projects or come up with your own idea. Projects may be done on your own or in teams of two. 

Written Assignments

• Assignment 1: Search, Planning, & Logic.  Due January 23rd.
• Assignment 2A: Bayesian Networks, Written Exercises.  Due January 30th.
• Assignment 2B: Bayesian Networks, Computer Exercise.  Due on February 6th.
• Assignment 3: Machine Learning, Computer Exercise.  Due on February 13th.

Project Timeline

• Jan 30 or earlier: Provide me an email or hardcopy project proposal. The proposal should contain five sections:
  1. A clear, concise description of what you plan to do,
  2. The general approach you'll use (e.g., heuristic search, learning, rules, belief networks)
  3. An explicit, coherent plan for quantitatively and/or qualitatively evaluating the system
  4. A time line for your implementation
  5. A preliminary bibliography. Check the textbooks and www.ResearchIndex.com for relevant literature.
  The proposal should not be more than about two pages in length. If you'd like a partner for the project and haven't found one, indicate this somewhere on the proposal.  I will provide feedback on your proposal, so you are encouraged to get your proposal to me as early as possible.
• Feb 13: Submit a one-page status report.
• Mar 6 or Mar 13: Present a 5 to 10 minute presentation of your project to the class.  See information on schedule about preparing this presentation.
• Mar 20:   See details below.  The report, about 8 to 10 pages long, will motivate the problem and your approach, describe the experiments and results, and relate the project to current literature.  If you have a personal web page you are encouraged to create a page with information about your project so that other people in the class and in later versions of this courage can learn about your project.  If you include the URL in your project write-up I will link the page to a permanent version of the course home page.

Turning in Projects

• Create a single archive file using either Winzip or gzipped tar (.zip or .tgz extension) containing your report (in .doc, .pdf, or .ps format), code, and any other material.  Important: your file should be named by your last (family) name.  If yours is a joint project include both last names separated by a hyphen.  Examples:
  

  jones.tgz
  smith-jones.zip

• Email the file as an attachment to to kautz@cs.washington.edu
• If your file cannot be emailed successfully because it is too large, you may submit it using either of the following methods:
  • Create a CD-ROM and mail it to me:
    

    Henry Kautz
    Dept Computer Science
    Box 352350
    University of Washington
    Seattle, WA 98195

  • Place your file on a public web or FTP site, and email me the exact URL needed to download the file.

Schedule of Student Presentations

• By noon on the day of presentation, students should email will@cs.washington.edu a short set of Powerpoints slides.  People who wish to present a demonstration must do so on the UW campus, we do not have the technical capability of sending laptop video from MSR to UW.

Possible Projects

More ideas - updated Jan 27th:

• Create a version of Walksat for multi-valued variables (not just Boolean variables).  If the domain of the variables is the set (R,G,B), then a clause could say something like "v1=R or v2=B".  Try out your system on encodings of some problems such as graph coloring, and/or other problems that naturally take this form.
• Build a really fast local-search algorithm specifically for quasigroup completion problems.  (I can supply you with a good backtracking solver for quasigroups so you can do speed/scaling comparisons.)
• Create a model-based diagnosis system (such as we described in class for the Deep Space One probe) for some device with which you are familar: say, your computer?
• Empirically compare the scaling properties of exact and approximate algorithms for Bayes nets, by (i) creating a family of Bayes nets of larger and larger size, and (ii) implementing or just downloading two or more different algorithms for inference.  For example, you might compare variable elimination (exact), junction tree (exact), and MCMC (approximate).  A huge collection of links to free Bayes net software is at http://www.ai.mit.edu/~murphyk/Software/bnsoft.html .  Can you come to some conclusions of circumstances under which each algorithm would be best?

The following are only suggestions.  You are encouraged to devise projects that relate to your work or experience. Many other projects are suggested in the exercises in the R&N textbook.

• 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.
• The International Conference on AI Planning (ICAPS) has a yearly competition for automated planners.  One problem with the results of such competitions is that planners that do well on one set of problems may do poorly on another.  In particular, A* type planners tend to do poorly on domains that require parallel actions and optimal (shortest) solutions.  Do a systematic study of several different state of the art planners, such as FF, IPP, and Blackbox, on variations of the Sokoban world, where the amount of parallelism can be controlled by having different numbers of Sokobans.
• AI planning is closely related to the problem of verifying hardware and software systems.  One kind of verification problem is to determine if a bad state (such as a deadlock) can be reached by a system for any sequence of inputs.  If we write operators that describe a system's operations and inputs as actions, then the problem comes a planning problem: is there a sequence of actions that reaches a goal (bad) state?  Choose a simple circuit or protocol to verify, encode the system with STRIPS operators, and use Blackbox or some other planner to find bugs.  For example, you might try a correct and buggy version of Peterson's mutual-exclusion algorithm.
• Implement intelligent virtual creatures in a virtual environment.  See IBM's java based robots http://robocode.alphaworks.ibm.com/home/home.html and Microsoft's .Net based robots: http://www.gotdotnet.com/terrarium/ .
• Prisoner's Dilemma.  In this multi-agent environment, one can explore levels of cooperation and deception between the inhabitants. The prisoner's dilemma setup has been studied in many different areas, such as economics, biology, sociology, and computer science. This surpisingly simple game provides interesting insights into the overall properties of highly complex system, e.g., our global economy.  Here is a description. Now, try it yourself.  As you can see, the basic setup is quite simpe. However, one can explore arbitrarily complicated strategies (involving learning and reasoning) in trying to win the game. Your team can build a multi-agent visual java setup to explore different classes of agents trying to outdo each other. If more than one team expresses interest in this project, we can have the teams compete (in friendly manner of course).
• 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.
• Use data-mining techniques to find correlations between the text in the New York Times online edition and the rise or fall of the major stock market indexes.
• 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.  
• Write a program to identify English characters from bitmaps. Various features are extracted from the bitmap, such as the Euler number (measure of how many holes in an object), centroid, and directional tendency. Then the 26 possible characters are ranked, under a rule that measure similarity of the observed features to features of canonical training examples.
• Build an expert system for a task you now perform manually using Bayesian networks.
• Create an implementation of the Winograd's famous SHRDLU system to work with sentences describing actions in the ``blocks world''. English commands are parsed by an ATN or chart parser. An interpreter module converts the parsed form into action commands. The actions are then carried out in a simulated environment.
• A computer bidding system for the game of bridge. Bridge, unlike chess, is a game of incomplete information, which makes standard game-tree search techniques unusable.
• 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.
• A program that generates automatic crossword puzzles, starting from a dictionary and an empty board.  For a bigger challenge, create a program that solves crossword puzzles given ordinary English language clues.  See work by Michael Littman for an approach.
• Recreate from its specifications the reinforcement learning (neural net) system (Tesauro, 1992) that learns to play backgammon by playing games against itself.