Introduction & Logic [Geoff ~3 Lectures]

- Propositional Logic
- First-order Logic
- Proofs
- resolution
- unification

- Satisfiability

Tues., Jan. 13:

- Lecture: Introducton to AI and Logic. [Slides] [Annotated]

Thurs., Jan. 15:

- Lecture: Proofs and First Order Logic. [Slides] [Annotated]

Tue., Jan. 20:

- Lecture: FOL proofs, completeness, and SAT [Slides] [Annotated]

Thurs., Jan. 22:

- First Half of Lecture: Satisfiability (Geoff) [Slides] [Updated]
- Second Half of Lecture: Search (Tuomas) [Slides(.ppt)] [Slides(.pdf)]

[Top]

Search & Optimization [Tuomas ~9 Lectures]

- Theorem Proving as Search
- Constraint Satisfaction Problems
- variable and value ordering heuristics
- forward checking
- arc consistency
- conflict-directed backjumping
- constraint/clause learning
- cutsets
- tree decomposition
- phase transitions
- iterative refinement
- DPLL

- Optimization
- informed search (i.e. with an objective and h-function)
- MIP including Gomory mixed integer cut
- pseudo-boolean inequalities
- relating CSP, (Max)SAT, and MIP
- binary search on objective value
- relating clause learning & cuts
- relating resolution, LP relaxation, and cuts
- Optional Topic: RRTs/spatial search (Geoff)

Tues., Jan. 27:

- Constraint Satisfaction Problems [Slides(.ppt)] [Slides(.pdf)]

Thurs., Jan. 29:

- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]

Tues., Feb. 3:

- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]

Thurs., Feb. 5:

- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]

- Russell & Norvig Chapter 5
- "GRASP: A Search Algorithm for Propositional Satisfiability", Marques-Silva & Sakallah, IEEE Trans. Computers, C-48, 5:506-521,1999
- "Chaff: Engineering an Efficient SAT Solver", Moskewicz, Madigan, Zhao, Zhang & Malik, 2001
- "BerkMin: A Fast and Robust Sat-Solver", Goldberg & Novikov, Proc. DATE 2002, pp. 142-149
- The slides on efficient boolean satisfiability here
- "Conflict-directed backjumping revisited", by Chen and van Beek, Journal of AI Research, 14, 53-81, 2001

Tues., Feb. 10:

- Informed Search [Slides(.ppt)] [Slides(.pdf)]

Thurs., Feb. 12:

- Informed Search [Slides(.ppt)] [Slides(.pdf)]
- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]

- Sandholm, T. 2006. "Optimal Winner Determination Algorithms", Chapter 14 of the book
*Combinatorial Auctions*, Cramton, Shoham, and Steinberg, eds., MIT Press.

Tues., Feb. 17:

- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]

Thurs., Feb. 19:

- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]

[Top]

Linear Programs, Convex Programs, Duality [Geoff ~2 Lectures]

- Boyd & Vandenberghe. Convex Optimization Sec 4.3.
- V. Vazirani. Approximation Algorithms. Ch 12.

Tues., Feb. 24:

- Optimization, Duality [Slides(.pdf)]

Thurs., Feb. 26:

- Duality [Slides(.pdf)]

- Multiple ways to write TSP as MIP [see lectures 1, 3]
- Lift and project cuts
- Another recent family of cuts
- Smoothed analysis
- MINISAT+ (software for solving PBIs)

[Top]

Planning [Geoff ~2 Lectures]

- Partial order planning
- Graphplan / SATplan

Tues., March 3rd:

- Duality and Planning [Slides(.pdf)]

Thurs., March 5th:

- Spatial Search; Uncertainty [Slides(.pdf)]

[Top]

Probabilistic Inference [Geoff ~4 Lectures]

- (Optional) Factor graphs and the sum-product algorithm (2001) Frank R. Kschischang, Brendan J. Frey, Hans-Andrea Loeliger

- Basic Probability
- marginals
- conditionals
- integration/summation

- Maximum Likelihood
- relation to optimization
- partition function
- natural/expectation parameters

- Undirected Graphical Models (MRFs)
- relation to SAT
- variable elimination
- factor graph inference

- Gradient Descent Learning
- MCMC
- MH
- Gibbs
- particle filters

- Optional Topics (if we have time)
- HMMs/POMDPS/RL
- EM algorithm

Tues., March 9th:

- Uncertainty, Inference [Slides(.pdf)]

Tues., March 17th:

- Inference [Slides(.pdf)]

Thurs., March 19th:

- Inference, Learning [Slides(.pdf)]

Tues., March 24th:

- Learning [Slides(.pdf)]

Thurs., March 26th:

- Learning [Slides(.pdf)]

Tues., March 31th:

- Learning [Slides(.pdf)]

[Top]

Game Playing, Equilibrium Finding [Tuomas ~6 Lectures]

- Game Types, Normal Form, Extensive Form, Solution Concepts, Solution Complexity
- Algorithms for Solving Normal Form Games
- Lemke-Howson
- PNS
- MIP Nash
- LP for zero sum games

- Complete Information Sequential Games
- Case: Deep Blue for chess

- Incomplete Information Sequential Games
- sequence form
- Gameshrink for automated (lossless) abstraction
- Case: Poker

- Correlated Equilibrium (Geoff)

Thurs., April 2nd:

- Game Theory [Slides1(.pdf)] [Slides1(.ppt)] [Slides2(.pdf)] [Slides2(.ppt)]

Tues., April 7th:

Tues., April 21st:

- Sequential Games [Slides(.pdf)] [Slides(.ppt)]

Thurs., April 23rd:

- Sequential Games [Slides(.pdf)] [Slides(.ppt)]

Tues., April 28th:

- Sequential Games [Slides(.pdf)] [Slides(.pptx)] [Slides(.ppt)]

[Top]

Multiagent Learning [Geoff ~2 Lectures]

- No-external-regret
- No-Phi-regret

[Top]

Mechanism Design [Tuomas 1 Lecture]

- Mechanism Design Setting
- Gibbard-Satterthwaite Impossibility
- Vickrey-Clarke-Groves Mechanism
- Auctions
- Automated Mechanism Design

[Top]