Consider a CSP problem. v Apply backtracking search. If backtracking search successful returns a solution else, a failure state which return a procedure recursive-backtracking. v Procedure recursive-backtracking starts with empty set and takes input as CSP problem. If complete assignment possible or assignment done then return actual assignment. v Variable is assigned a specific value. v The relative constraint is a set which is taken as input. v If value is complete and consistent according to constraints then assign value to variable, add that to list. v Call the recursive backtracking until result or failure is reached.
Every time recursive-backtracking sustains result (i.e. assignment.) v If result is failure then remove variable with specific value from assignment. It will return failure status.
Limitations of Backtracking
A success function is generated with above algorithm. But backtracking is not effective for very large problems. v The general performance is not so good. Domain specific heuristic function combined with uninformed search algorithm can generate better searching result. Improvement in Backtracking Search
We can also solve CSP without knowing the domain-specific knowledge. Here we need to design a module which resolve following queries:-
Which variable is assigned in next step and what order values can be tried? v Impact of current variable assignments on unassigned variables. v Avoidance of known failed path in the potential paths.
Commutative Problem
A problem is commutative if the order of application of any given set of actions has no effect on the outcome. This is the case for CSPs because, when assigning values to variables, we reach the same partial assignment, regardless of order. Therefore, all CSP search algorithms generate successors by considering possible assignments for only a single variables at each node in the search tree.
For example -
In graph-colouring problem, if vertex 1 is coloured with red then vertex 2 (adjacent to vertex
- will have two choices either green or blue but never red.
Selection of Next Unassigned Variable
Any general purpose method for solving CSP suffers from making a choice of next unassigned variable.
Variable and Value Ordering
Choosing a variable is critical to performance. v The efficiency of search algorithms depends considerably on the order in which variables are considered for instantiations. v This ordering affects the efficiency of the algorithm.
There exist various heuristics for dynamic or static ordering of values and variables. Techniques for selecting next best unassigned variable
- Minimum Remaining Values (MRV)
- It is also called as "Most constrained variable or fail-first heuristic".
- Backtracking combined with MRV gives better performance.
- Rule: Choose a variable with the fewest legal moves.
- It answers-Which variable shall we try first?
Degree heuristic
- It helps to choose next better state.
- Rule: Select variable involved in highest number constraints on other unassigned variable.
- Degree heuristic is very useful as a tie breaker among MRV variable.
- It answers-In what order should variable values can be tried?
Least constraining value
- The least constraining value is also effective method in some application.
- Rule: Choose the least constraining value from many variable i.e. the one that leaves the maximum flexibility for subsequent variable assignment.
- It can be combined with MRV for fast selection.
Passing Information through Constraints
While selecting unassigned variable for computation if we look at some of the constraints earlier in the search (or even before search begins), we can drastically reduce search space. Following are techniques which are helpful for earlier constraints checks.
Forward Checking (FC)
Forward checking is one of the potential technique which uses constraints more effectively during search. v It removes values in neighbouring unassigned variables domain that conflict with assigned variable. v Forward checking uses MRV to select assigned variable. v Backtracking search is performed if failure occurs. v Search terminates when any variable has no legal values. v Generic method, Ø Assigns variable 𝑋.
Forward checking remarks unassigned variable 𝑌 connected to 𝑋. Ø Remove values from D, where value is inconsistent with 𝑋. Constraint Propagation
A combined approach of heuristic plus forward checking gives more reliable, accurate and efficient results than a singular approach. v The forward checking propagates information from assigned to unassigned variables but can’t avoid or detect all failure. v Constraint propagation repeatedly enforces constraints locally. v The idea of arc consistency provides a fast method of constraint propagation that is substantially stronger than forward checking. Here "arc" refers to a directed arc in the constraint graph. Constraint Propagation using Arc Consistency
It is fast method of constraint propagation. v X→Y is consistent if (for every value of X there is some allowed value Y. For example [ V₂ → V₁, is consistent iff V₁ = Red, V₂ = Blue] (i.e. for every value of x in X there is some allowed value y in Y ). This is directed property example −[V₁ = V₂]
V₁ = V₂ is consistent if V₁ = Red and V₂ = Blue
As directed arcs between variables represent the domains of specified variables, they are consistent with each other. v Constraint propagation can be applied as preprocessing or propagation step. Ø Before search-Preprocessing. Ø After search-Propagation. v The procedure for maintaining arc consistency, can be applied repeatedly. Constraint Propagation using K-consistency
Arc consistency is not capable of detecting all inconsistencies. Partial assignments [ V₁ = Red, V₂ = Red] are inconsistent. v K-consistency is very strong form of constraint propagation. v A CSP is K-consistency if for any set of K − 1 variables and for any consistent assignment to those variable a consistent value can always be assigned to any Kth variable.
Local Search for CSP
It is most powerful search for CSP's. v Backtrack search require more time in dynamic environment which can be reduced by local search. v It uses complete state formulation as follows : -
a) The initial state which assigns value to every variable. b) Successor function alters value of one variable for each instance. c) For example - 8-queen problem Initial state: A random configuration of 8-queens in 8 columns. Successor function: Function 1: It picks one queen and moved to elsewhere in its columns. OR Function 1: Each column can have queen in a permutations of the 8 rows.
1 MIN-CONFLICTS Algorithm for Solving CSPs by Local Search
- Min-conflict heuristic select new value that result in a minimum number of conflicts with the other variable.
- The initial state may be choosen randomly or by a greedy assignment process that chooses a minimal-conflict value for each variable in turn.
- The conflicts procedure that counts the number of constraints violated by a particular value, given the rest of the current assignments.
The Algorithm
MIN-CONFLICTS Inputs: CSP, a constraint satisfaction problem. Max-steps, the number of steps allowed before giving up. Output: A solution or failure. Current-An initial complete assignment for CSP. for i = 1 to max-steps do If current is a solution for CSP then return current. var-a randomly chosen conflicted variable from VARIABLE [CSP]. value-the value v for var that minimizes CONFLICTS (var, v, current, csp). set var = value in current. return failure.
Advantages of Min-conflict
The key feature is that the runtime required for min-conflict is independent of problem size. For example-It can solve million-queen problem in an average 50 steps. v It also works for hard-problems. v Local search is also used in an online setting. For Example-in scheduling problem like weekly outline schedule.
Example-of Min conflict Consider 4-queen example shown in Fig. 1.18 in 3 parts (a), (b), (c).
Fig. 1.18 Min conflict example.
[Figure depicts how ' ℎ ' value changes per step]
Dealing with Special Constraints
Realistic problem has very special type (real in nature) of constraints which occurs frequently. Example -
All-diff constraints: It enforces the rule that all the variable in state space must have distinct values (as in the crypto arithmetic problem). v Almost constraints or resource constraints:
These are most important higher order constraints.
It bounds propagation for large value domains which are widely used in practical constraint problem.
Intelligent Backtracking
We observed in forward checking if inconsistency or failure occurs then we need to apply backtracking.
If backtracking is done efficiently then we can reduced total time. Chronological Backtracking
- It is one of the standard form (i.e. try different value for preceding variable).
- In chronological backtracking most latest decision points are always revisited.
- It has potential to back, up to preceding variable.
- A more intelligent approach to backtracking is to go all the way back to one of the set of variables that caused the failure. This set is called the conflict set; for example, in map colouring problem, the conflict set for M is {N, NW, NE}, where N, MW, NE are already coloured regions. In general, the conflict set for variable X is the set of previously assigned variables that are connected to X by constraints.
- The back jumping method backtracks to the most recent variable in the conflict set. If no legal value is found, it should return the most recent element of the conflict set along with the failure indicator.
Structure of a Problem (Which can be used for Finding Quick Solution)
A technique to represent a problem in simple way, is to decompose the problem in to many sub -problems.
Sub-problems can be independent or they can be connected. If the sub-problems are totally independent then we have very easy way to solve the problem in totality. We can solve each sub-problem independently and then combine the solutions.
Many practical CSP sub-problems are connected. The simple case is when the constraint graph forms a tree. Any two variables are connected by almost one path.
Algorithm for Solving Tree-Structured CSP in Linear Time
Choose any variable as the root of the tree, and order the variables from the root to the leaves in such a way that every node's parent in the tree precedes it in the ordering. v Label the variables 𝑋₁,…,𝑋𝑛 in order. Now, every variable except the root has exactly one parent variable.
Consider following example,
a) The constraint graph of a tree-structure CSP is, Fig. 1.19 Constraint graph.
b) A linear ordering of the variables consistent with the tree with V₁ as the root. Refer Fig.
1.20.
Fig. 1.20 Linear ordering of variables.
- For 𝑗 from 𝑛 down to 2, apply arc consistency to the arc (𝑋𝑖, 𝑋𝑗) where 𝑋𝑖 is the parent of 𝑋𝑗, removing values from domain [𝑋𝑖] as necessary.
- For 𝑗 from 1 to 𝑛, assign any value for 𝑋𝑗 consistent with the value assigned far 𝑋𝑖, where 𝑋𝑖, is the parent of 𝑋𝑗. Note: The complete algorithm runs in time 𝐎(nd²).
Graph Structured CSP If we can reduce graph to a tree then solving graph structured CSP would be better in terms of time. Reducing a graph to tree can be done in two ways.
- Remove the nodes.
- Collapse the nodes.
Remove the Nodes Approach (Cutset Conditioning)
Choose a subset S from VARIABLES [csp] such that constraint graph becomes a tree after removal of S. S is called as a cycle cutset. v For each possible assignment to the variables in 𝑆 that satisfies all constraints on 𝑆,
i) Remove from the domains of the remaining variables any values that are inconsistent with the assignment for S.
ii) If the remaining CSP has a solution, return it together with the assignment for S.
Note:
If the cycle cutset has size 𝐶, then the total runtime is 𝑂(𝑑𝑐, (𝑛 − 𝑐)𝑑²).
If the graph is "nearly a tree" then c will be small and the savings over straight backtracking will be huge.
For example –
Consider the following graph,
If we remove 𝑉₃ then the constraint graph is,
Collapse the Node (Tree Decomposition) Approach
The approach is based on constructing a tree decomposition of the constraint graph into a set of connected sub-problems. v Each sub-problem is solved independently and the resulting solutions are then combined. v A tree decomposition must satisfy the following three requirements: Ø Every variable in the original problem appears in at least one of the sub-problems. Ø If two variables are connected by a constraint in the original problem, they must
appear together (along with the constraint) in at least one of the sub-problems. Ø If a variable appears in two sub-problems in the tree, it must appear in every subproblems along the path connecting those sub-problems. v A given constraint graph admits many tree decompositions. In choosing a decomposition, the aim is to make the sub-problems as small as possible. v The tree width of a tree decomposition of a graph is one less than the size of the largest sub-problem; the tree width of the graph itself is defined to be the minimum tree width among all its tree decompositions. v CSPs with constraint graphs of bounded tree width, are solvable in polynomial time. Unfortunately, finding the decomposition with minimal tree width is NP-hard, but there are heuristic methods that work well in practice. For example – Consider the following graph,
A tree decomposition of above graph is,