BSG Cylon

This course is targeted at graduate students who need to learn about current-day research, and about how to perform current-day research, in Artificial Intelligence—the discipline of designing intelligent decision-making machines.

Students entering the class should have a pre-existing working knowledge of linear algebra, calculus, algorithms and data structures, and basic knowledge of computational complexity though the class has been designed to allow students with a strong numerate background to catch up and fully participate. Students should also be able to program in C, C++, Java, Python, or Ruby.

The course textbook is Artifical Intelligence: A Modern Approach, 3rd edition, by Russell and Norvig. This is not a required purchase. We will supplement readings in this book with timely research papers posted to the course website.


The course is taught by professors Martial Hebert (RI) and Ariel Procaccia (CSD). The teaching assistants are John Dickerson (CSD) and Felipe Trevizan (MLD). The course is open to graduate students in the School of Computer Science; interested and qualified undergraduates and other students should contact the professors for permission to join.

When and where?

We meet most Mondays and Wednesdays from 12:00pm to 1:20pm in GHC 4215. The first lecture will be held on Wednesday, January 18. Check the lecture schedule below for details!

The TAs will also hold weekly informal recitations at 5:00pm on Thursdays in GHC 4303. Weekly office hours will be held at the following times and locations:

Name Day Hours Location
John Dickerson Wednesdays 5:00–6:00pm GHC 9219
Martial Hebert Thursdays 9:00–10:00am EDSH 224
Ariel Procaccia Fridays 9:00–10:00am GHC 9021
Felipe Trevizan Tuesdays 9:00–10:00am GHC 8223


All lecture and homework dates and topics are subject to change. This is a rough outline of the topics we will be covering this semester.


Date Room Lecture Title Lecturer Link Notes
5/7/2012 Project Writeups Due
5/2/2012 GHC 4215 Project presentations HW #5 due
4/30/2012 GHC 4215 Project presentations
4/25/2012 GHC 4215 Project presentations
4/23/2012 GHC 4215 Self-driving cars Hebert link
4/18/2012 GHC 4215 Computational fair division Procaccia link
4/16/2012 GHC 4215 Computational game theory II Procaccia link
4/11/2012 GHC 4215 Computational game theory I Procaccia link HW #5 out
4/9/2012 GHC 4215 Computational social choice II Procaccia link Bartholdi, Tovey, & Trick
4/4/2012 GHC 4215 Computational social choice I Procaccia link HW #4 due
4/2/2012 GHC 4215 Midterm exam
3/28/2012 GHC 4215 Perception Hebert link
3/26/2012 GHC 4215 Perception Hebert link Project milestone due
3/21/2012 GHC 4215 Perception Hebert link HW #3 due, HW #4 out
3/19/2012 GHC 4215 Classical planning II Procaccia link
3/14/2012 Spring break!
3/12/2012 Spring break!
3/7/2012 GHC 4215 Classical planning I Procaccia link Bylander
3/5/2012 GHC 4215 Constraint satisfaction problems (CSPs) II Procaccia link HW #3 out
2/29/2012 GHC 4215 Constraint satisfaction problems (CSPs) I Procaccia link HW #2 due
Proofs from lecture
2/27/2012 GHC 4215 Motion planning and path finding III Hebert link Project proposal due
2/22/2012 GHC 4215 Motion planning and path finding II Hebert link
2/20/2012 GHC 4215 Motion planning and path finding I Hebert link
2/15/2012 GHC 4215 Heuristic search Procaccia link HW #2 out
Dechter & Pearl
2/13/2012 GHC 4215 Adversarial search Procaccia link HW #1 due
Proofs from lecture
2/8/2012 GHC 4215 Reinforcement learning and POMDPs Veloso link
2/6/2012 GHC 4215 Markov decision processes Veloso link
2/2/2012 GHC 4215 Reasoning with uncertainty IV Hebert link
1/30/2012 GHC 4215 Reasoning with uncertainty III Hebert link HW #1 out
1/25/2012 GHC 4215 Reasoning with uncertainty II Hebert link
1/23/2012 GHC 4215 Reasoning with uncertainty I Hebert link
1/18/2012 GHC 4215 Introduction Procaccia link
1/16/2012 No class (MLK Day)


Homeworks are due at the begining of class, unless otherwise specified. You will be allowed 5 total late days without penalty for the entire semester. Each late day corresponds to 24 hours or part thereof. Once those days are used, you will be penalized according to the policy below: Homework is worth full credit at the beginning of class on the due date. For the next 24 hours, it will be graded so that the highest possible score is equal to the 70th percentile of the distribution of scores of the on-time homeworks. For example, if your raw score is 80 out of 100 points, but the 70th percentile of the HW distribution is 85/100, then you will get credit for 80 * (85/100) = 68 points. For the following 24 hours, it will be graded out of the 40th percentile of the on-time homeworks. Thereafter, it will be worth nothing. You must turn in all of the homeworks, even if for reduced credit, in order to pass the course.


HW Released Due Subjects Covered Link Notes Key
#5 4/13/2012 5/2/2012 Perception, social choice, and game theory link Code: link
#4 3/21/2012 4/4/2012 Classical planning link
#3 3/5/2012 3/21/2012 Motion planning and CSPs link Reading: link
#2 2/15/2012 2/29/2012 MDPs and classical search link Maze maps: link link
#1 1/30/2012 2/13/2012 Probabilistic inference link Observations: link link


In lieu of a final exam, students will complete a course project. We encourage students to combine techniques from AI with their own research for these projects. Projects will be accompanied by a 6-8 page paper due at the end of the semester and a poster presentation session at a date and time to be determined.


Project proposals are due on February 27, and should consist of a short (2–3 pages) but well-researched summary of your project idea accompanied by a plan of execution. Students are allowed (and encouraged) to work in groups; however, the expectations we will have for your project rise proportional to the group size! We'll post some project ideas in the future.

As an example of a reasonable project proposal, please take a look at the following example from last year's Graduate AI (pdf). The proposal begins with motivation and a brief explanation of the problem, and then sets a series of goals. If the project is harder than expected, only the "75%" goals will be completed; if it's difficult level is as expected, the "100%" goals will be completed; finally, if it's easier than expected, the student plans to complete the ambitious "125%" goals as well. The more you plan now, the easier it will be to complete your project well and on time!

Sample proposal: (pdf)


One month after proposing your project, the TAs will want to check up on your progress. On March 26, you will turn in a short (3–4) page description of the work you've accomplished on your project so far. You can also discuss any changes you've made to your project plans in this document.

Sample milestone: (pdf)

Final Presentation and Paper

During the last three scheduled lecture slots, student groups will give short (10–15 minutes) presentations of their projects. After these presentations (by 11:59pm on Monday, May 7), a conference-sized (6–8 pages) paper covering the project material will be due.

Bureaucratic Miscellania


Grades are based on Class Participation (10%), Homeworks (35%), Final Project (35%) and the Midterm (20%).

Auditing the class

Interested students should first register, then fill out an audit form and have one of the instructors sign it. Auditors are required to complete a class project, but no homeworks or exams: that way they can choose to focus their efforts on whichever area of AI most interests them.

To those outside CMU

Feel free to use the slides and materials available online here! If you use our slides, an appropriate attribution is requested. Please email the instructors with any corrections or improvements.

Carnegie Mellon University