Constraint Satisfaction Algorithms, with applications in Computer Vision and Scheduling

Tutorial Slides by Andrew Moore

The tutorial teaches concepts from the AI literature on Constraint Satisfaction. Accompanying animations are in http://www.cs.cmu.edu/~awm/animations/constraint. This is a special case of uninformed search in which we want to find a solution configuration for some set of variables that satisfies a set of constraints. Example problems including graph coloring, 8-queens, magic squares, the Waltz algorithm for interpreting line drawings, many kinds of scheduling and most important of all, the deduction phase of minesweeper. The algorithms we'll look at include backtracking search, forward checking search and constraint propagation search. We'll also look at general-purpose heuristics for additional search accelerations.

Download Tutorial Slides (PDF format)

Powerpoint Format: The Powerpoint originals of these slides are freely available to anyone who wishes to use them for their own work, or who wishes to teach using them in an academic institution. Please email Andrew Moore at awm@cs.cmu.edu if you would like him to send them to you. The only restriction is that they are not freely available for use as teaching materials in classes or tutorials outside degree-granting academic institutions.

Advertisment: I have recently joined Google, and am starting up the new Google Pittsburgh office on CMU's campus. We are hiring creative computer scientists who love programming, and Machine Learning is one the focus areas of the office. If you might be interested, feel welcome to send me email: awm@google.com .