Constraint Satisfaction Problems Flashcards
State in CSP
state is defined by variables, X, with values from domain
goal test in CSP
set of constraints specifying allowable combinations of values for subsets of variables
Variable based model
Solution is not a path but an assignment of values for a set of variables that satisfy all constraints
Complete solution
all variables are assigned values. Solutions are complete and consistent
consistent solution
does not violate any constraints. Solutions are complete and consistent
Constraint graph
nodes are varialbes, arcs are constraints
Varieties of CSPs
discrete variables - finite and infinite domains
continuous variables
unary constraints
constraints involve a single variable
3 types of constraints
unary, binary, high order
binary constraints
involve pairs of variables
higher-order constraints
involve 3 or more variables
apply local search for CSPs
allow states with some unsatisfied constraints; operators assign a value to a variable; variable selection, value selection
min conflicts heuristic
choose value that violates the fewest constraints
min-conflicts algorithm
Assign each variable a random value, defining the inital state
While state is not consistent: pic a variable that has a constraint violated, find a value for the variable that minimizes the total number of violated constraints (ver all variables)
Min Conflicts Algorithm Advantages
Simple and fast
Min Conflicts Algorithm Disadvantages
Only searches states that are reachable from the initial state (might not search entire state space); does not allow worse moves; not complete
CSP Tree Search Formulation
initial state: empty assignment
successor function: assign a value to an unassigned variable
goal test: the current assignment is complete: all variables assigned a value and all constraints satisfied
Why isn’t cost important for CSP?
Find any solution
every solution appears at depth
at depth n with n variables
variable assignments are
commutative
generate and test strategy
generate candidate solutions, then test if it satisfies all constraints
How to improve DFS for CSP
backtracking with consistency checking
backtracking with consistency checking for successors
don’t generate a successor that creates an inconsistency with any existing assignment - perform consistency checking when a node is generated
back tracking with consistency checking successor function
assigns a value to an unassigned variable that does not conflict with all current assignments (fails if no legal assignments); the uninformed search of CSPs
Backtracking with consistency checking algorithm
Start with empty state
while not all vars in state assigned a value:
pick a variable, if it has a value that does not violate any constraints, then assign that value
else: go back to previous variable and assign it another value
Is backtracking search complete?
Yes; will find a solution if one exists, might expand the entire search space
Summary of backtracking search
depth first search algorithm: goes down 1 variable at a time, at deadend, backs up to the last variable whose value can be changed w/o violating constraints and changes it, if you backed up to root and tried all values, then no solutions
How to improve backtracking efficiency?
Heuristics:
Which variable assigned next, what order of values tried, early detection of failure
Which variable next?
Most constrained variable
Most constraining variable
most-constrained variable
choose the variable with the fewest remaining moves, aka minimum remaining values heuristic; minimizes branching factor
most-constraining variable
tie breaker for most constrained variable; choose the variable with the most constraints on the remaining variables; aka degree heuristic
Which value next?
Least-constraining value
least-constraining value
try to pick best values first; value that rules out the fewest values in the remaining variables
Improve CSP
DFS with consistency checking/heuristics
Forward Checking
Forward Checking
At start, record set of all possible legal values for it; when assign a value to variable, update the set of legal values for all unassigned variables; backtrack immediately if empty set of possible values
Forward Checking Algorithm idea
keep track of remaining legal values for all variables; deaded when any variable has no legal values
Why constraint propagation?
Forward checking propagates information from assigned to unassigned variables, but doesn’t provide early detection for all failures
constraint propagation main idea
When you delete a value from a variable’s domain, check all variables connected to it; if any of them change, delete all inconsistent values connected to them; etc
arc consistency
x->y is consistent iff:
for every value x at X there is some allowed y, if not, delete x (if x loses a vlue, all neighbors of X need to be rechecked)
Arc Consistency Algorithm
hold
How to combine search with CSP:
at each node in DFS search assign a selected value to a selected variable; run CSPto reduce variables’ domains and check if any inconsistencies arise as a result of this assignment
Combining Backtracking search with CSP algorithm
hold
