Constraint Satisfaction Problem

artificial-intelligence

Definition

Constraint Satisfaction Problem

A constraint satisfaction problem consists of three main components:

1. A finite set of variables $\mathcal{V}=\{V_1,V_2,\dots ,V_n\}$
2. Associated domains for each variable: Each variables $V_i\in \mathcal{V}$ has a non-empty domain $D_i$ of possible values it can take.
3. A finite set of constraints: $\mathcal{C}=\{C_1,C_2,\dots ,C_m\}$

A constraint $C\in \mathcal{C}$ between a subset of variables ${V_i}_1,\dots ,{V_i}_j$ is defined as a subset of the Cartesian product of their domains ${D_i}_1\times \cdots \times {D_i}_j$ This means a constraint lists all the allowed combinations of values for the variables it involves. For example, a constraint might be $V_1\ne V_2$, meaning $V_1$ and $V_2$ cannot have the same value.

Types of Constraints

Unary Constraint

A unary constraint restricts the domain of a single variable. For example $C(V_i)=\{1,3,5\}$ means $V_i$ must be 1, 3, or 5.

Binary Constraint

A binary constraint restricts the values of a pair of variables. For example, $C(V_i,V_j)=\{(1,2),(3,5)\}$ means if $V_i$ is 1, then $V_j$ must be 2, or if $V_i$ is 3, $V_j$ must be 5.

Constraint Satisfaction Problem

A state is defined by a set of variables $\mathcal{V}$, each of which has an associated domain $D_v$ of possible values. The goal test is a set of constraints that specify allowable combinations for values of subsets of these variables.

Essentially, you have a problem defined by variables, the possible values those variables can take, and a set of rules (constraints) that must be satisfied by any valid combination of values.

Comparison to Standard Search

In standard search problem, a state is often treated as a “black box” with no discernible internal structure from the algorithm’s perspective. The algorithm can only interact with states using problem-specific routines like a successor function, a heuristic function, and a goal test.

CSPs, on the other hand, have a more structured and standardised representation for states and the goal test. This structure allows for the development of search algorithms that can exploit this common representation and use general-purpose heuristics rather than problem-specific ones.