Advanced Artificial Intelligence: 15-780 / 16-731, Spring 2005
1:30 - 2:50 ,
Newell-Simon Hall 1305 Instructors
Artificial Intelligence: A Modern Approach, second edition,
Evaluation will be based on written and programming
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)
Segment I: Search (Tuomas).
Topics: AI as
the design of
agents, linear programming refresher, uninformed search, constraint
satisfaction problems and algorithms, informed search, heuristics,
lower bounding techniques, mixed integer programming, iterative
Thu Jan 13: AI
as the design of agents. Read
chapter 2. Search.
Tue Jan 18: Uninformed
search. Read chapter 3.
Thu Jan 20: More on informed
search. Read chapter 4.
Tue Jan 25: Advanced
informed search. Read this article:
Winner Determination Algorithms. = chapter 14 of the book Combinatorial
Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press. Homework
Thu Jan 27: More on advanced
Tue Feb 1: Rest of advanced
informed search. Iterative
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,
theory, probabilistic reasoning, Bayesian networks, learning and
algorithms, stochastic methods, sequential reasoning, HMMs,
Segment III: Computational Game Theory (Tuomas)
Topics: Game types, game representations,
concepts, algorithms for solving games, algorithms that play well
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
natural perception, how the brains does it, open issues in AI.