Advanced Topics in AI

Welcome to Lecture 3 – Constraint Satisfaction Problems. These problems also belong to Search Problems, namely to Identification Problems. In this lecture we don’t care about the path to the goal, like we did in the last lecture. We are only interested in finding a goal which satisfies certain properties, called constraints. We will look at how to define such Constraint Satisfaction Problems (CSPs), and how to solve them efficiently using general-purpose algorithms, heuristics and by exploiting the structure of the CSP.

Topics in this course:

• Formalization and Varieties (CSP 1)
• Examples (CSP 2)
• Backtracking (CSP 3)
• Improving Backtracking by Filtering and Ordering (CSP 4 and 5)
• Exploiting the Structure and Improving it (CSP 6 and 7)
• Iterative and Local Methods (CSP 8 and 9)

The lecture videos can be found here.

Step-by-step examples and additional explanations:

• Formalization
• CSP Example
• Improving Structure