Constraint Satisfaction Problem And Constraint Solving Strategies Computer Science Essay

Published:

Constraint Satisfaction Problem is an important problem in artificial intelligence and operations research. Many practical problems can be formulated as CSP, i.e., finding a consistent value assignment to variables subject to a set of constraints. This paper includes an initial definition of constraint satisfaction problem. Basically there two branches under the roof of constraint programming i.e. constraint satisfaction and constraint solvingThis paper attempts review of different techniques for constraint satisfaction, that have appeared in the literature like Systematic Search and Consistency Techniques.

Constraint satisfaction problem is a special kind of problem where we have to maintain a relation between the number of variables and the given domain. That is from the fixed domain we can give different values to the variables. For example simple graph coloring problem in which no 2 adjacent region can have same color. Suppose we have to color

a graph having 7 states with 4 colors red, green, blue and

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Yellow. So 7 states represent your variables and 4 colors

represent domain. This problem is solved by labeling each node with a variable and non equal constraint between each two variables labeling adjacent nodes. Hence constrain satisfaction problem has:-

Set of variables. {x1,x2,x3…xn}

Finite domain for each variable xi

Set of constraints {c1,c2,c3…cn}

Final result should be such that every variable will get a value which satisfies the constraints.

Constraint satisfaction is evolved from artificial intelligence. It has following properties such as:-

Constraint may have multiple values for one variable

Constraints can have relation between the variables from different domains

Constraints are non directional i.e. if x=y+2 then x can be calculated with given formula and y can also be calculated as y=x-2

Constraint is declarative, additive and partially independent of each other.

Constraint programming is nothing but after studying the constraints such as properties, requirements the programming should generate the solution which satisfy all constraints. This is successfully applied in computer graphics, database system, biology for DNA structure, circuit design, etc.

Varieties of CSPs:-

discrete variables such as variables with finite and infinite domains

continuous variables

unary i.e. containing only one variable

binary containing two variables

higher order containing 3 or more variables

We can use constraint satisfaction problem when problem can be expressed by set of variables, when constraints are simple, when constraints are propagating and when solutions are densely distributed in the space of possible assignments.

Constraint Satisfaction:-

The problem which can be solved by search in which due to constraint the values taken by variable gets reduced. The algorithm is generated in such a way that finds the solution or it reaches to the conclusion that there is no solution at all.

Constraint Solving:-

It uses the variables with infinite domain which is the main difference in constraint satisfaction and constraint solving. Instead of combination and search it uses mathematical methods.

Lot of problems can be solved by using constraint programming method such as N-Queen problem, Sudoku problem, and crypto-arithmetic problem.

N-Queen problem:-

It is well known problem in which we have to place N- Queens in N*N chessboard and the constraint is no Queen should threaten each other. Easy way to satisfy this constraint is to place the Queens in such a way that no 2 Queens should be in one row or column or diagonal.

Sudoku problem:-

Each Sudoku has a unique solution that can be reached logically without guessing. The constraint is we have to enter digits from 1 to 9 into the blank spaces. Every row must contain one of each digit. So must every column, as must every 3x3 square. Such 9 squares are present in the problem.

Crypt-arithmetic problem:-

Mathematical expression is given in which instead of numbers characters are used and we have to assign number to each character. The constraint is different characters should have different values

E.g. SEND+MORE=MONEY

We can add more constraints such that S≠0 and M≠0

Real world CSPs:-

Time Tabling, Course Scheduling, Job Shop Scheduling, Nurse Scheduling, Staff Scheduling, Transport Planning, Resource Allocation, Airport Counter Allocation, Warehouse Location, Network Configuration

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Conventional programming technique are very hard and time consuming as there are no constraints so search increases exponentially with program size.

e.g. Consider nurse scheduling problem in which 10 nurse are available and 3 shifts are there. So we try all possible permutations of all nurses in all shifts [5,7]. That is 310 combinations but now if we want to increase number of nurse and shifts to 20 and 4 respectively then combinations will be 420 and it is not possible to find optimal solution out of it. Now if we add some constraints like number of nurses in one shift or specialization of nurse then the search space reduces and problem becomes tractable.

Search methods are divided into two broad classes one traversing the space of partial solution and other that explore the space of complete value assignment.

Why to use CSP rather than mathematical expressions?

There are two reasons:-

CSP representation is closer to problem.

The algorithms used are very simple and can find solution more quickly.

Various aspects to be considered while dealing with CSP:-

Systematic search algorithm

Generates all possible value assignments then perform tests so that all constraints get satisfied.

Consistency techniques

Solution should be consistent and if not then the inconsistency should be detected as early as possible.

Constraint propagation

Constraint propagation [4,8] is the process of determining how the possible values of one variable affect the possible values of other variables i.e. by integrating Systematic search with consistency techniques e.g. forward checking, backtracking etc.

Variable and Value Ordering

The order in which the variables are considered is very important as it affects the efficiency [6].

Reduction in search

Systematic search like backtracking has alternative choices which degrades the performance so by selecting proper selection order of variables

Constraint optimization

Finding a solution satisfying all constraints and applying optimization on it in order to get a good solution.

Constraint Satisfaction Problem Solving Using Search:-

Systematic search algorithms are sound and complete that is either they find solution or come to the result that problem is insoluble. But only disadvantage is they take large time to do so.

Generate and Test :-

This method searches the space of complete assignments. First it generates some assignment of variables and then checks whether the value satisfies all constraints or not. If it is not satisfying all constraints then algorithm tries another assignment. The algorithm stops when the complete assignment is satisfying the constraints or the solution does not exist.

The algorithm uses the generator which returns all complete assignments in some specific order. The variables are labeled by the values from their respective domains then algorithm checks for constraint satisfaction or returns fail if no other assignment is remaining.

The disadvantage of this method is it generates many wrong assignments which gets rejected during checking phase. So to improve this algorithm 2 ways are:-

Generator of assignment should generate the assignments by removing the conflicts by performing local search

Generator should be combined with the tester so that validity of constraint can be checked at the time of assignment.

Backtracking:-

It is combination of generate and test phase and uses partial assignment. As soon as the variable is initialized the validity of constraint is checked and if the partial assignment violates any of the constraint then backtracking is done so variable can have alternate value assignment.

If inconsistency occurs then algorithm finds alternate unlabelled value and for searching such values various procedures are required so complexity increases [1].

There are 3 main drawbacks of this method:-

As the algorithm is not identifying the reason of failure repeated failure occurs due to same reason. This effect is called as thrashing and can be avoided using backjumping or intelligent backtracking [3].

As conflicting values are not remembered so backtracking has to perform redundant work for same conflicting variables [3].

It detects the conflict too late means it is not possible to detect the conflict before it occurs [3].

Backjumping:-

To avoid the thrashing problem backjumping is used [1,3]. Working is similar to backtracking, that is this algorithm picks one variable at a time and check that the new assignment is compatible with the constraint values. The only change is if this algorithm finds inconsistency then it analyses the situation and it uses the violated constraint as a guidance to find out the conflicting variable. Backjumping algorithm backtracks to most recent conflicting variable where backtracking backtracks to the immediate previous variable.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Backmarking:-

The disadvantage of backtracking 'redundant work' is eliminated by using the method of backmarking [3]. Both backmarking and Backtracking are useful for reducing the number of compatible checks. That is if Y is incompatible with X then it remembers this incompatibility and whenever X is used then Y is not considered again.

If a search path is extended by choosing a value for a variable X then backmarking is done at individual level. If inconsistency is detected then marking is done at that point in the search tree. 'Mark' is used with 'Back to' that is once conflict occurred that level is referred as mark and back to operation is carried out means all possible alternatives of marked variables are rejected.

Consistency Techniques:-

Here consider following example:

Let A<B be a constraint between the variable A with the domain DA=3,4,5,6,7 and the variable B with the domain DB=1,2,3,4,5. Visibly, for some values in DA there does not exist a consistent value in DB satisfying the constraint A<B and vice versa. Such values can be removed from respective domains without loss of any solution, i.e., the reduction is safe. We get reduced domains DA ={3,4} and DB={4,5}.

Note, that this reduction does not remove all inconsistent pairs necessarily, for example A=4, B=4 is still in domains, but for each value of A from DA it is possible to find a

consistent value of B and vice versa.

Binary CSP is represented as a constraint graph where each node is labeled by the variable and the edge between two nodes corresponds to the binary constraint binding the variables that label the nodes connected by the edge. Unary constraint can be represented by the cycle.

Node Consistency:-

It is the simplest consistency technique. The node representing a variable X in a constraint graph is node consistent if and only if for every value V in the current domain DX of X, each unary constraint on X is satisfied. A CSP is node consistent if and only if all variables are node consistent, i.e., for all variables all values in its domain satisfy the constraints on that variable.

If the domain DX of the variable X contains a value "a" that does not satisfy the unary constraint on X, then the instantiation of X to "a" will always result in an immediate failure. Thus, the node inconsistency can be eliminated by simply removing those values from the domain DX of each variable X that do not satisfy a unary constraint on X.

Arc Consistency:-

If the constraint graph is node consistent then unary constraints can be removed because they all are satisfied. As we are working with the binary CSP, there remains to ensure consistency of binary constraints. In the constraint graph, binary constraint corresponds to arc, therefore this type of consistency is called arc consistency [2,3].

An arc (Vi,Vj) is arc consistent if and only for every value x in the current domain of Vi which satisfies the constraints on Vi there is some value y in the domain of Vj such that Vi=x and Vj=y is permitted by the binary constraint between Vi and Vj. Note, that the concept of arc-consistency is directional, i.e., if an arc (Vi,Vj) is consistent, then it does not automatically mean that (Vj,Vi) is also consistent. A CSP is arc consistent if and only if every arc (Vi,Vj) in its constraint graph is arc consistent.

Clearly, an arc (Vi,Vj) can be made consistent by simply deleting those values from the domain of Vi for which there does not exist a corresponding value in the domain of Dj such that the binary constraint between Vi and Vj is satisfied (note, that deleting of such values does not eliminate any solution of the original CSP). The following algorithm does precisely that.

Directional Arc Consistency:-

In the above definition of arc consistency we mentioned a directional nature of arc consistency (for arc). Nevertheless, the arc consistency for CSP is not directional at all as each arc is assumed in both directions in the Arc Consistency algorithms. Although, the node and arc consistency algorithms seem easy they are still stronger than necessary for some problems, for example, for enabling backtrack-free search in CSPs which constraints form trees. Therefore yet simpler concept was proposed to achieve some form of consistency, namely, directional arc consistency that is defined under total ordering of the variables.

A CSP is directional arc consistent under an ordering of variables if and only if every arc (Vi,Vj) in its constraint graph such that i<j according to the ordering is arc consistent. Notice the difference between AC and DAC, in AC we check every arc (Vi,Vj) while in DAC only the arcs (Vi,Vj) where i<j are considered. Consequently, the arc consistency is stronger than directional arc consistency, i.e., arc consistent CSP is also directional arc consistent but not vice versa

And finally directional arc consistent is not necessarily arc consistent as well.

Path Consistency:-

Given that arc consistency is not enough to eliminate the need for backtracking, is there another stronger degree of consistency that may eliminate the need for search? The above example shows that if one extends the consistency test to two or more arcs, more inconsistent values can be removed. This is the main idea of path-consistency [3].

A path (V0, V1…Vm) in the constraint graph for CSP is path consistent if and only if for every pair of values x in D0 and y in Dm that satisfies all the constraints on V0 and Vm there exists a label for each of the variables V1,..., Vm-1 such that every binary constraint on the adjacent variables Vi, Vi+1 in the path is satisfied. A CSP is path consistent if and only if every path in its graph is path consistent.

Note carefully that the definition of path consistency for the path (V0, V1,..., Vm) does not require the values x0, x1,..., xm to satisfy all the constraints between variables V0, V1,..., Vm, In particular, the variables V1, V3 are not adjacent variables in the path (V0, V1,..., Vm), so the values x1, x3 needs not satisfy the constraint between V1, V3.

Naturally, a path consistent CSP is arc consistent as well because an arc is equivalent to the path of length 1. In fact, to make the arc (Vi,Vj) arc-consistent one can make the path (Vi,Vj,Vi) path-consistent.

Consequently, path consistency implies arc consistency. But the reverse is not true.

Directional Path Consistency:-

Similarly to weakening arc-consistency to directional arc-consistency we can weaken path-consistency to directional path consistency. The reason for doing this is also the same as in DAC. Sometimes, it is sufficient to achieve directional path-consistency which is computationally less expensive than achieving full path-consistency.

A CSP is directional path consistent under an ordering of variables if and only if for every two variables Vi and Vj each path (Vi,Vk,Vj) in its constraint graph such that k>i and k>j according to the ordering is path consistent.

Again, notice the difference between Path Consistency and Directional Path Consistency. In PC we check every path (Vi,Vk,Vj) while in DPC only the paths (Vi,Vk,Vj) where k>i and k>j are considered. Consequently, the path consistency is stronger than directional path consistency; however, it is less expensive to achieve directional path consistency. The following example shows that path consistency is strictly stronger than directional path consistency, i.e., PC removes more inconsistent values than DPC. It also shows that DPC can be even weaker then AC. However, DPC is at least as strong as DAC because if path (Vi,Vk,Vi) where i<k is pathconsistent then also the arc (Vi,Vk) is arc-consistent.

Conclusion

This paper has presented the Constraint Satisfaction Problem, and fundamental techniques to solve this type of problem. Some systematic search techniques were discussed, beginning with backtrack. Backjumping avoids thrashing problem present in backtracking by reucing the number of search nodes. Conversely, Backmark reduces the number of constraint checks.

Consistency Techniques pre-processes a CSP to reduce workload of subsequent search by filtering domain elements and /or modifying constraint. Enforcing Arc Consistency is popular technique due to its relative low cost. Enforcing pathe consistency modifies costraints to rule out inconsistent pairs of values.