Class Project

Your class project is an opportunity for you to explore an interesting artificial intelligence problem of your choice. All projects must have an implementation component, though theoretical aspects may also be explored. You should also evaluate your approach, preferably on real-world data, though for some projects simulated data may also be appropriate. Below, you will find some project ideas, but the best idea would be to combine AI with problems in your own research area. Your class project must be about new things you have done this semester; you can't use results you have developed in previous semesters. If you are uncertain about this requirement, please email the instructors.

Projects should be done in teams of 1-3 students. Each project will also be assigned a 15-780 instructor as a project consultant/mentor. They will consult with you on your ideas, but of course the final responsibility to define and execute an interesting piece of work is yours. Your project will be worth 25% of your final class grade, and will have the following deliverables:

  1. A project proposal (1 page maximum). This should include a project title, a project idea, the data set that you will use, the software that you need to write, 1-3 revelant papers that you need to read, and who your teammates are.

  2. First project milestone report. This writeup should present substantial initial results (4 pages). Worth 10% of project grade.

  3. Second project milestone report. Should be a mostly complete draft with results of your first experiments, although possibly missing the final experiments (5 pages). Worth 15% of project grade.

  4. A final writeup in the format of a conference paper (6 pages maximum, not including references). Worth 40% of project grade

  5. A poster presenting your work for a special class poster session. This is in lieu of a final exam and all students are required to attend. Worth 35% of the project grade.

Formatting

The project milestones and final writeup should be written in LaTeX using \documentclass[twocolumn]{article} or similar. The margins and spacing should not be altered. Finally, the bibliography does not count against the page limit.

Candidate Projects

Below are descriptions of some potential project ideas. You are encouraged to select and flesh out one of these projects, or make up your own well-specified project.

Project 1: A recent paper presents a new algorithm for computing Nash equilibria in large zero-sum extensive-form games based on the idea of minimizing counterfactual regret. This algorithm was used by University of Alberta's computer poker research group to produce one of the best bots in the world for two-player limit Texas hold'em. The project would be to implement this algorithm and run it on two-player limit Texas hold'em, plotting how the solution quality changes over time. We can provide a similar plot for the algorithm used by CMU's bot. This would establish which of the two equilibrium-finding algorithms is better for the game -- an important open problem.

Project 2: Sometimes the solution output by state-of-the-art equilibrium-finding algorithms possesses undesirable qualities. For example, the equilibrium of 1-card poker found here uses the standard approach of converting the game to sequence-form and solving an LP, but the computed strategy for player 2 is actually weakly dominated (e.g., he can shift weight from calling with a 5 to calling with an 8). In a recent paper, several efficient algorithms are presented for computing equilibrium refinements. These algorithms guarantee that equilibria with more desirable properties are found, and in particular that an equilibrium that is not weakly-dominated is found. The project would involve implementing one or more of the algorithms from this paper and testing them on 1-card poker, or another game. Another algorithm of interest would be fictitious play, which is used to compute an approximate-equilibrium in 3-player tournaments in this paper .

Project 3: Traffic insanity: in this project you would investigate automated management of traffic intersections. This is an interesting subject with suprising results. Automated traffic management systems have been shown to perform significantly (sereval hundred times) better than traffic lights. There are a number of papers on this subject here, and the paper which started it all is here. Optimize efficiency, maximum throughput, or robustness to uncertainty. Look at the behavior of a system with multiple intersections.

Project 4: In this project you would consider the problem of sensor planning. For example, you could plan a path for a robot which allows its sensors to reduce its uncertainty as rapidly as possible. Sensors could include cameras or laser rangefinders and uncertainty could be about the shape or identity of an object or environment. We have access to an O-bot mobile robot which will allow you to implement your algorithm on a research robot and run it in a real environment. Talk to Byron or Geoff if you are interested in this project.

Project 5: Decision making and planning play an important role in robotics where the goal is to make an optimal series of actions to achcieve some goal. In a recent paper the authors show that finding the optimal action for a given state can be naturally formalized as a multiclass classificaton problem. This project would involve building a Lego Mindstorms robot and implementing a planning algorithm to alllow the robot to complete some intelligent task. Examples include planning for gripping objects and footplacement planning for bipedal walking. Make the planner run as quickly as possible, while still finding near optimal paths.

Project 6: An important class of problems in AI are satisfiability problems. Local search algorithms like WalkSAT are known to perform well on a variety of problems, particularly those derived from automated planning problems. However, scaling WalkSAT to work on large problems is not trivial. Additionally, WalkSAT lacks the clause-learning capabilities of other solvers like DPLL. One option to parallelize WalkSAT is to run multiple copies and learn new clauses by taking a "snapshot" of all the copies at a given point in time. Graphics processing units provide an ideal environment for parallelizing WalkSAT: they are extremely parallel (up to 5000 threads), WalkSAT has little control flow, and the CPU is left free during execution and could be put to use learning new clauses without interrupting the WalkSAT instances. In this project, you would implement WalkSAT to run on CUDA (nvidia's GPU SDK) or equivalent platform and test its performance on automated planning problems.

Project 7: Reinforcement Learning Competition. The reinforcement learning (RL) competition is a forum for reinforcement learning researchers to rigorously compare the performance of RL methods on a suite of challenging domains. You can read more about the competition here. Although the testing MDPs won't be available until after the end of the semester, you may present your own results on the proving MDPs during the class poster session.