Constraint Satisfaction Problems

Question 1

State in CSP

Answer 1

state is defined by variables, X, with values from domain

Question 2

goal test in CSP

Answer 2

set of constraints specifying allowable combinations of values for subsets of variables

Question 3

Variable based model

Answer 3

Solution is not a path but an assignment of values for a set of variables that satisfy all constraints

Question 4

Complete solution

Answer 4

all variables are assigned values. Solutions are complete and consistent

Question 5

consistent solution

Answer 5

does not violate any constraints. Solutions are complete and consistent

Question 6

Constraint graph

Answer 6

nodes are varialbes, arcs are constraints

Question 7

Varieties of CSPs

Answer 7

discrete variables - finite and infinite domains

continuous variables

Question 8

unary constraints

Answer 8

constraints involve a single variable

Question 9

3 types of constraints

Answer 9

unary, binary, high order

Question 10

binary constraints

Answer 10

involve pairs of variables

Question 11

higher-order constraints

Answer 11

involve 3 or more variables

Question 12

apply local search for CSPs

Answer 12

allow states with some unsatisfied constraints; operators assign a value to a variable; variable selection, value selection

Question 13

min conflicts heuristic

Answer 13

choose value that violates the fewest constraints

Question 14

min-conflicts algorithm

Answer 14

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)

Question 15

Min Conflicts Algorithm Advantages

Answer 15

Simple and fast

Question 16

Min Conflicts Algorithm Disadvantages

Answer 16

Only searches states that are reachable from the initial state (might not search entire state space); does not allow worse moves; not complete

Question 17

CSP Tree Search Formulation

Answer 17

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

Question 18

Why isn’t cost important for CSP?

Answer 18

Find any solution

Question 19

every solution appears at depth

Answer 19

at depth n with n variables

Question 20

variable assignments are

Answer 20

commutative

Question 21

generate and test strategy

Answer 21

generate candidate solutions, then test if it satisfies all constraints

Question 22

How to improve DFS for CSP

Answer 22

backtracking with consistency checking

Question 23

backtracking with consistency checking for successors

Answer 23

don’t generate a successor that creates an inconsistency with any existing assignment - perform consistency checking when a node is generated

Question 24

back tracking with consistency checking successor function

Answer 24

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

Question 25

Backtracking with consistency checking algorithm

Answer 25

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

Question 26

Is backtracking search complete?

Answer 26

Yes; will find a solution if one exists, might expand the entire search space

Question 27

Summary of backtracking search

Answer 27

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

Question 28

How to improve backtracking efficiency?

Answer 28

Heuristics:

Which variable assigned next, what order of values tried, early detection of failure

Question 29

Which variable next?

Answer 29

Most constrained variable

Most constraining variable

Question 30

most-constrained variable

Answer 30

choose the variable with the fewest remaining moves, aka minimum remaining values heuristic; minimizes branching factor

Question 31

most-constraining variable

Answer 31

tie breaker for most constrained variable; choose the variable with the most constraints on the remaining variables; aka degree heuristic

Question 32

Which value next?

Answer 32

Least-constraining value

Question 33

least-constraining value

Answer 33

try to pick best values first; value that rules out the fewest values in the remaining variables

Question 34

Improve CSP

Answer 34

DFS with consistency checking/heuristics

Forward Checking

Question 35

Forward Checking

Answer 35

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

Question 36

Forward Checking Algorithm idea

Answer 36

keep track of remaining legal values for all variables; deaded when any variable has no legal values

Question 37

Why constraint propagation?

Answer 37

Forward checking propagates information from assigned to unassigned variables, but doesn’t provide early detection for all failures

Question 38

constraint propagation main idea

Answer 38

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

Question 39

arc consistency

Answer 39

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)

Question 40

Arc Consistency Algorithm

Answer 40

hold

Question 41

How to combine search with CSP:

Answer 41

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

Question 42

Combining Backtracking search with CSP algorithm

Answer 42

hold