Date |
Content |
Readings |
Textbook |
| PROPOSITIONAL SATISFIABILITY | |||
| Tu 3/31, Th 4/2, Tu 4/7 | Introduction. Propositional satisfiability, phase transitions and heavy-tailed behaviour. Stochastic search, DPLL algorithm, discrete Lagrangian methods. | [1-7] | RN 7.5-7.6; D 5.3-5.4, 6.5; GNT 7.3 |
| CONSTRAINT SATISFACTION | |||
| Th 4/9 | Introduction to CSPs and local consistency algorithms. | [8] | RN 5.1-5.2; D 2.1, 3.1-3.4 |
| Tu 4/14, Th 4/16 | Classical CSP algorithms: conflict-directed backjumping, forward checking, backmarking, dynamic variable ordering. | [9-10] | RN 5.2-5.3; D 5.1-5.2, 6.1-6.4, 6.6 |
| Tu 4/21 | Dynamic backtracking. Decomposition methods. | [11-12,13] | RN 5.4; D 9.1-9.3 |
| CONSTRAINT-BASED SCHEDULING | |||
| Th 4/23, Tu 4/28 | Simple Temporal Networks and constraint-based scheduling. | [14,15] | RN 12.1; D 12.2-12.3; RVBW 22.1, 22.3-22.4; GNT 13.4, 15.2-15.3; ZF ch 4 |
| PLANNING | |||
| Th 4/30, Tu 5/5 | Classical Planning: Causal Link, State Space, HTN, SAT, CSP, and GraphPlan planning. Reachability heuristics. | [18-22,23] | RN 11.1-11.6, 12.2; GNT 2.1-2.6, 4.2-4.5, 5.2-5.6, 6.2-6.3, 7.2, 7.4, 18.2, 8.3, 8.5-8.6, 11.5, 9.2-9.4 |
| Th 5/7 | Temporal and resource-based planning. | [24-26] | RN 12.2; GNT 14.2, 15.4 |
| Tu 5/12 | Planning under uncertainty. | [27-29] | RN 12.3-12.4; GNT 16.2-16.4, ... |
| Th 5/14 | Integrative SAT and CSP planning; combined planning and scheduling. | [30-32] | RVBW 22.2; ZF ch 6,16,19,24; GNT 15.4 |
| Tu 5/19 | Guest lecture | ||
| ADVANCED TOPICS | |||
| Th 5/21 | Modelling, symmetry, preferences. Complexity results. | [33-36] | Excerpts of RVBW ch 11, 10, 9, 8; ... |
| Tu 5/26 | Execution: plan execution and recognition, model-based diagnosis and control. | [37] | RN 12.5-12.6; ZF ch 12; GNT 24.8-24.9, 19.2-19.6 |
| CONCLUSION | |||
| Th 5/28 | Student presentations | ||
| Tu 6/2 | No class scheduled |
Readings specified are from the reading list. Textbooks are referred to by authors named: e.g., RN is Russell & Norvig, Second Edition.