CSP Search
AIMA 6.3-6.4
CMPSC 442
Week 5, Meeting 15, Four Segments
Outline
● CSP Backtracking Search
● CSP Search Heuristics
● Local Search for CSPs
● The Structure of CSP Problems
2Outline, Wk 5, Mtg 15
CSP Search
AIMA 6.3-6.4
CMPSC 442
Week 5, Meeting 15, Segment 1 of 4: CSP Backtracking
Introducing CSP as Search
● A CSP can easily be expressed as a search problem
○ Initial State: the empty assignment {}
○ Successor function: Assign a value to any unassigned variable provided
that there is not a constraint conflict
○ Goal test: the current assignment is complete
○ Path cost: a constant cost for every step
● If a solution exists, it is necessarily at depth n, given n variables
○ Depth First Search can be used
CSP Backtracking Search 4
Backtracking Search (Includes Inference)
● Depth-first search for CSPs with single-variable assignments is called
backtracking search
● In CSP, variable assignments are commutative, meaning it does not
matter what order the assignments are made
○ [step 1: WA = red; step 2: NT = blue] = [step 1: NT = blue; step 2: WA = red]
● Given the commutativity of any sequence of assignments, the number
of leaves for a CSP with n variables of domain size d = dn
○ In other words, one solution path p of length n is equivalent to all n!
permutations of p
CSP Backtracking Search 5
Backtracking Search Pseudo Code
CSP Backtracking Search 6
Backtracking Search Tree for Map-Coloring
CSP Backtracking Search 7
Backtracking Solution to Sudoku
8CSP Backtracking Search
https://commons.wikimedia.org/wiki/File:Sudoku_solved_by_bactracking.gif#/media/File:Sudoku_solved_by_bactracking.gif
CSP Search
AIMA 6.3-6.4
CMPSC 442
Week 5, Meeting 15, Segment 2 of 4: CSP Heuristics
Backtracking Search Heuristics
● Exploits domain-independent heuristics (in contrast to the
domain-dependent heuristics of informed search algorithms)
● Demonstrates the advantages of a factored state representation
● Four kinds of heuristics
○ Which variable to assign next: Select-Unassigned-Variable()
○ What inferences to perform at each step: Inference()
○ How far to backtrack: Backtrack()
○ When to save and re-use partial results
CSP Search Heuristics 10
Minimum Remaining Values (MRV) Heuristic
● Select a variable to assign with the fewest legal values,
meaning the most constrained variable
● Identifies a potential conflict early, if no value can be
assigned
11CSP Search Heuristics
Degree Heuristic
● Select the variable to assign that participates in the largest number of
contraints with other variables (highest degree in the constraint graph)
○ Reduces branching factor on remaining variables
○ Very effective for picking which state to color first: SA
12CSP Search Heuristics
Least Constraining Value Heuristic
● Used for ordering the domain values (see backtracking pseudo-code)
● Intuition: ensure maximum flexibility for remaining assignments
○ Given WA=red, NT = green, where Q is the next variable:
■ Q=blue would eliminate last possible value for SA
13CSP Search Heuristics
Inference during Search, using Forward Checking
● Whenever a variable Xi is assigned, for each variable Xj connected to
Xi by a constraint, delete from the domain of Xj any value that is
inconsistent with the value chose for Xi
14CSP Search Heuristics
Inference during Search, using Forward Checking
● Whenever a variable Xi is assigned, for each variable Xj connected to
Xi by a constraint, delete from the domain of Xj any value that is
inconsistent with the value chose for Xi
15CSP Search Heuristics
Inference during Search, using Forward Checking
● Whenever a variable Xi is assigned, for each variable Xj connected to
Xi by a constraint, delete from the domain of Xj any value that is
inconsistent with the value chose for Xi
16CSP Search Heuristics
Inference during Search, using Forward Checking
● Whenever a variable Xi is assigned, for each variable Xj connected to
Xi by a constraint, delete from the domain of Xj any value that is
inconsistent with the value chose for Xi
17
● Terminate! No assignment for SA
CSP Search Heuristics
MAC Algorithm: Maintaining Arc Consistency
● Unlike AC-3, forward checking does not recursively propagate
constraints when domains of variables are changed
● Solution: combine AC-3 and forward checking
○ After making an assignment to Xi
■ Find subset Y = all arcs (Xi,Xj)
● Call AC-3 on Y
18CSP Search Heuristics
Chronological Backtracking Can Fail
● Given an assignment Q=red, NSW=green, V=blue, T=red
○ There is no legal assignment for SA
○ Backtracking to most recent assignment to reassign T does not help
19CSP Search Heuristics
Improved Backtracking: Backjumping
● Identify a variable’s conflict set
○ Variable assignments that are in conflict
○ Conflict set for SA: {Q=red, NSW=green, V=blue}
● Jump back to reassign the most recently assigned variable in the
conflict set: V=blue
20CSP Search Heuristics
Forward Checking versus Backjumping
● Forward checking can build the conflict set
○ When forward checking from an assignment X = v deletes v from the
domain of Y, add X=v to the conflict set for Y
○ If the last value is deleted the domain of Y then the assignments in the
conflict set for Y are added to the conflict set of X (since the assignment
X=v leads to a contradiction in Y try a new assignment for X
● Notice that backjumping finds the same conflicts that forward checking
does
21CSP Search Heuristics
Conflict-directed backjumping
● Consider {WA = red, NSW = red}
○ Any assignment of NT, SA, Q and V will fail
○ Therefor, backjump to the last assignment before assigning any of
NT, SA, Q and V, which is NSW = red
● Let Xj be the current variable with conflict set conf(Xj)
○ If all values for Xj fail, backjump to the most recent variable Xi in
conf(Xj) and recompute the conflict set for Xi as follows:
22CSP Search Heuristics
Constraint Learning
● If a partial assignment is encountered that leads to
failure (e.g., {WA = red, NT = green, Q = blue}) during
a search, save the information
○ NoGood({WA = red, NT = green, Q = blue})
● Then it won’t be tried again
● Modern CSP solvers gain in efficiency through use
of constraint learning
23CSP Search Heuristics
CSP Search
AIMA 6.3-6.4
CMPSC 442
Week 5, Meeting 15, Segment 3 of 4: Local Search for
CSPs
Local Search for CSPs
● Local search algorithms such as hill-climbing and simulated annealing
can apply to CSPs using complete state formulation
○ Each state assigns a value to every variable
○ The search changes one variable at a time
● Variable selection: randomly select any conflicted variable
● Value selection by min-conflicts heuristic:
○ Choose a value that violates the fewest constraints
○ Apply hill-climb with h(n) = total number of violated constraints
25Local Search for CSPs
Hill Climbing CSP for 8-Queens
● Board 1: randomly place 8 queens, choose queen in col 8 to move next, label
each new position with number of attacking queens
● Board 2: col 8 queen has moved to row 3 (first row with only 1 conflict);
randomly choose col 6 queen, label positions with number of attacking queens
● Board 3: col 6 queen moved to row 8. SOLVED (IN TWO STEPS)!
26Local Search for CSPs
Pseudo Code for Min Conflicts Algorithm
27Local Search for CSPs
Efficiency of CSP Local Search
● Not counting the initial placement of n-queens, the run-time of
min-conflicts is independent of the size of n!
○ Solves 106-queens in ~50 steps
○ The reason it works well is that solutions are densely distributed
throughout the state space
28Local Search for CSPs
CSP Search
AIMA 6.3-6.4
CMPSC 442
Week 5, Meeting 15, Segment 4 of 4: Structure of CSP
Problems
Structure of CSP Problems
● Examination of the CSP graph can be used to solve problems more
quickly
○ Independent subproblems
○ Tree-structured CSPs
● Patterns of values can also help solve problems
30
Independent Subproblems
● Connected components of a constraint graph constitute independent
problems
○ If assignment Si is a solution of CSPi, then ∪Si is a solution of ∪CSPi
○ Reduction of complexity: if each CSPi has c variables from a total of n, then
there are n/c subproblems, each with complexity dc, where d is the size of
the domain, giving O(dcn/c) which is linear in n, instead of O(dn) which is
exponential in n
● Connected components of CSPs are rare ☹
31Structure of CSP Problems
Tree-structured CSPs
● A tree-structured CSP can be solved in time linear in the # of variables
● A constraint graph is a tree when any pair of variables is connected by
only one path
● Do a topological sort of the CSP graph to create a tree
○ A linear ordering of the nodes where for every directed edge Xi, Xj , Xi
precedes Xj
32Structure of CSP Problems
Cycle Cutsets
● Given the efficiency of tree-structured CSPs, turn other CSP graphs into trees
● A cycle cutset S of a graph G: any subset of vertices of G that, if removed,
leaves G a tree
○ EG: Assign a value v to SA, then remove v from domains of remaining variables; SA
is a cycle cutset that can be removed,, leaving a forest of trees
33Structure of CSP Problems
Cycle Cutset Algorithm
● Choose some cutset S
● For each possible assignment to the variables in S that satisfies all
constraints on S
○ Remove any values for the domains of the remaining variables that are not
consistent with S
○ If the remaining CSP has a solution, then you have are done
● For graph size n, domain size d
● Time complexity for cycle cutset of size c:
○ O(dc * d2(n-c)) = O(dc+2 (n-c))
34Structure of CSP Problems
Summary
● CSPs represent a state with variable/value pairs, and conditions on a
solution as constraints. Many real-world problems can be cast as CSPs
● While CSPs are NP-complete, many CSPs can be solved
● Inference techniques (node, path, arc or k-consistency) rule out variable
assignments (constraint propagation)
● Backtracking search interleaved with inference can be used for CSPs
● Heuristics that are general to any CSP can improve efficiency, such as
minimum remaining values, degree, least-constraining value
● Local search using min-conflicts heuristic is very effective
● Tree-structured CSPs can be solved in linear time
35Summary Wk 5, Mtg 15