CSP

• search algorithms so far requrie domain specific knowledge (heuristics)

• more generic approach: sates are expressed by certain variables and values which are assigned to them

  • each variable has a set of potential values (=domain)

• a state is a goal state, if constraints on variables are met

Idea: Try to find assignement to variables s.t. all constraints are fullfilled

-> formulate each problem in terms of a CSP, no domain specific knowledge needed

• Start with emtpy set of assignments

• in each depth of tree, take a free variable

  • for a free variable, assign a value of the domain

  • check if this value conflicts with the constraint

    • yes: check next

    • no: go deeper into the tree

  • all values conflict with constraints: backtrack

Minimum remaining values (MRV):

Use variable, which has the smallest number of potential values

(slides: most constrained variable)

Tie breaker:

Use variable, which has the highest number of remaining constraints

(slides: most constraining varaible)

-> prunes big parts of the tree; minimiize branching factor

Least constraining value (LCV):

Choose value, which rules out the fewest values in the remaining variables.

-> only useful, if we want to find one solution (not helpful if all solutions must be found)

If we assign a value for X:

• look through all unassigned neighbors Y of X

• eliminate all values for Y, which conflict with the chosen value for X

• any variable has an empty set of potential values

using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for another variable

-> can be done before the actual search!

-> can also be done during search!

• variable is arc-consistent, if all values in its domain satisfies its (binary) constraints

  • need to check if for each possible value of X, if its neighbors Y can be assigned a value matching the constraints between X and Y

• a network is arc-consistent, if all its nodes are arc-consistent (with respect to their neighbors)

• reduces the domains for each variables of a CSP

• if any domain is empty -> failure

• 
  

• put all (binary) constraints into a queue

• fore each constraint (X, Y):

  • remove value from domain of X, if there is no value in the domain of Y to satsify the constraint

  • check if domain of X has changed:

    • yes: append all constraints of X to queue (except (X,Y))

    • no: keep going