Learn · NPTEL

Course10610615842 lectures

AI:Constraint Satisfaction

Prof. Deepak Khemani · IIT Madras

Start with lecture 1 At NPTEL

Lectures

Week 1: Introduction to CSP and Constraint Networks

  1. Constraint Satisfaction Problems Video
  2. CSP Examples: Map colouring, N-Queens, Classroom scheduling Video
  3. CSP Examples: Huffman-Clowes Labelling, Waltz Algorithm, Crosswords Video
  4. Model Based Diagnosis - An application of CSP Video

Week 2: Projection Networks, Constraint Propagation, Generalized AC

  1. Constraint Networks - An Introduction Video
  2. Binary Constraint Networks (BCN), Equivalent Networks Video
  3. Projection Networks Video

Week 3: i-consistency. Directional consistency, Graph orderings

  1. Constraint Propagation Video
  2. Algorithms AC1 and AC3 Video
  3. Can we do better than AC3? Video
  4. Algorithm AC4 Video
  5. Generalized AC, Path-Consistency Video
  6. i-Consistency, Algorithm PC1 Video
  7. Algorithm PC2, Strong i-Consistency Video

Week 4: Backtrack free search, Adaptive consistency, Search methods for solving CSPs, Lookahead methods

  1. Directional Consistency and Graph Ordering Video
  2. Min-Width and Min-Induced-Width Ordering Video
  3. Directional Arc-Consistency and Tree CSPs Video
  4. Directional Path-Consistency and Directional i-Consistency Video
  5. Backtrack-Free search and Adaptive Consistency Video
  6. Adaptive Consistency: Bucket Elimination Video

Week 5: Combining search and reasoning, Lookback methods and Gaschnig's backjumping

  1. Search Methods for Solving CSPs Video
  2. Algorithm Backtracking Video
  3. Look-Ahead Methods in Search Video
  4. Look-Ahead Search: Examples Video
  5. Combining Search with Reasoning: Algorithm DPLL Video
  6. Algorithm Backmarking Video
  7. Dynamic Value Ordering, Dynamic Variable Ordering Video

Week 6: Graph based backjumping, Conflict directed backjumpipng, Combining lookahead with lookback, Learning

  1. Look-Back Methods - Definitions Video
  2. Gaschnig’s Backjumping: The Culprit Variable Video
  3. Gaschnig’s Backjumping, Graph-Based Backjumping Video
  4. Graph-Based Backjumping: Internal and Relevant Dead-Ends Video
  5. Conflict-Directed Backjumping: Definitions Video
  6. Algorithm Conflict-Directed Backjumping Video
  7. Combining Look-Ahead and Look-Back: FC-CBJ Video
  8. Learning During Search Video

Week 7: Model based systems, Model based diagnosis, Truth maintenance systems

  1. Model Based Systems Video
  2. Model Based Diagnosis Video
  3. Truth Maintenance Systems Video
  4. Planning as Constraint Satisfaction Video
  5. Planning as Constraint Satisfaction (cont.) Video
  6. Planning as Satisfiability Video
  7. Wrapping Up and Further Study Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Madras
Department
Computer Science and Engineering
Teacher
Prof. Deepak Khemani
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed