CS计算机代考程序代写 algorithm 3a_Constraint_Satisfaction.dvi

3a_Constraint_Satisfaction.dvi

COMP9414 Constraint Satisfaction 1

This Lecture

� Constraint Satisfaction Problems (CSPs)

� Standard search methods

◮ Backtracking search and heuristics

◮ Forward checking and arc consistency

◮ Domain splitting and arc consistency

◮ Variable elimination

� Local search

◮ Hill climbing

◮ Simulated annealing

UNSW ©W. Wobcke et al. 2019–2021

COMP9414: Artificial Intelligence

Lecture 3a: Constraint Satisfaction

Wayne Wobcke

e-mail:w. .au

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 3

Example: Map Colouring

Western
Australia

Northern
Territory

South
Australia

Queensland

New South Wales

Victoria

Tasmania
Variables: WA, NT, Q, NSW, V, SA, T

Domains: Di = {red, green, blue}

Constraints: Adjacent regions have different colours (WA 6= NT, etc.)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 2

Constraint Satisfaction Problems

� Constraint Satisfaction Problems are defined by a set of variables Xi,

each with a domain Di of possible values, and a set of constraints C

� Aim is to find an assignment to each the variables Xi (a value from

the domain Di) such that all of the constraints C are satisfied

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 5

Example: n-Queens Puzzle

� Put n queens on n×n board so that no two queens attack one another

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 4

Example: Map Colouring

� Solution is an assignment that satisfies all the constraints

Western
Australia

Northern
Territory

South
Australia

Queensland

New South Wales

Victoria

Tasmania

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

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 7

Example: Cryptarithmetic

S E N D

+ M O R E

M O N E Y

Variables:

D E M N O R S Y

Domains:

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

Constraints:

M 6= 0, S 6= 0 (unary constraints)

Y = D+E or Y = D+E −10, etc.

D 6= E, D 6= M, D 6= N, etc.

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 6

n-Queens Puzzle as a CSP

Assume one queen in each column. Domains are possible positions of

queen in a column. Assignment is when each domain has one element.

Variables: Q1, Q2, Q3, Q4

Domains: Di = {1,2,3,4}

Constraints:

Qi 6= Q j (cannot be in same row)

|Qi −Q j| 6= |i− j| (or same diagonal)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 9

Example: Sudoku

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 8

Cryptarithmetic with Hidden Variables

We can add “hidden” variables to simplify the constraints

OWTF U R

+

OWT

OWT

F O U R

X
2

X
1

X
3

Variables: F T U W R O X1X2X3

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

Constraints:

AllDifferent(F,T,U,W,R,O)

O + O = R + 10·X1, etc.

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 11

Varieties of CSPs

Discrete variables

� Finite domains; size d ⇒ O(dn) complete assignments

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

� Infinite domains (integers, strings, etc.)

◮ Job shop scheduling, variables are start/end days for each job

◮ Need a constraint language, e.g. StartJob1 + 5 ≤ StartJob3

◮ Linear constraints solvable, nonlinear undecidable

Continuous variables

� e.g. start/end times for Hubble Telescope observations

� Linear constraints solvable in polynomial time by LP methods

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 10

Real World CSPs

� Assignment problems (e.g. who teaches what class)

� Timetabling problems (e.g. which class is offered when and where?)

� Hardware configuration (e.g. minimize space for circuit layout)

� Transport scheduling (e.g. courier delivery, vehicle routing)

� Factory scheduling (optimize assignment of jobs to machines)

� Gate assignment (assign gates to aircraft to minimize transit)

Many real world CSPs are also optimization problems

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 13

Backtracking Search

CSPs can be solved by assigning values to variables one by one, in

different combinations. Whenever a constraint is violated, go back to the

most recently assigned variable and assign it a new value.

Can be implemented using Depth First Search on a special kind of state

space, where states are defined by the values assigned so far

� Initial state: Empty assignment

� Successor function: Assign a value to an unassigned variable that

does not conflict with previously assigned values of other variables

� Goal state: All variables are assigned a value and all constraints are

satisfied

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 12

Types of Constraint

� Unary constraints involve a single variable

◮ M 6= 0

� Binary constraints involve pairs of variables

◮ SA 6= WA

� Higher-order constraints involve 3 or more variables

◮ Y = D+E or Y = D+E −10

� Inequality constraints on continuous variables

◮ EndJob1 + 5 ≤ StartJob3

� Soft constraints (Preferences)

◮ 11am lecture is better than 8am lecture!

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 15

Backtracking Search Example

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 14

Path Search vs Constraint Satisfaction

Important difference between path search problems and CSPs

� Constraint Satisfaction Problems (e.g. n-Queens)

◮ Difficult part is knowing the final state

◮ How to get there is easy

� Path Search Problems (e.g. Rubik’s Cube)

◮ Knowing the final state is easy

◮ Difficult part is how to get there

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 17

Problem with Backtracking Search

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 16

Backtracking Search Example

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 19

Improvements to Backtracking Search

General-purpose heuristics can give huge gains in speed

1. Which variable should be assigned next?

2. In what order should its values be tried?

3. Can inevitable failure be detected early?

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 18

Backtracking Search Space Properties

The search space has very specific properties

� If there are n variables, every solution is at depth exactly n

� Variable assignments are commutative

[WA = red then NT = green] same as [NT = green then WA = red]

Backtracking search can solve n-Queens for n ≈ 25

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 21

Degree Heuristic

� Tie-breaker among MRV variables

◮ Choose variable with most constraints on remaining variables

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 20

Minimum Remaining Values

� Minimum Remaining Values (MRV)

◮ Choose the variable with the fewest legal values

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 23

Constraint Graph

Binary CSP: Each constraint relates at most two variables

Constraint Graph: Nodes are variables, arcs show constraints

WA

NT

SA

Q

NSW

V

T

General-purpose CSP algorithms use the graph structure to speed up

search, e.g. Tasmania is an independent subproblem!

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 22

Least Constraining Value

� Given a variable, choose the least constraining value

◮ One that rules out the fewest values in the remaining variables

More generally, 3 allowed values would be better than 2, etc.

Combining these heuristics makes 1000-Queens feasible

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 25

Forward Checking

Idea: Keep track of remaining legal values for unassigned variables

Terminate search when any variable has no legal values

WA NT Q NSW V SA T

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 24

Forward Checking

Idea: Keep track of remaining legal values for unassigned variables

WA NT Q NSW V SA T

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 27

Forward Checking

Idea: Keep track of remaining legal values for unassigned variables

Terminate search when any variable has no legal values

WA NT Q NSW V SA T

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 26

Forward Checking

Idea: Keep track of remaining legal values for unassigned variables

Terminate search when any variable has no legal values

WA NT Q NSW V SA T

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 29

Arc Consistency

Simplest form of constraint propagation is arc consistency

Arc (constraint) X → Y is arc consistent if

for every value x in dom(X) there is some allowed y in dom(Y )

WA NT Q NSW V SA T

Make X → Y arc consistent by removing any such x from dom(X)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 28

Constraint Propagation

Forward checking propagates information from assigned to unassigned

variables, but doesn’t provide early detection for all failures

WA NT Q NSW V SA T

NT and SA cannot both be blue!

Constraint propagation repeatedly enforces constraints locally

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 31

Arc Consistency

Arc (constraint) X → Y is arc consistent if

for every value x in dom(X) there is some allowed y in dom(Y )

WA NT Q NSW V SA T

If X loses a value, neighbours of X need to be rechecked

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 30

Arc Consistency

Simplest form of constraint propagation is arc consistency

Arc (constraint) X → Y is arc consistent if

for every value x in dom(X) there is some allowed y in dom(Y )

WA NT Q NSW V SA T

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 33

Domain Splitting and Arc Consistency

States are whole CSPs (not partial assignments)

� Make CSP domain consistent and arc consistent

◮ Domain consistent = all unary constraints are satisfied

� To solve CSP using Depth First Search

◮ Choose a variable v with more than one value in domain

◮ Split the domain of v into two subsets

◮ This gives two smaller CSPs

◮ Make each CSP arc consistent (if possible)

◮ Solve each resulting CSP (or backtrack if unsolvable)

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 32

Arc Consistency

Arc (constraint) X → Y is arc consistent if

for every value x in dom(X) there is some allowed y in dom(Y )

WA NT Q NSW V SA T

Arc consistency detects failure earlier than forward checking

For some problems, it can speed up the search enormously

For others, it may slow the search due to computational overheads

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 35

Variable Elimination

� If there is only one variable, return the intersection of its (unary)

constraints

� Otherwise

◮ Select a variable X

◮ Join the constraints in which X appears, forming constraint R1

◮ Project R1 onto its variables other than X, forming R2

◮ Replace all of the constraints in which X appears by R2

◮ Recursively solve the simplified problem, forming R3

◮ Return R1 joined with R3

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 34

Constraint Optimization Problems

States are whole CSPs (not partial assignments) with costs

� Make CSP domain consistent and arc consistent

� Add CSP to priority queue

� To solve CSP using Greedy Search

◮ Remove CSP with minimal h from priority queue

◮ Choose a variable v with more than one value in domain

◮ Split the domain of v into two subsets

◮ This gives two smaller CSPs

◮ Make each CSP arc consistent (if possible) – add to priority queue

� cost(CSP) ≈ sum of costs to violate soft constraints

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 37

Variable Elimination Example

r1 : C 6= E C E

3 2

3 4

4 2

4 3

r2 : C > D C D

3 2

4 2

4 3

r3 : r1 ⊲⊳ r2 C D E

3 2 2

3 2 4

4 2 2

4 2 3

4 3 2

4 3 3

r4 : π{D,E}r3 D E

2 2

2 3

2 4

3 2

3 3

→֒ new constraint

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 36

Variable Elimination Example

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 39

Local Search

� Iterative Improvement

◮ Assign all variables randomly (possibly violating constraints)

◮ Change one variable at a time, trying to reduce the number of

violations at each step

◮ Greedy Search with h = number of constraints violated

h = 5 h = 2 h = 0

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 38

Variable Elimination Example

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 41

Plateaux and Local Optima

Sometimes, have to go sideways or even backwards to make progress

towards a globally optimal solution

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 40

Hill Climbing by Min-Conflicts

2

2

1

2

3

1

2

3

3

2

3

2

3

0

� Variable selection: randomly select any conflicted variable

� Value selection by min-conflicts heuristic

◮ Choose value that violates fewest constraints

◮ Can (often) solve n-Queens for n ≈ 10,000,000

UNSW ©W. Wobcke et al. 2019–2021

COMP9414 Constraint Satisfaction 43

Simulated Annealing

� Stochastic hill climbing based on difference between evaluation of

previous state (h0) and new state (h1)

◮ If h1 < h0, definitely make the change ◮ Otherwise, make the change with probability e−(h1−h0)/T where T is a “temperature” parameter � Reduces to ordinary hill climbing when T = 0 � Becomes totally random search as T → ∞ � Sometimes, gradually decrease value of T during search UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 42 Inverted View When minimizing violated constraints, it makes sense to think of starting at the top of a ridge and climbing down into the valleys UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 45 Summary � Much interest in CSPs for real-world applications � Backtracking = depth-first search with one variable assigned per node � Variable and value ordering heuristics help significantly � Forward checking helps by detecting inevitable failure early � Hill climbing by min-conflicts often effective in practice � Simulated annealing can help to escape from local optima � Which method(s) are best varies from one task to another! UNSW ©W. Wobcke et al. 2019–2021 COMP9414 Constraint Satisfaction 44 Phase Transitions in CSPs Given random initial state, hill climbing by min-conflicts with random restarts can solve n-Queens in almost constant time for arbitrary n with high probability (e.g. n = 10,000,000) Randomly-generated CSPs tend to be easy if there are very few or very many constraints, but become extra hard in a narrow range of the ratio R = number of constraints number of variables R CPU time critical ratio UNSW ©W. Wobcke et al. 2019–2021