04 CSP

• so far we used domain-sepecific heuristics to evauluates states, which can be hard to come up with

• CSPs are a more generic approach to search algorithms

• CSPs ony use general-purpose heuristics which help to solve wide varity of problems efficiently (without domain-specific heuristics)

• set of variables X_i

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

• constraints among varialbes

State:

• variables with assigned values

Goal state:

• complete (each variable is assinged)

• consistent (all constraints hold)

• nodes are variables

• edges are constraints

Each constraint relates exactly two variables

finite: each variable has a finite domain of values

infinite: some variables have an infinite domain

• states are a set of variable assignments

  • inital state is {}

• DFS

• in each step of DFS assign value to one variable

  • value must be in domai of variable

  • value must not conflict with constraints

  • if not possible -> backtrack

• goal test:

  • all variables assigned?

• which variable to assign?

• which value to assign?

Minimum remaining values (MRV):

• Use variable, which has the smallest number of potential values

Tie breaker:

• Use variable, which has the highest number of remaining constraints

-> 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 variables Y, which have constraints with X

• reduce the domains of Y based on the assigned values

• any variable has an empty domain

• forward checking only updates the related variables based on the latest assignment

• forward checking does not early detect failures:

  • e.g. as a result of forward checking there might be a state which can not be resolved without violating constraints

-> constrainted propagation

recusrive approach:

using the constraints to reduce the domain for a variable, which in turn can reduce the domain for another variable

-> can be done before the actual search!

-> can also be done during search!

• simplest form of constraint propagation

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

  • for all values in domain of X: each neighbor Y can be assinged a value without conflict

  • if X loses a value -> all neighbors need to be re-checked

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

• 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

Reduce complexity if CSP has certain structure:

• if constraint graph consist of several components:

  • solve each graph on its own -> reduce state space

• if constrait graph is a tree:

  • backtracking can be avoided

  • linear runtime in size of variables

• no, because in each depth we assign a value to one variable

• hence, there is exactly one path in the tree to a certain state

• try to assign numbers so variables

• then you can “compute” numerically with variables, e.g.:

  “blue house next to the green” -> abs(blue - green) = 1