CSP idea

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)

CSP definition

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)

Constrained graph

nodes are variables

edges are constraints

Binary constraints

Each constraint relates exactly two variables

Finite vs infinite CSP

finite: each variable has a finite domain of values

infinite: some variables have an infinite domain

Basic CSP algorithm:

Backtracking

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?

Critical questions for efficiency

which variable to assign?

which value to assign?

How to choose unassigned variable?

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

How to choose value to assign to variable?

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)

Forward checking

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

Forward cheking

failing condition

any variable has an empty domain

How to further improve forward checking

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

Constraint 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!

Arc consistency

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)

AC 3 algorithm

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

Exploit CSP structure

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

Can there be duplicated states in the backtracking search?

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

Strategy to encode CSPs

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

Last changeda year ago