CSP_8968662

Содержание

Слайд 2

What is search for?

Assumptions: single agent, deterministic, fully observable, discrete environment
Search for

What is search for? Assumptions: single agent, deterministic, fully observable, discrete environment
planning
The path to the goal is the important thing
Paths have various costs, depths
Search for assignment
Assign values to variables while respecting certain constraints
The goal (complete, consistent assignment) is the important thing

Слайд 3

Constraint satisfaction problems (CSPs)

Definition:
State is defined by variables Xi with values from

Constraint satisfaction problems (CSPs) Definition: State is defined by variables Xi with
domain Di
Goal test is a set of constraints specifying allowable combinations of values for subsets of variables
Solution is a complete, consistent assignment
How does this compare to the “generic” tree search formulation?
A more structured representation for states, expressed in a formal representation language
Allows useful general-purpose algorithms with more power than standard search algorithms

Слайд 4

Example: Map Coloring

Variables: WA, NT, Q, NSW, V, SA, T
Domains: {red,

Example: Map Coloring Variables: WA, NT, Q, NSW, V, SA, T Domains:
green, blue}
Constraints: adjacent regions must have different colors e.g., WA ≠ NT, or (WA, NT) in {(red, green), (red, blue), (green, red), (green, blue), (blue, red), (blue, green)}

Слайд 5

Example: Map Coloring

Solutions are complete and consistent assignments, e.g., WA = red,

Example: Map Coloring Solutions are complete and consistent assignments, e.g., WA =
NT = green, Q = red, NSW = green, V = red, SA = blue, T = green

Слайд 6

Example: n-queens problem

Put n queens on an n × n board with

Example: n-queens problem Put n queens on an n × n board
no two queens on the same row, column, or diagonal

Слайд 7

Example: N-Queens

Variables: Xij
Domains: {0, 1}
Constraints:
Σi,j Xij = N
(Xij, Xik) ∈ {(0, 0),

Example: N-Queens Variables: Xij Domains: {0, 1} Constraints: Σi,j Xij = N
(0, 1), (1, 0)}
(Xij, Xkj) ∈ {(0, 0), (0, 1), (1, 0)}
(Xij, Xi+k, j+k) ∈ {(0, 0), (0, 1), (1, 0)}
(Xij, Xi+k, j–k) ∈ {(0, 0), (0, 1), (1, 0)}

Xij

Слайд 8

N-Queens: Alternative formulation

Variables: Qi
Domains: {1, … , N}
Constraints:
∀ i, j non-threatening (Qi

N-Queens: Alternative formulation Variables: Qi Domains: {1, … , N} Constraints: ∀
, Qj)

Q2

Q1

Q3

Q4

Слайд 9

Example: Cryptarithmetic

Variables: T, W, O, F, U, R
X1, X2
Domains: {0, 1,

Example: Cryptarithmetic Variables: T, W, O, F, U, R X1, X2 Domains:
2, …, 9}
Constraints:
O + O = R + 10 * X1
W + W + X1 = U + 10 * X2
T + T + X2 = O + 10 * F
Alldiff(T, W, O, F, U, R)
T ≠ 0, F ≠ 0

X2 X1

Слайд 10

Example: Sudoku

Variables: Xij
Domains: {1, 2, …, 9}
Constraints:
Alldiff(Xij in the same unit)

Xij

Example: Sudoku Variables: Xij Domains: {1, 2, …, 9} Constraints: Alldiff(Xij in the same unit) Xij

Слайд 11

Real-world CSPs

Assignment problems
e.g., who teaches what class
Timetable problems
e.g., which class is offered

Real-world CSPs Assignment problems e.g., who teaches what class Timetable problems e.g.,
when and where?
Transportation scheduling
Factory scheduling
More examples of CSPs: http://www.csplib.org/

Слайд 12

Standard search formulation (incremental)

States:
Variables and values assigned so far
Initial state:
The empty

Standard search formulation (incremental) States: Variables and values assigned so far Initial
assignment
Action:
Choose any unassigned variable and assign to it a value that does not violate any constraints
Fail if no legal assignments
Goal test:
The current assignment is complete and satisfies all constraints

Слайд 13

Standard search formulation (incremental)

What is the depth of any solution (assuming n

Standard search formulation (incremental) What is the depth of any solution (assuming
variables)?
n (this is good)
Given that there are m possible values for any variable, how many paths are there in the search tree?
n! · mn (this is bad)
How can we reduce the branching factor?

Слайд 14

Backtracking search

In CSP’s, variable assignments are commutative
For example, [WA = red then

Backtracking search In CSP’s, variable assignments are commutative For example, [WA =
NT = green] is the same as [NT = green then WA = red]
We only need to consider assignments to a single variable at each level (i.e., we fix the order of assignments)
Then there are only mn leaves
Depth-first search for CSPs with single-variable assignments is called backtracking search

Слайд 19

Backtracking search algorithm

Making backtracking search efficient:
Which variable should be assigned next?
In what

Backtracking search algorithm Making backtracking search efficient: Which variable should be assigned
order should its values be tried?
Can we detect inevitable failure early?

Слайд 20

Which variable should be assigned next?

Most constrained variable:
Choose the variable with the

Which variable should be assigned next? Most constrained variable: Choose the variable
fewest legal values
A.k.a. minimum remaining values (MRV) heuristic

Слайд 21

Which variable should be assigned next?

Most constrained variable:
Choose the variable with the

Which variable should be assigned next? Most constrained variable: Choose the variable
fewest legal values
A.k.a. minimum remaining values (MRV) heuristic

Слайд 22

Which variable should be assigned next?

Most constraining variable:
Choose the variable that imposes

Which variable should be assigned next? Most constraining variable: Choose the variable
the most constraints on the remaining variables
Tie-breaker among most constrained variables

Слайд 23

Which variable should be assigned next?

Most constraining variable:
Choose the variable that imposes

Which variable should be assigned next? Most constraining variable: Choose the variable
the most constraints on the remaining variables
Tie-breaker among most constrained variables

Слайд 24

Given a variable, in which order should its values be tried?

Choose the

Given a variable, in which order should its values be tried? Choose
least constraining value:
The value that rules out the fewest values in the remaining variables

Слайд 25

Given a variable, in which order should its values be tried?

Choose the

Given a variable, in which order should its values be tried? Choose
least constraining value:
The value that rules out the fewest values in the remaining variables

Which assignment for Q should we choose?

Слайд 26

Early detection of failure

Apply inference to reduce the space of possible assignments

Early detection of failure Apply inference to reduce the space of possible
and detect failure early

Слайд 27

Early detection of failure

Apply inference to reduce the space of possible assignments

Early detection of failure Apply inference to reduce the space of possible
and detect failure early

Слайд 28

Early detection of failure: Forward checking

Keep track of remaining legal values for unassigned

Early detection of failure: Forward checking Keep track of remaining legal values
variables
Terminate search when any variable has no legal values

Слайд 29

Early detection of failure: Forward checking

Keep track of remaining legal values for unassigned

Early detection of failure: Forward checking Keep track of remaining legal values
variables
Terminate search when any variable has no legal values

Слайд 30

Early detection of failure: Forward checking

Keep track of remaining legal values for unassigned

Early detection of failure: Forward checking Keep track of remaining legal values
variables
Terminate search when any variable has no legal values

Слайд 31

Early detection of failure: Forward checking

Keep track of remaining legal values for unassigned

Early detection of failure: Forward checking Keep track of remaining legal values
variables
Terminate search when any variable has no legal values

Слайд 32

Early detection of failure: Forward checking

Keep track of remaining legal values for unassigned

Early detection of failure: Forward checking Keep track of remaining legal values
variables
Terminate search when any variable has no legal values

Слайд 33

Constraint propagation

Forward checking propagates information from assigned to unassigned variables, but doesn't

Constraint propagation Forward checking propagates information from assigned to unassigned variables, but
provide early detection for all failures
NT and SA cannot both be blue!
Constraint propagation repeatedly enforces constraints locally

Слайд 34

Simplest form of propagation makes each pair of variables consistent:
X ?Y is

Simplest form of propagation makes each pair of variables consistent: X ?Y
consistent iff for every value of X there is some allowed value of Y

Arc consistency

Consistent!

Слайд 35

Simplest form of propagation makes each pair of variables consistent:
X ?Y is

Simplest form of propagation makes each pair of variables consistent: X ?Y
consistent iff for every value of X there is some allowed value of Y

Arc consistency

Слайд 36

Simplest form of propagation makes each pair of variables consistent:
X ?Y is

Simplest form of propagation makes each pair of variables consistent: X ?Y
consistent iff for every value of X there is some allowed value of Y
When checking X ?Y, throw out any values of X for which there isn’t an allowed value of Y
If X loses a value, all pairs Z ? X need to be rechecked

Arc consistency

Слайд 37

Arc consistency

Simplest form of propagation makes each pair of variables consistent:
X ?Y

Arc consistency Simplest form of propagation makes each pair of variables consistent:
is consistent iff for every value of X there is some allowed value of Y
When checking X ?Y, throw out any values of X for which there isn’t an allowed value of Y
If X loses a value, all pairs Z ? X need to be rechecked

Слайд 38

Arc consistency

Simplest form of propagation makes each pair of variables consistent:
X ?Y

Arc consistency Simplest form of propagation makes each pair of variables consistent:
is consistent iff for every value of X there is some allowed value of Y
When checking X ?Y, throw out any values of X for which there isn’t an allowed value of Y
If X loses a value, all pairs Z ? X need to be rechecked

Слайд 39

Simplest form of propagation makes each pair of variables consistent:
X ?Y is

Simplest form of propagation makes each pair of variables consistent: X ?Y
consistent iff for every value of X there is some allowed value of Y
When checking X ?Y, throw out any values of X for which there isn’t an allowed value of Y

Arc consistency

Слайд 40

Simplest form of propagation makes each pair of variables consistent:
X ?Y is

Simplest form of propagation makes each pair of variables consistent: X ?Y
consistent iff for every value of X there is some allowed value of Y
When checking X ?Y, throw out any values of X for which there isn’t an allowed value of Y
Arc consistency detects failure earlier than forward checking
Can be run before or after each assignment

Arc consistency

Слайд 41

Arc consistency algorithm AC-3

Arc consistency algorithm AC-3

Слайд 42

Does arc consistency always detect the lack of a solution?

There exist stronger

Does arc consistency always detect the lack of a solution? There exist
notions of consistency (path consistency, k-consistency), but we won’t worry about them

Слайд 43

Tree-structured CSPs

Certain kinds of CSPs can be solved without resorting to backtracking

Tree-structured CSPs Certain kinds of CSPs can be solved without resorting to
search!
Tree-structured CSP: constraint graph does not have any loops

Source: P. Abbeel, D. Klein, L. Zettlemoyer

Слайд 44

Algorithm for tree-structured CSPs

Choose one variable as root, order variables from root

Algorithm for tree-structured CSPs Choose one variable as root, order variables from
to leaves such that every node's parent precedes it in the ordering

http://cs188ai.wikia.com/wiki/Tree_Structure_CSPs

Слайд 45

Algorithm for tree-structured CSPs

Choose one variable as root, order variables from root

Algorithm for tree-structured CSPs Choose one variable as root, order variables from
to leaves such that every node's parent precedes it in the ordering
Backward removal phase: check arc consistency starting from the rightmost node and going backwards

http://cs188ai.wikia.com/wiki/Tree_Structure_CSPs

Слайд 46

Algorithm for tree-structured CSPs

Choose one variable as root, order variables from root

Algorithm for tree-structured CSPs Choose one variable as root, order variables from
to leaves such that every node's parent precedes it in the ordering
Backward removal phase: check arc consistency starting from the rightmost node and going backwards
Forward assignment phase: select an element from the domain of each variable going left to right. We are guaranteed that there will be a valid assignment because each arc is consistent

http://cs188ai.wikia.com/wiki/Tree_Structure_CSPs

Слайд 47

Algorithm for tree-structured CSPs

If n is the numebr of variables and m

Algorithm for tree-structured CSPs If n is the numebr of variables and
is the domain size, what is the running time of this algorithm?
O(nm2): we have to check arc consistency once for every node in the graph (every node has one parent), which involves looking at pairs of domain values

Слайд 48

Nearly tree-structured CSPs

Cutset conditioning: find a subset of variables whose removal makes

Nearly tree-structured CSPs Cutset conditioning: find a subset of variables whose removal
the graph a tree, instantiate that set in all possible ways, prune the domains of the remaining variables and try to solve the resulting tree-structured CSP
Cutset size c gives runtime O(mc (n – c)m2)

Source: P. Abbeel, D. Klein, L. Zettlemoyer

Слайд 49

Algorithm for tree-structured CSPs

Running time is O(nm2) (n is the number of

Algorithm for tree-structured CSPs Running time is O(nm2) (n is the number
variables, m is the domain size)
We have to check arc consistency once for every node in the graph (every node has one parent), which involves looking at pairs of domain values
What about backtracking search for general CSPs?
Worst case O(mn)
Can we do better?

Слайд 50

Computational complexity of CSPs

The satisfiability (SAT) problem:
Given a Boolean formula, is there

Computational complexity of CSPs The satisfiability (SAT) problem: Given a Boolean formula,
an assignment of the variables that makes it evaluate to true?
SAT is NP-complete
NP: class of decision problems for which the “yes” answer can be verified in polynomial time
An NP-complete problem is in NP and every other problem in NP can be efficiently reduced to it (Cook, 1971)
Other NP-complete problems: graph coloring, n-puzzle, generalized sudoku
It is not known whether P = NP, i.e., no efficient algorithms for solving SAT in general are known

Слайд 51

Local search for CSPs

Start with “complete” states, i.e., all variables assigned
Allow

Local search for CSPs Start with “complete” states, i.e., all variables assigned
states with unsatisfied constraints
Attempt to improve states by reassigning variable values
Hill-climbing search:
In each iteration, randomly select any conflicted variable and choose value that violates the fewest constraints
I.e., attempt to greedily minimize total number of violated constraints

h = number of conflicts

Слайд 52

Local search for CSPs

Start with “complete” states, i.e., all variables assigned
Allow

Local search for CSPs Start with “complete” states, i.e., all variables assigned
states with unsatisfied constraints
Attempt to improve states by reassigning variable values
Hill-climbing search:
In each iteration, randomly select any conflicted variable and choose value that violates the fewest constraints
I.e., attempt to greedily minimize total number of violated constraints
Problem: local minima

h = 1

Слайд 53

Local search for CSPs

Start with “complete” states, i.e., all variables assigned
Allow

Local search for CSPs Start with “complete” states, i.e., all variables assigned
states with unsatisfied constraints
Attempt to improve states by reassigning variable values
Hill-climbing search:
In each iteration, randomly select any conflicted variable and choose value that violates the fewest constraints
I.e., attempt to greedily minimize total number of violated constraints
Problem: local minima
For more on local search, see ch. 4

Слайд 54

CSP in computer vision: Line drawing interpretation

An example polyhedron:

Domains: +, –, →, ←

CSP in computer vision: Line drawing interpretation An example polyhedron: Domains: +,

Variables: edges

David Waltz, 1975

Desired output:

Слайд 55

CSP in computer vision: Line drawing interpretation

Four vertex types:

Constraints imposed by each vertex

CSP in computer vision: Line drawing interpretation Four vertex types: Constraints imposed
type:

David Waltz, 1975

Слайд 56

CSP in computer vision: 4D Cities

G. Schindler, F. Dellaert, and S.B. Kang,

CSP in computer vision: 4D Cities G. Schindler, F. Dellaert, and S.B.
Inferring Temporal Order of Images From 3D Structure, IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2007.

1. When was each photograph taken?
2. When did each building first appear?
3. When was each building removed?

Set of Photographs:

Set of Objects:
Buildings

http://www.cc.gatech.edu/~phlosoft/

Слайд 57

CSP in computer vision: 4D Cities

Goal: reorder images (columns) to have as

CSP in computer vision: 4D Cities Goal: reorder images (columns) to have
few violations as possible

observed

missing

occluded

Columns: images
Rows: points

Violates constraints:

Satisfies constraints:

Слайд 58

CSP in computer vision: 4D Cities

Goal: reorder images (columns) to have as

CSP in computer vision: 4D Cities Goal: reorder images (columns) to have
few violations as possible
Local search: start with random ordering of columns, swap columns or groups of columns to reduce the number of conflicts
Can also reorder the rows to group together points that appear and disappear at the same time – that gives you buildings
Имя файла: CSP_8968662.pptx
Количество просмотров: 28
Количество скачиваний: 0