CSP example: map coloring

[Pages:11]Constraint Satisfaction Problems (CSPs)

Russell and Norvig Chapter 6

CSP example: map coloring

Given a map of Australia, color it using three colors such that no neighboring territories have the same color.

October 13, 2014

2

CSP example: map coloring

Constraint satisfaction problems

n A CSP is composed of:

q A set of variables X1,X2,...,Xn with domains (possible values) D1,D2,...,Dn

q A set of constraints C1,C2, ...,Cm q Each constraint Ci limits the values that a subset of variables can

take, e.g., V1 V2

October 13, 2014

3

October 13, 2014

4

Constraint satisfaction problems

n A CSP is composed of:

q A set of variables X1,X2,...,Xn with domains (possible values) D1,D2,...,Dn

q A set of constraints C1,C2, ...,Cm q Each constraint Ci limits the values that a subset of variables can

take, e.g., V1 V2

In our example: n Variables: WA, NT, Q, NSW, V, SA, T n Domains: Di={red,green,blue} n Constraints: adjacent regions must have different colors.

q E.g. WA NT (if the language allows this) or q (WA,NT) in {(red,green),(red,blue),(green,red),(green,blue),(blue,red),

(blue,green)}

October 13, 2014

5

Constraint satisfaction problems

n A state is defined by an assignment of values to some or all variables.

n Consistent assignment: assignment that does not violate the constraints.

n Complete assignment: every variable is mentioned. n Goal: a complete, legal assignment.

{WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green}

10/13/14

6

1

Constraint satisfaction problems

n Simple example of a formal representation language n CSP benefits

q Standard representation language q Generic goal and successor functions q Useful general-purpose algorithms with more power than

standard search algorithms, including generic heuristics n Applications:

q Time table problems (exam/teaching schedules) q Assignment problems (who teaches what)

October 13, 2014

7

Varieties of CSPs

n Discrete variables q Finite domains of size d O(dn) complete assignments.

n The satisfiability problem: a Boolean CSP

q Infinite domains (integers, strings, etc.) n Continuous variables

q Linear constraints solvable in poly time by linear programming methods (dealt with in the field of operations research).

n Our focus: discrete variables and finite domains

October 13, 2014

8

Varieties of constraints

n Unary constraints involve a single variable. q e.g. SA green

n Binary constraints involve pairs of variables. q e.g. SA WA

n Global constraints involve an arbitrary number of variables. n Preference (soft constraints) e.g. red is better than green often

representable by a cost for each variable assignment; not considered here.

October 13, 2014

9

Constraint graph

n Binary CSP: each constraint relates two variables n Constraint graph: nodes are variables, edges are

constraints

October 13, 2014

10

Example: cryptarithmetic puzzles

October 13, 2014

The constraints are represented

by a hypergraph

11

CSP as a standard search problem

n Incremental formulation

q Initial State: the empty assignment {}. q Successor: Assign value to unassigned variable provided

there is no conflict. q Goal test: the current assignment is complete.

n Same formulation for all CSPs !!! n Solution is found at depth n (n variables).

q What search method would you choose?

October 13, 2014

12

2

Backtracking search

n Observation: the order of assignment doesn't matter

can consider assignment of a single variable at a time. Results in dn leaves (d: number of values per variable).

n Backtracking search: DFS for CSPs with singlevariable assignments (backtracks when a variable has no value that can be assigned)

n The basic uninformed algorithm for CSP

Sudoku solving

1 2 3 4 5 6 7 8 9

A B C D E F G H I

October 13, 2014

13

10/13/14

14

Sudoku solving

Constraints:

A

B

Alldiff(A1,A2,A3,A4,A5,A6,A7,A8,A9) C

... Alldiff(A1,B1,C1,D1,E1,F1,G1,H1,I1) ...

D E

Alldiff(A1,A2,A3,B1,B2,B3,C1,C2,C3) F

...

G

H

Can be translated into constraints

I

between pairs of variables.

1 2 3 4 5 6 7 8 9

10/13/14

15

Sudoku solving

1 2 3 4 5 6 7 8 9

A B C D E F G H I

Let's see if we can figure the value of the center grid point.

Images from wikipedia and

10/13/14

16

Solving Sudoku

"In this essay I tackle the problem of solving every Sudoku puzzle. It turns out to be quite easy (about one page of code for the main idea and two pages for embellishments) using two ideas: constraint propagation and search."

Peter Norvig



10/13/14

17

Constraint propagation

n Enforce local consistency n Propagate the implications of each constraint

October 13, 2014

18

3

Arc consistency

n X Y is arc-consistent iff for every value x of X there is some allowed value y of Y

n Example: X and Y can take on the values 0...9 with the constraint: Y=X2. Can use arc consistency to reduce the domains of X and Y: q X Y reduce X's domain to {0,1,2,3} q Y X reduce Y's domain to {0,1,4,9}

October 13, 2014

19

The Arc Consistency Algorithm

function AC-3(csp) returns false if an inconsistency is found and true otherwise inputs: csp, a binary csp with components {X, D, C} local variables: queue, a queue of arcs initially the arcs in csp while queue is not empty do (Xi, Xj) REMOVE-FIRST(queue) if REVISE(csp, Xi, Xj) then if size of Di=0 then return false for each Xk in Xi.NEIGHBORS ? {Xj} do add (Xk, Xi) to queue

function REVISE(csp, Xi, Xj) returns true iff we revise the domain of Xi revised false for each x in Di do if no value y in Dj allows (x,y) to satisfy the constraints between Xi and Xj then delete x from Di revised true return revised

October 13, 2014

20

Arc consistency limitations

n X Y is arc-consistent iff for every value x of X there is some allowed y of Y

n Consider mapping Australia with two colors. Each arc is consistent, and yet there is no solution to the CSP.

n So it doesn't help

October 13, 2014

21

Path Consistency

n Looks at triples of variables

q The set {Xi, Xj} is path-consistent with respect to Xm if for every assignment consistent with the constraints of Xi, Xj, there is an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}

n The PC-2 algorithm achieves path consistency

10/13/14

22

K-consistency

n Stronger forms of propagation can be defined using the notion of k-consistency.

n A CSP is k-consistent if for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.

n Not practical!

Backtracking example

October 13, 2014

23

October 13, 2014

24

4

Backtracking example

Backtracking example

October 13, 2014

25

October 13, 2014

26

Backtracking example

October 13, 2014

Improving backtracking efficiency

n General-purpose methods/heuristics can give huge gains in speed:

q Which variable should be assigned next? q In what order should its values be tried? q Can we detect inevitable failure early?

27

October 13, 2014

28

Backtracking search

function BACKTRACKING-SEARCH(csp) return a solution or failure return RECURSIVE-BACKTRACKING({} , csp)

function RECURSIVE-BACKTRACKING(assignment, csp) return a solution or failure

if assignment is complete then return assignment var SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp) for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do

if value is consistent with assignment according to CONSTRAINTS[csp] then

add {var=value} to assignment result RECURSIVE-BACTRACKING(assignment, csp) if result failure then return result remove {var=value} from assignment return failure

October 13, 2014

29

Most constrained variable

var SELECT-UNASSIGNED-VARIABLE(csp)

Choose the variable with the fewest legal values (most constrained variable) a.k.a. minimum remaining values (MRV) or "fail first" heuristic q What is the intuition behind this choice?

October 13, 2014

30

5

Most constraining variable

Least constraining value heuristic

n Select the variable that is involved in the largest number of constraints on other unassigned variables.

n Also called the degree heuristic because that variable has the largest degree in the constraint graph.

n Often used as a tie breaker e.g. in conjunction with MRV.

October 13, 2014

31

n Guides the choice of which value to assign next. n Given a variable, choose the least constraining value:

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

q why?

October 13, 2014

32

Forward checking

Forward checking

n Can we detect inevitable failure early? q And avoid it later?

n Forward checking: keep track of remaining legal values for unassigned variables.

n Terminate search direction when a variable has no legal values.

October 13, 2014

33

n Assign {WA=red} n Effects on other variables connected by constraints with WA

q NT can no longer be red q SA can no longer be red

October 13, 2014

34

Forward checking

Forward checking

n Assign {Q=green} n Effects on other variables connected by constraints with WA

q NT can no longer be green q NSW can no longer be green q SA can no longer be green

October 13, 2014

35

n If V is assigned blue n Effects on other variables connected by constraints with WA

q SA is empty q NSW can no longer be blue n FC has detected that partial assignment is inconsistent with the constraints and backtracking can occur.

October 13, 2014

36

6

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 {1,2,3,4}

X2 {1,2,3,4}

X3 {1,2,3,4}

X4 {1,2,3,4}

October 13, 2014

37

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 {1,2,3,4}

X2 {1,2,3,4}

X3 {1,2,3,4}

X4 {1,2,3,4}

October 13, 2014

38

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 {1,2,3,4}

X2 { , ,3,4}

X3 { ,2, ,4}

X4 { ,2,3, }

October 13, 2014

39

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 {1,2,3,4}

X2 { , ,3,4}

X3 { ,2, ,4}

X4 { ,2,3, }

October 13, 2014

40

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 {1,2,3,4}

X2 { , ,3,4}

X3 { , , , }

X4 { ,2,3, }

October 13, 2014

41

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 {1,2,3,4}

X3 {1,2,3,4}

X4 {1,2,3,4}

October 13, 2014

42

7

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, ,3, }

X4 {1, ,3,4}

October 13, 2014

43

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, ,3, }

X4 {1, ,3,4}

October 13, 2014

44

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, , , }

X4 {1, ,3, }

October 13, 2014

45

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, , , }

X4 {1, ,3, }

October 13, 2014

46

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, , , }

X4 { , ,3, }

October 13, 2014

47

Example: 4-Queens Problem

1 2 3 4 1 2 3 4

X1 { ,2,3,4}

X2 { , , ,4}

X3 {1, , , }

X4 { , ,3, }

October 13, 2014

48

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download