IIT Madras · Computer Science

AI:Constraint Satisfaction

Prof. Deepak Khemani · 42 free video lectures

42 video lectures. Topics: Constraint Satisfaction Problems; CSP Examples: Map colouring, N-Queens, Classroom scheduling; CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords; Model Based Diagnosis - An application of CSP; Constraint Networks - An Introduction; Binary Constraint…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Constraint Satisfaction Problems
  2. CSP Examples: Map colouring, N-Queens, Classroom scheduling
  3. CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords
  4. Model Based Diagnosis - An application of CSP
  5. Constraint Networks - An Introduction
  6. Binary Constraint Networks (BCN), Equivalent Networks
  7. Projection Networks
  8. Constraint Propagation
  9. Algorithms AC1 and AC3
  10. Can we do better than AC3?
  11. Algorithm AC4
  12. Generalized AC, Path-Consistency
  13. i-Consistency, Algorithm PC1
  14. Algorithm PC2, Strong i-Consistency
  15. Directional Consistency and Graph Ordering
  16. Min-Width and Min-Induced-Width Ordering
  17. Directional Arc-Consistency and Tree CSPs
  18. Directional Path-Consistency and Directional i-Consistency
  19. Backtrack-Free search and Adaptive Consistency
  20. Adaptive Consistency: Bucket Elimination
  21. Search Methods for Solving CSPs
  22. Algorithm Backtracking
  23. Look-Ahead Methods in Search
  24. Look-Ahead Search: Examples
  25. Combining Search with Reasoning: Algorithm DPLL
  26. Algorithm Backmarking
  27. Dynamic Value Ordering, Dynamic Variable Ordering
  28. Look-Back Methods - Definitions
  29. Gaschnig’s Backjumping: The Culprit Variable
  30. Gaschnig’s Backjumping, Graph-Based Backjumping
  31. Graph-Based Backjumping: Internal and Relevant Dead-Ends
  32. Conflict-Directed Backjumping: Definitions
  33. Algorithm Conflict-Directed Backjumping
  34. Combining Look-Ahead and Look-Back: FC-CBJ
  35. Learning During Search
  36. Model Based Systems
  37. Model Based Diagnosis
  38. Truth Maintenance Systems
  39. Planning as Constraint Satisfaction
  40. Planning as Constraint Satisfaction (cont.)
  41. Planning as Satisfiability
  42. Wrapping Up and Further Study

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Madras.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights