Semester Project
Select an area of artificial intelligence that interests you, and write a program to solve a problem in that area. The project you choose should be limited enough that you can write the program in one semester. You may write the program in any language, to run on any computer; the only restriction is that the program must run on either a computer at the university or a computer that can be brought to the university, so that the program can be demonstrated at the end of the semester.
You may work in a team of up to 3 people on your project.
Suggested topics include:
Since some of these topics will be covered late in the semester, you will need to read ahead in the textbook when choosing a topic and designing a solution.
10 points extra credit on the project will be awarded to anyone who presents his or her AI project at the 2007 STEM symposium .
There are four deadlines for the project:
- February 21: Project proposal due
This should be a one-page description of the project you plan to undertake. In your proposal, state:
I will return the proposal with comments indicating whether I think the project is too hard, too easy, or about right for a semester project, and whether I think the language and general approach you have chosen are appropriate for your project.
- The problem you will be solving.
- The programming language you intend to use.
- The platform your program will run on.
- The type of user interface your program will have (text? graphical? web-based? etc.).
- The general approach you plan to take (A*? Minimax? A rule-based production system with backward chaining? etc.) including the major data structures.
- Some details about your proposed solution to the problem.
For a game-playing or puzzle-solving system:
- How will you represent the game or puzzle states -- the board (if any), the cards (if any), the positions of pieces, etc?
- How will a move be represented?
- Give 2 or 3 heuristics that you think would work well in your game or puzzle. (These may change later, as you develop the program, but I want your thoughts at this point.)
For a natural language system:
- How will you represent the syntax of acceptable input sentences or questions?
- How will you represent the semantics (meaning) of the input sentences or questions?
- What actions do you want the computer to carry out in response to the input? (Possible examples include: 1) Respond to queries, based on a database of knowledge. 2) Update an internal database or semantic net, based on information in the input sentence. 3) Carry out a robotic command. 4) Reply with the equivalent UNIX shell command.)
For a genetic algorithm:
- What data structure will you use to represent an individual in the population?
- What data structure will you use to represent the entire population?
- What fitness function do you plan to use? (This may change later, as you develop the program, but I want your thoughts at this point.)
- How will mutations occur?
- How will crossover occur?
For other kinds of projects:
The details will vary with the specific kind of project you have chosen, but you should include a level of detail comparable to that described above.If you wish to begin your project early, you may submit a proposal earlier than February 19; I will return the proposal with comments a few days after I receive it, so that you may begin work.
- March 21: Project draft due
Turn in a listing of the program so far, along with any external documentation you have written. At this stage, your program should be at least halfway completed. The program will probably contain some function stubs or other incomplete sections at this point; this is acceptable. However, all existing code should exhibit good style: mnemonic variable names, proper indentation, and good program comments. Make sure that, either in the program comments or in external documentation, you explain clearly what your overall approach to the problem is. I will comment on your general approach and programming style, and I will try to point out any upcoming pitfalls that I see in the program development.
Your program documentation should clearly indicate the author(s) of each portion of the code. For teams of 2 or 3 people, I expect to see indications in the documentation that each team member has contributed significantly to the code. (If you have borrowed any code from a textbook or web source, clearly indicate this in the documentation also.)
Also turn in the 2-3 page paper summarizing your project, as described in the Project due section below. You may revise this paper between now and the due date, but it should be largely complete at this point.
- April 16: Project due
Turn in:
- A listing of the program on paper.
- An e-mailed file (or files) containing the program. Include any data files that your program uses.
- A brief paper (2-3 pages) describing the problem your program solves, the problem-solving approach you selected, the basic design of your program, and any extensions or improvements you would like to make to the program if you had more time and resources.
- April 16-18: Project presentations
Give a 10-minute presentation in class describing your project. Tell the class:
- What problem you were solving
- What approach you took
- What successes you achieved
- What difficulties you encountered
- What you learned along the way
All projects must be demonstrated for the instructor during the last 3 weeks of the semester. A sign-up sheet will be made available in April.
The proposal, the project draft, and the final project will all be graded based on their quality. A late proposal or a sloppy project draft will pull your project grade down even if the final project is good.
Grading guidelines
The total project grade will be computed using the following percentages:
Project proposal: 10% Project draft: 10% Final project program: 60% Final project paper: 10% Final project in-class presentation: 10%
All programs should exhibit good style. Each variable name should suggest the meaning of the variable. Proper indentation should be used throughout. The program should begin with a comment stating the programmer's name, the date, the course the program was written for, and the problem that the program solves. Each subroutine (function, procedure, or predicate, depending on the language) should begin with a comment explaining what that subroutine does. Any complicated algorithms or data structures in the program should be commented, as should any portion of the code that is unclear. A project will not receive an A if it is written in a poor style, even if the program solves its problem correctly.
My only requirement for the user interface is that it should be clear for the user to understand and should provide reasonable error-checking. (The program should not crash merely because the user inputs an illegal game move, for example.) Prompts should be clear, and instructions should be provided where appropriate.
Your program may have either a command-line user interface or a graphical user interface. Do not invest too much time in making a fancy user interface, however, unless the rest of your program works correctly. A game-playing program that plays well and uses alpha-beta pruning but has a simple command-line interface can receive an A; a game-playing program that plays poorly and does not use alpha-beta pruning but has a fancy graphical user interface will not receive an A. (And similarly for other kinds of projects.)
This will vary depending on the exact problem, but here are some sample guidelines. In the descriptions below, "excellent" describes the quality that I expect from a program that receives an "A".
An excellent game program (for a zero-sum game of perfect information) should use minimax and alpha-beta pruning, and it should have a heuristic function that enables it to play well.
An excellent rule-based natural language program should contain at least 30-40 grammar rules (not counting lexical rules like noun --> [cat]), and it should take some interesting action based on the input (such as create a semantic net, construct a database query, or construct a UNIX shell command). An excellent ATN-based natural language program should contain networks for at least 30-40 different kinds of phrases.
An excellent genetic algorithm project should incorporate mutation and crossover, each with associated probabilities, and candidates for reproduction should be chosen based on a fitness function. The project should report the results of several different runs of the program, with different settings for mutation and crossover probabilities, with an evaluation of which settings worked best for your problem.