Introduction to Constraint Satisfaction

Introduction: problem formulation, historical overview, applications.
Search approaches: local search (hill climbing, min-conflicts), depth-first search (backtracking, backjumping, backmarking).
Consistency techniques: arc consistency and algorithms to achieve it (AC-3, AC-4), higher-level consistency techniques: path-consistency, global constraints.
Summary: Integration of consistency with search, value/variable ordering heuristics. Optimization problems. Problem modelling.

Constraint satisfaction is one of fundamental topics of artificial intelligence. The first constraint satisfaction techniques have been developed in computer vision and later applied in many areas, including planning, scheduling, resource allocation, and even bioinformatics. As a model-based approach, it provides trustworthy and explainable solutions as the users can easily understand and verify the model as well as the solution itself.

Many practical problems can be described using a set of variables and relations between them, i.e. as a constraint satisfaction problem. For example, in scheduling problems, variables describe times when activities start and resources (machines, people, tools etc.) to which the activities are allocated. Activities may be ordered in time, which is described using precedence relations, and resources may have limited capacity, for example, at most one activity can be processed at any time. Sudoku, N-queens problem, and map coloring are well-known puzzles that can be naturally encoded and solved using constraint satisfaction techniques. The course overviews major constraint satisfaction techniques and shows how they can be used to solve practical problems.