Class meeting
times: Tue/Thu **,
**Newell-Simon Hall 1305

**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.

**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-5921*Course book*

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

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

**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.