Constraint Satisfaction Problems

(1)

Constraint Satisfaction

Problems

(2)

Sommario

n 

Constraint Satisfaction Problems (CSP)

Constraint Programming = rappresentazione e ricerca soluzione di CSP

n 

Backtracking search for CSPs

n 

Local search for CSPs

(3)

Constraint satisfaction problems (CSPs)

n  Standard search problem:

n  Stato: “scatola nera“ – any data structure that supports successor function, heuristic function, and goal test

n  CSP:

n  Stato definito da variablili X_i con valori in un dominio (cont o disc) D_i

n  goal test insieme di constraints che specifica combinazioni possibili di valori per sottoinsimi di variabili (constraints espliciti e impliciti)

n  Esempio 8-regine

n  Semplice esempio di linguaggio formale di rappresentazione

n  Permette lo sviluppo di general-purpose algorithms con più potere degli algoritmi standard di ricerca

(4)

Example: Map-Coloring

n  Variables WA, NT, Q, NSW, V, SA, T

n  Domains D_i = {red,green,blue}

n  Constraints: regioni adiacienti devono avere colori

n  Ad es., WA ≠ NT (implicito) o, esplicitamente, (WA,NT) in {(red,green), (red,blue),(green,red), (green,blue),(blue,red),(blue,green)}

(5)

Example: Map-Coloring

n 

Solutions are complete and consistent assignments, e.g., WA = red, NT = green,Q = red,NSW =

green,V = red,SA = blue,T = green

(6)

Constraint graph

n  Binary CSP: each constraint relates two variables

n  Constraint graph: nodes are variables, arcs are constraints

(7)

Varieties of CSPs

n  Discrete variables

n  finite domains:

n  n variables, domain size d ! O(dⁿ) complete assignments

n  e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete)

n  infinite domains:

n  integers, strings, etc.

n  e.g., job scheduling, variables are start/end days for each job

n  need a constraint language, e.g., StartJob₁ + 5 ≤ StartJob₃

n  Continuous variables

n  e.g., start/end times for Hubble Space Telescope observations

n  linear constraints solvable in polynomial time by linear programming

(8)

Varieties of constraints

n 

Unary constraints involve a single variable,

n  e.g., SA ≠ green

n 

Binary constraints involve pairs of variables,

n  e.g., SA ≠ WA

n 

Higher-order constraints involve 3 or more variables,

n  e.g., cryptarithmetic column constraints

(9)

Example: Cryptarithmetic

n  Variables:

F T U W R O X₁ X₂X₃

n  Domains: {0,1,2,3,4,5,6,7,8,9}

n  Constraints:

n  Alldiff (F,T,U,W,R,O) variabili tutte con valori diversi!

n  O + O = R + 10 · X₁

n  X₁ + W + W = U + 10 · X₂ X + T + T = O + 10 · X

hyper constraint graph

(10)

Many Real-world CSPs

n  Assignment problems

n  e.g., who teaches what class

n  Timetabling problems

n  e.g., which class is offered when and where?

n  Transportation scheduling

n  Factory scheduling

n  Boolean satisfiability

n  ….

n  Notice that many real-world problems involve real-valued

(11)

Standard search formulation (incremental)

Let's start with the straightforward approach, then fix it States are defined by the values assigned so far

n  Initial state: the empty assignment { }

n  Successor function: assign a value to an unassigned variable that does not conflict with current assignment

! fail if no legal assignments

n  Goal test: the current assignment is complete

1.  This is the same for all CSPs!

2.  Every solution appears at depth n with n variables à use depth-first search

3.  b = (n - l )d at depth l, hence n! · dⁿ leaves !!

(12)

Backtracking search

n  Variable assignments are commutative:

[ prima WA = red poi NT = green ] stessa cosa di:

[ prima NT = green poi WA = red ]

n  Only need to consider assignments to a single variable at each node à b = d and there are dⁿ leaves

n  Depth-first search for CSPs with single-variable assignments is called backtracking search

n  Backtracking search is the basic uninformed algorithm for CSPs

Can solve n-queens for n ≈ 25

(13)

Backtracking search

(14)

Backtracking example

(15)

Backtracking example

(16)

Backtracking example

(17)

Backtracking example

(18)

Improving backtracking efficiency

n 

General-purpose methods can give huge gains in speed:

n 

Which variable should be assigned next?

n 

In what order should its values be tried?

n 

Can we detect inevitable failure early?

(19)

Most constrained variable

n 

Most constrained variable:

Scegli la var con meno valori accettabili

n 

minimum remaining values (MRV) heuristic

(20)

Most constrain ing variable

n 

Criterio aggiuntivo di preferenza tra most constrained variables

n 

Most constraining variable (degree heuristic):

n 

Scegli la variabile con il maggior numero di vincoli

con le variabili rimanenti

(21)

Least constraining value

n 

Data una variabile, scegli il valore meno vincolante:

n 

the one that rules out the fewest values in the remaining variables

n 

Combining these heuristics makes 1000

queens feasible!

(22)

Forward checking

n  Idea:

n  Keep track of remaining legal values for unassigned variables

n  Terminate search when any variable has no legal values

(23)

Forward checking

n  Idea:

(24)

Forward checking

n  Idea:

(25)

Forward checking

n  Idea:

(26)

Constraint propagation (Inference)

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

n  NT and SA cannot both be blue!

n  Constraint propagation repeatedly enforces constraints locally

(27)

Arc consistency

n  Simplest form of propagation makes each arc consistent

n  X àY is consistent iff

for every value x of X there is some allowed y of Y

(28)

for every value x of X there is some allowed y of Y

Arc consistency

(29)

Arc consistency

for every value x of X there is some allowed y

n  If X loses a value, neighbors of X need to be rechecked

(30)

Arc consistency

for every value x of X there is some allowed y

n  If X loses a value, neighbors of X need to be rechecked

n  Arc consistency detects failure earlier than forward checking

n  Can be run as a preprocessor or after each assignment

(31)

Arc consistency algorithm AC-3

(32)

Backtraching with Inference

(33)

Esempio Sudoku: AC-3 utile?

(34)

Esempio Sudoku

n 

Formulare il problema come CSP (variabili, domini, vincoli)

n 

Applicare AC-3 al problema precedente:

provare ordine E6, I6, A6, ….

n 

Quanto è utile AC-3 nell’esempio?

(35)

Esercizio AC-3

n 

3 variabili: x, y, z

n 

Dom(x)={3,5}, Dom(y)={7}, Dom(z)={4,7}

n 

Vincoli: x ≠ y, x < z, y ≠ z

n 

AC(x,z): si/no?

n 

AC(z,x): si/no?

n 

AC(z,y): si/no?

n 

….

(36)

Esercizio AC-3: soluzione

n 

….

(37)

Local search for CSPs

n  Hill-climbing, simulated annealing typically work with

"complete" states, i.e., all variables assigned

n  To apply to CSPs:

n  allow states with unsatisfied constraints

n  operators reassign variable values

n  Variable selection: randomly select any conflicted variable

n  Value selection by min-conflicts (general) heuristic:

n  choose value that violates the fewest constraints

n  i.e., hill-climb with h(n) = total number of violated constraints

(38)

Example: 4-Queens

n  States: 4 queens in 4 columns (4⁴ = 256 states)

n  Actions: move queen in column

n  Goal test: no attacks

n  Evaluation: h(n) = number of attacks

n  Given random initial state, can solve n-queens in almost constant time for arbitrary n with high probability: n = 10.000.000 is solvable!!

(39)

Esempio: 8 regine

(40)

Local Search: Min-Conflic

n 

Funziona molto bene quando il problema contiene molte soluzioni

n 

Usato per schedulare le osservazioni del telescopio Spaziale Hubble:

Drastica riduzione dei costi computazionali: una

settimana di osservazioni schedulata in 10 minuti

(prima in tre settimane!)

(41)

Da arc-consistency a n -consistency

n  Estensione del concetto di arc(2)-consistenza

n  3-consistenza:

per ogni tripla (X,Y,Z):

per ogni (X=v, Y=w) che soddisfa C_xy Esiste Z=k tale che

C_xz e C_zy sono soddisfatti

n  Anche chiamata path-consistenza perchè considera un cammino da X a Y attraverso Z

n  Imporre la path-consistenza vuol dire eliminare gli

assegnamenti a X e Y che non soddisfano la proprietà, cioè

(42)

Esempi di 3-consistenza (1)

n  Si consideri il problema colorazione mappa australia con due colori: blu e rosso

n  Il CSP ha soluzione?

n  Imporre la proprietà di arc-consistency al CSP come modifica I domini?

n  Il CPS arc-consistente è anche path-consistente?

n  Se non lo è come si modificano i vincoli binari? (Cioè gli assegnamenti binari ammessi dai relativi vincoli)

(43)

Esempi di 3-consistenza (3)

n  Si consideri il seguente CSP:

X <= Y, Y < Z, X <= Z

Dom(X)={1,2}, Dom(Y)={1,3}, Dom(Z)={2,4}

n  E’ arc-consistente?

n  E’ path-consistente?

n  Se non lo è, quali sono gli assegnamenti binari da rimuovere?

(44)

K-consistenza e strong consistency

n  La 1-2-3 consistenza si generalizza a k-consistenza con k>=1:

Ogni assegnamento consistente per X1, …, X(k-1) può essere esteso a un assegnamento consistente per

X1, …, Xk

n  Strong k-consistency:

vale q-concistency per ogni valore di q in {1…k}

n  Theorema: Se il CSP ha n variabili e vale strong n-consistency allora posso trovare soluzione, se esiste, con un algoritmo

polinomiale (alla lavagna)

(45)

Summary

n  CSPs are a special kind search problem:

n  Molte applicazioni

n  states defined by values of a fixed set of variables

n  goal test defined by constraints on variable values

n  Backtracking = depth-first search with one variable assigned per node

n  Variable ordering and value selection heuristics help significantly

n  Forward checking prevents assignments that guarantee later failure

n  Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies

n  Iterative min-conflicts is usually effective in practice