Syllabus
1. Introduction: definitions of planning and scheduling problems, examples, solving mechanisms (search, constraint satisfaction, SAT), representation of planning problems (set-theoretic, classical).
2. State-Space Planning (forward search, backward search, STRIPS), Plan-Space Planning (PSP, PoP), Neoclassical Planning (planning graph, Graphplan).
3. Planning as SAT, planning as a CSP, planning heuristics.
4. Planning with Time and Resources (temporal problems, planning with chronicles, resource allocation).
5. Scheduling problems: traditional scheduling problems, Graham’s classification, scheduling as constraint satisfaction, resource and precedence constraints, scheduling strategies.
6. Case studies.
Annotation
The course gives an introduction to planning and scheduling. It is focused on the algorithms for solving planning and scheduling problems with emphasis on using constraint-based techniques.