Advanced Artificial Intelligence: 15-780 / 16-731, Spring 2005

Class meeting times: Tue/Thu 1:30 - 2:50, Newell-Simon Hall 1305

Instructors

Mike Lewicki
lewicki@cs, http://www.cs.cmu.edu/~lewicki
Mellon Institute 115K, x8-3921

Tuomas Sandholm
sandholm@cs, http://www.cs.cmu.edu/~sandholm
Wean 7127, x8-8216

Office hour: Tu 3-3:30.

Teaching Assistants

Andrew Gilpin
gilpin@cs, http://www.cs.cmu.edu/~gilpin
Wean 3715 x8-1405

Jean Oh
jeanoh@cs, http://www.cs.cmu.edu/~jeanoh
NSH 1517, x8-5921Course book

Russell and Norvig: Artificial Intelligence: A Modern Approach, second edition, Prentice Hall.

Evaluation

            Evaluation will be based on written and programming homeworks/projects.  There will be no exams.

Course schedule (will be updated dynamically)

• Tue Jan 11: Course organization, introduction, definitions of AI, examples of AI, history of AI (Mike)
• Lecture slides: introduction, history of AI, course organization Read Chapter 1.

Segment I: Search (Tuomas).

Topics: AI as the design of agents, linear programming refresher, uninformed search, constraint satisfaction problems and algorithms, informed search, heuristics, upper and lower bounding techniques, mixed integer programming, iterative refinement search.

• Thu Jan 13: AI as the design of agents. Read chapter 2.  Search.
• Tue Jan 18: Uninformed search. Read chapter 3. Informed search.
• Thu Jan 20: More on informed search.  Read chapter 4.
• Tue Jan 25: Advanced informed search. Read this article: Optimal Winner Determination Algorithms. = chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.  Homework 1 posted.
• Thu Jan 27: More on advanced informed search. 
• Tue Feb 1: Rest of advanced informed search.  Iterative refinement algorithms.
• Thu Feb 3: Guest lecture on robotic path planning/manipulation.
• Tue Feb 8: Constraint satisfaction problems (CSPs), variable and value ordering heuristics, forward checking, arc consistency, conflict-directed backjumping, constraint learning, cutsets, tree decomposition, phase transitions, and iterative refinement for SAT. Read chapter 5. Homework 1 due.

Segment II: Probabilistic Inference and Learning (Mike)

Topics: AI as optimal decision making, probability theory, probabilistic reasoning, Bayesian networks, learning and inference algorithms, stochastic methods, sequential reasoning, HMMs, MDPs, POMDPs, efficient reasoning.

• Thu Feb 10: Probability theory.  Read chapter 13.
• Tue Feb 15: More on probability theory and probabilistic inference.  Here is the matlab code is used for the examples. For reference, almost any book on probability theory will cover this basic material.  Here are some I like:
• Bayesian Data Analysis by Gelman, Carlin, Stern, and Rubin.
• Information Theory, Inference, and Learning Algorithms, by David MacKay.
• Thu Feb 17: Density estimation. Read chapter 20.  The references listed about are also useful.
• Tue Feb 22: Probabilistic Reasoning.   Read chapter 14.
• Thu Feb 24: Inference and Learning in Bayesian Networks.
• Tue Mar 1: Graphical Models.
• M. I. Jordan, "Graphical Models", Stat. Science, Vol. 19, No. 1, 140-155, 2004.  (pdf)
• Thu Mar 3: Hidden Markov Models.  Read chapter 15.
• L. R. Rabiner, "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition," Proc. of the IEEE, Vol.77, No.2,  pp.257--286, 1989.  (pdf)
• Homework 2 part A posted.  Introduction to Matlab. Other tutorials.
• Homework 2 part B posted.
• Mon Mar 7 - Fri Mar 11, Spring Break, no class
• Tue Mar 15: Inference in Continuous Time. Read chapter 15 and 25.1-3.
• Thu Mar 17: Markov Decision Processes. Read chapters 16 and 17.
• Homework 2 (parts A and B) due.
• Tue Mar 22: No lecture. Homework 3 posted. The insurance.m file.
• Thu Mar 24: POMDPs.  Chapter 17.

Segment III: Computational Game Theory (Tuomas)

Topics: Game types, game representations, solution concepts, algorithms for solving games, algorithms that play well albeit not optimally, mechanism design.

• Tue Mar 29: Game types, normal form, extensive form, solution concepts, complexity of finding solutions. Slide packet 1a, slide packet 1b. Read Chapters 6, 17.6-17.7. Optional reading: an extended version of an IJCAI-03 paper on the complexity of finding equilibria of games.
• Thu Mar 31: Algorithms for solving normal form games (Lemke-Howson, PNS, MIP Nash, LP for zero-sum games, etc.). Homework 3 due. Homework 4 posted.
• Tue Apr 5: Algorithms for solving/playing well in sequential games of complete information. Case: Deep Blue for chess.
• Thu Apr 7: Algorithms for solving sequential games of incomplete information, sequence form, GameShrink for automated (lossless) abstraction. Case: poker.
• Tue Apr 12: Mechanism design, Gibbard-Satterthwaite impossibility, Vickrey-Clarke-Groves mechanism, auctions.
• Thu Apr 14, Spring Carnival, no class
• Tue Apr 19: Automated mechanism design. Homework 4 due. Homework 5 posted (updated 4/24).

Segment IV: Natural Intelligence (Mike)

Topics: Properties of natural intelligent systems, natural perception, how the brains does it, open issues in AI.

• Thu Apr 21: Natural Intelligence 1.
  
• Tue Apr 26: Natural Intelligence 2.
  
• Thu Apr 28: Natural Intelligence 3.
  Homework 5 due.