Constraint Satisfaction Problem

artificial-intelligence

Definition

Constraint Satisfaction Problem

A constraint satisfaction problem is an instance $I=(V,D,C)$ consisting of:

1. A finite set of variables $V$
2. A finite domain $D$ of values
3. A finite set of constraints $C$

Each constraint is a pair $(S,R)$ where:

1. $S=(x_1,\dots ,x_r)$ is a tuple of variables called the scope
2. $R\subseteq D^r$ is an $r$-ary relation specifying the admissible assignments to the variables in $S$

An assignment $f:V\to D$ satisfies the instance if for every constraint $(S,R)\in C$ with $S=(x_1,\dots ,x_r)$, one has $(f(x_1),\dots ,f(x_r))\in R$. The constraint satisfaction problem asks whether there exists an assignment satisfying all constraints.

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.