In the previous notes, all the problems can be solved by searching in a space of states. These states can be evaluated by domain-specific heuristics and tested to see whether they are goal states. From the point of view of the search algorithm, however, each state is atomic, or indivisible—a black box with no internal structure.

To solve a wide variety of problems more efficiently, we use a factored representation for each state: a set of variables, each of which has a value. A problem is solved when each variable has a value that satisfies all the constraints on the variable. A problem described this way is called a constraint satisfaction problem, or CSP.

Defining CSP

A constraint satisfaction problem consist of three components, X, D and C:

• X: set of variables
• D: set of domains, one for each variable
• C: set of constraints that specify allowable combinations of values

To solve a CSP, we need to define a state space and the notion of a solution. Each state in a CSP is defined by an assignment of values to some or all of the variables. An assignment that does not violate any constraints is called a consistent assignment. A complete assignment is one in which every variable is assigned, and a solution to a CSP is a consistent, complete assignment.

Variations on the CSP formalism

Discrete Variables:

For finite domains, domain of size d → $O(d^m)$ complete assignments

need a constraint language such as $T_1 + d_1 \le T_2$

Continuous Domain

Ex: Scheduling time of Hubble Space Telescope

Best Known category: Linear Programming problems, where constraints must be linear equalities or non-equalities. Linear programming problems can be solved in time polynomial in the number of variables. Problems with different types of constraints and objective functions have also been studied—quadratic programming, second-order conic programming, and so on.

Type of Constraints:

• Unary constraint: constraint that restricts the value of a single variable
• Binary constraint: constraint that involve 2 variables
• Global Constraint: constraint involve 3 or more variables, like Alldiff (all variables need to have different value)

Many real-world CSPs include preference constraints, indicating which solutions are preferred. Those constraints can be understand as soft constraints and are often representable by a cost for each variable assignment. We call such a problem a constraint optimization problem, or COP. Linear programming problems do this kind of optimization.

Constraint Propagation

In CSP, an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint propagation: using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable, and so on.

The key idea is local consistency. We have to make sure each part of the problem stay consistent throughout the process, and there are different types of them:

Node Consistency