NOC:AI:Constraint Satisfaction


Lecture 1 - Constraint Satisfaction Problems


Lecture 2 - CSP Examples: Map colouring, N-Queens, Classroom scheduling


Lecture 3 - CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords


Lecture 4 - Model Based Diagnosis - An application of CSP


Lecture 5 - Constraint Networks - An Introduction


Lecture 6 - Binary Constraint Networks (BCN), Equivalent Networks


Lecture 7 - Projection Networks


Lecture 8 - Constraint Propagation


Lecture 9 - Algorithms AC1 and AC3


Lecture 10 - Can we do better than AC3?


Lecture 11 - Algorithm AC4


Lecture 12 - Generalized AC, Path-Consistency


Lecture 13 - i-Consistency, Algorithm PC1


Lecture 14 - Algorithm PC2, Strong i-Consistency


Lecture 15 - Directional Consistency and Graph Ordering


Lecture 16 - Min-Width and Min-Induced-Width Ordering


Lecture 17 - Directional Arc-Consistency and Tree CSPs


Lecture 18 - Directional Path-Consistency and Directional i-Consistency


Lecture 19 - Backtrack-Free search and Adaptive Consistency


Lecture 20 - Adaptive Consistency: Bucket Elimination


Lecture 21 - Search Methods for Solving CSPs


Lecture 22 - Algorithm Backtracking


Lecture 23 - Look-Ahead Methods in Search


Lecture 24 - Look-Ahead Search: Examples


Lecture 25 - Combining Search with Reasoning: Algorithm DPLL


Lecture 26 - Algorithm Backmarking


Lecture 27 - Dynamic Value Ordering, Dynamic Variable Ordering


Lecture 28 - Look-Back Methods - Definitions


Lecture 29 - Gaschnig’s Backjumping: The Culprit Variable


Lecture 30 - Gaschnig’s Backjumping, Graph-Based Backjumping


Lecture 31 - Graph-Based Backjumping: Internal and Relevant Dead-Ends


Lecture 32 - Conflict-Directed Backjumping: Definitions


Lecture 33 - Algorithm Conflict-Directed Backjumping


Lecture 34 - Combining Look-Ahead and Look-Back: FC-CBJ


Lecture 35 - Learning During Search


Lecture 36 - Model Based Systems


Lecture 37 - Model Based Diagnosis


Lecture 38 - Truth Maintenance Systems


Lecture 39 - Planning as Constraint Satisfaction


Lecture 40 - Planning as Constraint Satisfaction (Continued...)


Lecture 41 - Planning as Satisfiability


Lecture 42 - Wrapping Up and Further Study