Project Ideas

The ideal project will be done as a group of three students, but if that doesn't work for you, let me know what you'd like to do and why and we'll work something out. Groups are welcome to propose any project idea that excites them; I'm happy to iterate with you, make suggestions and point you to relevant papers or resources.

Guidelines

Here are a few guidelines that may help choose a successful project:

Aim for a open-ended, scalable project, i.e. one where you can likely get something simple written quickly and then improve it in variety of ways. This way, if you under estimate the length or difficulty of the project, you'll still get something out of it. And hopefully, you'll have time for some fun bels and whistles. If you, instead, choose a monolythic project, there is greater risk of doom. To reify this strategy, write down a series of milestones in advance with your best guess as to how long they will take. Does your plan allow every member of the team to be working in parallel or are some people blocked by deliverables from teammates?
Aim for a project where there is an interesting question to be answered or experiment to be run. This is good practice for research papers, will be fun to evaluate, and is a key thing to try and include in your final report. For example, What is the relative performance (both in compute time and score) of two different Pacman control strategies? What are the relative learning curves for a Q-learning algorithm using linear function approximation vs one using a multi-layer neural network?
You are welcome to write code from scratch or start by downloading code from the Web; however, your report must explicitly list all code or external resources used. Your grade will be based (naturally) on the ideas, implementation and experiments that you perform, so if you use external code, then more significant results are expected (however, it may be more fun as well).

Concrete Project Suggestions

And here are a few specific ideas to consider:

Extend the Pacman reinforcement-learning agent to handle larger enviroments or to handle a different simulated world. Implement the UCT algorithm and/or policy iteration and/or different abstraction schemes. Resources: original paper on UCT, tutorial on UCT.
If you are sick of Pacman, why not try a game? A common AI class project is an othello-playing program (you should be able to find code for one on the Web). If you have already implemented alpha-beta search, then the main effort is devising a good heuristic board evaluation function. Instead, why not learn th evaluation function using reinforcement learning by playing the agent against itself? Resources: clearly written paper on RL applied to Othello.
Interested in Blackjack? Check out the programming project described here. This is a great way to get started (ignore the specific compilation and turnin details) and you can extend it in any direction you like - finite number of card decks, reinforcement learning, additional state (card counting) etc. A great report will compare the effectiveness of several strategies (eg with and without extra state).
In HW 4, you've implemented partical filtering as a mechanism for letting Pacman track it's beliefs about ghost-positions given noisy sensor information. But then the planner makes a (simple but dumb) MAP assumption and assumes that each ghost is in it's most likely position and acts accordingly. For your project, try implementing one or more POMDP algorithms and plan a course of action that accounts for all possible positions of the ghosts, weighted by their probability. Does it perform better than the MAP planner? Can you devise worlds where it does much better? How much slower is the planner than a plain MDP planner?

Schedule

See main class page.

Project Deliverables

Here are some notes on initial Specifications, end-of-term in-class Presentations and Final Written Reports

Project Groups

Department of Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA 98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX