CONSTRAINT SATISFACTION PROBLEMS(CSP)

Constraint satisfaction problems are specific class of AI problems used to solve the complex problems by finding a solution which satisfies the set of constraints imposed on the values or assignments of variables.

Some of the example problems which can be solved using CSP are scheduling, planning, resource allocation, sudoku solving and automated reasoning.

Definition: A Constraint Specification Problem is a specific category of problems in AI involves set of variables each of which can take a domain of possible values and set of constraints to be satisfied by the variables.

The goal of a CSP problem is to find a suitable value for each variable which satisfies all the constraints.

CSP is represented as a triple {X,D,C} where

X={x1,x2,x3,..} where X is a set of variables

D={D1,D2,D3,..} where each Di is the set of possible values of xi variable

C={C1,C2,C3,….} where Ci is the constraint that restricts the values that can be assigned to subset of variables.

CSP consists of 3 main components:

1. Variables

2. Domains

3. Constraints

Variables: Variables are used to represent entities or components of a problem for which values are to be assigned. Different variable types may be integer type, Boolean type, or categorical type. The choice of variables depends on the problem being solved.

Example: In scheduling problem time slots, tasks, resources, users are the variables.

In sudoku empty cells are the variables.

Set of variables are represented as X= {x1, x2, x3…}

Domains: Domain specifies the range or set of values a variable can take. Each variable in the CSP is associated with a domain. The domain restricts the values of the variables. The category of domain can vary depending on the nature of the problem being solved.

Some common domain categories are :

Finite Domain: In finite domains the variables can take only a set of discrete values.

Binary Domains: Variable may consist of only two values {0,1}

Integer Domain: Variable may consist of limited number of integer values like 1,2,3,4 etc.

Enumeration Domain consists of limited number of distinct values like “red, green and blue”

Ex: In graph coloring problem the domain is available colors.

Infinite domains have an infinite number of possible values, such as real numbers.

Ex: sine and cosine functions can take infinite domain values

Continuous Domain: Some CSPs contain variables whose domains are continuous values and can accept any real number falls in a given range.

Real-valued domains: Variables may accept any real number that falls within a given range like x[0,1] or x[1,100] etc..

Interval domains: Variable may accept any real number that falls with in a given an interval domain like xϵ[-П , П]

Example: In Sudoku the domain of empty cell is 1 to 9

In scheduling the domain of task is available time slots

Constraints: Constraints specify the conditions to be satisfied by the variables. Constraints restrict the combinations of values that a variable can take. Constraints are represented in the form of logical expressions, equations or functions.

There are several types of constraints. Some of the commonly used constraints are:

Unary Constraints: These constraints limit the possible values of a single variable without considering the values of other variables. It has only one parameter.

Ex : x1≠ 7 means x1 cannot have a value 7.

Binary Constraints: Binary constraints describe the relationship between two variables. It has only two parameters.

Ex: x1 < x2 indicates that x1 must be less than x2

Global constraints: Global constraints involve multiple variables and restrict more complex relationship between the variables. Generally, these constraints are used to capture higher level patterns, structures or rules. Global constraint enforces all variables in a set must take distinct values.

Ex: If two tasks are to be scheduled with one resource and two cannot be scheduled at a time then this is a global constraint.

Soft constraints: These are the constraints which can be violated to a certain degree. Based on the degree of violation soft constraints assign penalties and cost to the problem solving.

Solving the CSP problem with soft constraints involves optimization of the objective function to minimize the cost.

Example: In project scheduling, meeting deadlines is a hard constraint, but it can be delayed slightly if the cost is reduced.

Constraint Satisfaction Problem solving techniques:

1. Backtracking method

2. Constraint propagation method

3. Local Search method

Back tracking method:

Backtracking is a widely used technique for solving CSPs. It is a systematic search algorithm that explores possible assignments for variables. Its picks a variable, setting a value for it, and then recursively scanning through other variables. In the event of conflict, i.e. when it encounters constraints that cannot be satisfied it backtracks and tries a different value for preceding variable.

The backtracking algorithm’s essential elements are:

Variable Ordering: The order in which variables are chosen is known as variable ordering.

Value Ordering: The sequence in which values are assigned to variables is known as value ordering.

Constraint Propagation: Reducing the domain of variables based on constraint compliance is known as constraint propagation.

The back tracking algorithm follows these steps:

• Choose an unassigned variable.
• Select a value from its domain.
• Check if the assignment violates any constraints.
• If a constraint is violated, backtrack to the previous variable and try another value.
• Continue this process until all variables are assigned values, or a valid solution is found.

Forward Checking: The backtracking technique has been improved using forward checking. It tracks the remaining accurate values of the unassigned variables after each assignment and reduces the domains of variables whose values don’t match the assigned ones. As a result, the search space is smaller, and constraint propagation is more effectively accomplished.

Constraint Propagation:

Constraint propagation is a process of communicating the domain reduction of a decision variable for all other constraints stated over this variable. It narrows down the domains of variables by iteratively applying constraints. It’s often used in conjunction with backtracking to improve efficiency. The concept of constraint propagation can be illustrated as follows:

• Step 1: Start with an initial CSP problem in AI with variables, domains, and constraints.
• Step 2: Apply constraints that have been specified in the problem to narrow down the domains of variables.
• Step 3: After constraint propagation, some variables may have their domains reduced to only a few possibilities, making it easier to find valid assignments.
• Step 4: If a variable’s domain becomes empty during propagation, it indicates that the current assignment is inconsistent, and backtracking is needed.

Example:

Consider a simple CSP with two variables, X and Y, each with domains {1, 2, 3}, and a constraint X ≠ Y. Constraint propagation will iteratively reduce the domains as follows: If X is assigned 1, then Y cannot be 1, so Y’s domain becomes {2, 3}.

Local Search:

Local search algorithms in AI are the methods used to find the solutions to optimization problems where the search space is continuous, meaning its not limited to discrete values but rather spans a range of values.

In optimization problems the first step is to choose an objective function which needs to be optimized. This function maps each point in search space to real number to represent its fitness.

The search method starts with a randomly generated initial solution based on some heuristic and a part of search space.

The algorithm explores the neighborhood (which is adjacent in continuous space) of the current solution to find a better solution and evaluates for the maximization of objective function and selects one of the neighborhoods and moves to that solution towards an optimal or near-optimal point.

This algorithm continues till either for maximum number of iterations or maximum output value for optimization function or for a predefined time.

The drawback this algorithm is it may stick at local optimum value even though it is not a global optimum value. It can be overcome by random restarts or simulated annealing.

The performance of this algorithm depends on the size of the search space, neighborhood definition and shape of the objective function. These parameters are to be selected carefully to improve the efficiency.

Example:

N-Queens problem: In this problem all the N-queens are to be placed on

N x N chess board.

It can be represented as a CSP problem as below

N-Queens={Q,P,C}

Where Q is a set of queens Q={q1,q2,q3,q4}

P is set of positions for queens={{(1,1),(1,2),(1,3),(1,4)}, {(2,1),(2,2),(2,3),(2,4)}, {(3,1),(3,2),(3,3),(3,4)}, {(4,1),(4,2),(4,3),(4,4)}}

C is a set of constraints for all the queens that no two queens should attack each other.

C={No two queens should be in the same row,

No two queens should be in the same column,

No two queens should be in the diagonal}

Let us understand the process using local search and backtracking using constraint propagation

Local Search method:

Step1: Randomly select the solution state and check for constraints to validate whether the queens are correctly placed.

In the initial state there are 5 pairs of queens attacking each other shown by lines.

Step2 : We need to choose the neighboring node to move to reduce the conflicts.

Q1 has 3 conflicts

Q2 has 2 conflicts

Q3 has 2 conflicts

Q4 has 3 conflicts

Among these queens we need to choose the queen with maximum number of conflicts.

So either Q1 or Q4 is to be moved. Let Q1 is selected to move

This is not the solution state. There 2 pairs of queens are conflicting shown by lines.

Q3 , Q4,Q2 all have one conflict. choose one among them to move. Let Q4 choose to move

Now no two queens are conflicting each other.

If we validate for the final positions to place all the queens on the board.

1. All the queens are placed on the board

2. No two queens are conflicting.

This state is considered as the goal state or solution state to the 4-Queens problem.

Backtracking and constraint propagation approach to solve N-Queens problem:

N-Queens problem: In this problem all the N-queens are to be placed on NxN chess board.

It can be represented as a CSP problem as below

N-Queens={Q,P,C}

Where Q is a set of queens Q={q1,q2,q3,q4}

P is set of positions for queens={{(1,1),(1,2),(1,3),(1,4)}, {(2,1),(2,2),(2,3),(2,4)}, {(3,1),(3,2),(3,3),(3,4)}, {(4,1),(4,2),(4,3),(4,4)}}

C is a set of constraints for all the queens that no two queens should attack each other.

C={No two queens should be in the same row, No two queens should be in the same column,No two queens should be in the diagonal}

Step1: start with empty board and choose an unassigned variable. Q1

· Select a value from its domain.

P1 ={{(1,1),(1,2),(1,3),(1,4)}, {(2,1),(2,2),(2,3),(2,4)}, {(3,1),(3,2),(3,3),(3,4)}, {(4,1),(4,2),(4,3),(4,4)}}

Choose one position (1,1) and place Q1

initial state

• Check if the assignment violates any constraints.

There are no other queens assigned a position. So, there are no conflicts.

Now propagate the remaining constraints to the next variable.

Step2 : Choose another variable Q2

The domain for Q2 is P2. After adding some more constraints search space reduces and the domain becomes P2= {{(2,3),(2,4)}, {(3,2),(3,4)}, {(4,2),(4,3)}}

Constraints C2 for Q2= {cannot place queen in first row, cannot place queen in second row, cannot place 2 queens in same row or same column or diagonal}

Now choose first free place (2,3) and check whether there is any conflict

It is not same row or column with Q1. Choose that place.

Step 3: Choose another variable Q3

P3={{(3,2),(3,4)}, {(4,2),(4,3)}}

Constraints C3 for Q3= {cannot place queen in first row, cannot place queen in second row, cannot place 2 queens in same row or same column or diagonal, cannot place queen in 1st or 2nd row, cannot place queen in 1st or 2nd column}

so the domain for Q3 reduces to P={{(3,4)},{(4,3)}

choose first free position and place Q3

If a constraint is violated, backtrack to the previous variable, and try another value.

Now constraint is violated with Q3 and Q2 are becoming diagonal.

Now try to place the Q3 in (4,3)

This placement is also violating the constraint that no two queens can be placed in same column.

And there is no other place for Q3 . i.e the domain is exhausted.

Now backtrack to the previous variable i.e Q2 and try another value in its domain. The domain of Q2 is P2.

P2={{(2,3),(2,4)}, {(3,2),(3,4)}, {(4,2),(4,3)}} initially we have chosen (2,3). Now choose the next value(2,4)

Now the domain for Q3 changes to P3={{ {(3,2)}, {(4,2)}}

Choose first position and place Q3 in (3,2)

Now the domain for Q4 becomes only (4,3) which is also a conflict position.

Now we need to back track to Q1 and find the another position for Q1 whose domain is

P1=={{(1,1),(1,2),(1,3),(1,4)}, {(2,1),(2,2),(2,3),(2,4)}, {(3,1),(3,2),(3,3),(3,4)}, {(4,1),(4,2),(4,3),(4,4)}}

Choose (1,2) for Q1

Choose place for Q2 in {(2,4)}

• Continue this process until all variables are assigned values, or a valid solution is found.

Choose place for Q3 in {(3,1)}

Choose place for Q4 in {(4,3)} which is a final solution.

The solution for the Constraint Satisfaction Problems can be solved efficiently using backtracking algorithm in combination with constraint propagation method.

References:

Constraint Satisfaction Problems in Artificial Intelligence — Scaler Topics

Artificial Intelligence (ai) | Local search continuous spaces | #artificialintelligence (youtube.com)

Constraint Satisfaction Problem in AI (almabetter.com)

What is Constraint Satisfaction Problem in Artificial Intelligence? (intellipaat.com)

Lecture Notes on Local Search Algorithms (jarrar.info)