程序代写代做代考 algorithm Constraint Sa+sfac+on Problems (Chapter 6)

Constraint Sa+sfac+on Problems (Chapter 6)

Two classes of search problems
• Assump+ons: single agent, determinis+c, fully observable, discrete environment
• Search for planning
– The path to the goal is the
important thing
– Paths have various costs, depths
• Search for assignment
– Assign values to variables while
respec+ng certain constraints
– The goal (complete, consistent assignment) is the important thing

Constraint sa+sfac+on problems (CSPs)
• Defini+on:
– State is defined by variables Xi with values from domain Di
– Goal test is a set of constraints specifying allowable combina+ons of values for subsets of variables
– Solu/on is a complete, consistent assignment
• How does this compare to the “generic” tree search
formula+on?
– A more explicit representa+on for states and goal test – Allows for more efficient specialized search algorithms

Example: Map Coloring
• Variables: WA, NT, Q, NSW, V, SA, T
• Domains: {red, 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)}

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

Example: n-queens problem
• Putnqueensonann×nboardwithnotwoqueensonthe same row, column, or diagonal

Example: N-Queens
• Variables: Xij
• Domains: {0, 1} • Constraints:
Σi,j Xij = N
(Xij, Xik) ∈ {(0, 0), (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

N-Queens: Alterna+ve formula+on
• Variables: Qi
• Domains: {1, … , N}
Q1 Q2
Q3 Q4
• Constraints:
∀ i, j non-threatening (Qi , Qj)

Example: Cryptarithme+c
• Variables: T, W, O, F, U, R X1, X2
• Domains: {0, 1, 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

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

Real-world CSPs • Assignment problems
– e.g., who teaches what class • Timetable problems
– e.g., which class is offered when and where? • Transporta+on scheduling
• Factory scheduling
• More examples of CSPs: hip://www.csplib.org/

Standard search formula+on (incremental)
• States:
– Variables and values assigned so far
• Ini/al state:
– Theemptyassignment
• Ac/on:
– Chooseanyunassignedvariableandassigntoitavalue
that does not violate any constraints • Fail if no legal assignments
• Goal test:
– Thecurrentassignmentiscompleteandsa+sfiesall constraints

Standard search formula+on (incremental)
• What is the depth of any solu+on (assuming n 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?

Backtracking search
• In CSP’s, variable assignments are commuta/ve
– For example, [WA = red then 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

Example

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

Which variable should be assigned next?
• Most constrained variable:
– Choose the variable with the fewest legal values – A.k.a. minimum remaining values (MRV) heuris+c

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

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

Given a variable, in which order should its values be tried?
• Choose the least constraining value:
– The value that rules out the fewest values in the remaining variables
Which assignment for Q should we
choose?

Early detec+on of failure
Apply inference to reduce the space of possible assignments and detect failure early

Early detec+on of failure: Forward checking
• Keep track of remaining legal values for unassigned variables
• Terminate search when any variable has no legal values

Constraint propaga+on
• Forward checking propagates informa+on from assigned to unassigned variables, but doesn’t provide early detec+on for all failures
• NT and SA cannot both be blue!
• Constraint propaga/on repeatedly enforces constraints locally

Arc consistency
• Simplest form of propaga+on makes each pair of variables consistent:
– XàY is consistent iff for every value of X there is some allowed value of Y
Consistent!

Arc consistency
• Simplest form of propaga+on makes each pair of variables consistent:
– XàY is consistent iff for every value of X there is some allowed value of Y

Arc consistency
• Simplest form of propaga+on makes each pair of variables consistent:
– XàY 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

Arc consistency
• Simplest form of propaga+on makes each pair of variables consistent:
– XàY 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

Arc consistency
• Simplest form of propaga+on makes each pair of variables consistent:
– XàY 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
• Arc consistency detects failure earlier than forward checking
• Can be run before or aser each assignment

Arc consistency algorithm AC-3

Does arc consistency always detect the lack of a solu+on?
B AD
C
A BC D
• There exist stronger no+ons of consistency (path consistency, k-consistency), but we won’t worry about them

Tree-structured CSPs
• Certain kinds of CSPs can be solved without resor+ng to backtracking search!
• Tree-structured CSP: constraint graph does not have any loops
Source: P. Abbeel, D. Klein, L. Zettlemoyer

Algorithm for tree-structured CSPs
• Choose one variable as root, order variables from root to leaves such that every node’s parent precedes it in the ordering
http://cs188ai.wikia.com/wiki/Tree_Structure_CSPs

Algorithm for tree-structured CSPs
• Choose one variable as root, order variables from root to leaves such that every node’s parent precedes it in the ordering
• Backward removal phase: check arc consistency star+ng from the rightmost node and going backwards
• Forward assignment phase: select an element from the domain of each variable going les 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

Algorithm for tree-structured CSPs
• If n is the number of variables and m is the domain size, what is the running +me 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

Nearly tree-structured CSPs
• Cutset condi/oning: find a subset of variables whose removal makes the graph a tree, instan+ate that set in all possible ways, prune the domains of the remaining variables and try to solve the resul+ng tree-structured CSP
• Cutset size c gives run+me O(mc (n – c)m2)
Source: P. Abbeel, D. Klein, L. Zettlemoyer

Algorithm for tree-structured CSPs
• Running +me is O(nm2)
(n is the number of 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 beier?

Computa+onal complexity of CSPs • The sa+sfiability (SAT) problem:
– Given a Boolean formula, is there 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 +me
– 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

Local search for CSPs
• Start with “complete” states, i.e., all variables assigned
• Allow states with unsa+sfied constraints
• Aiempt to improve states by reassigning variable values
• Hill-climbing search:
– In each itera+on, randomly select any conflicted variable and choose value that violates the fewest constraints
– I.e., aiempt to greedily minimize total number of violated constraints
h = number of conflicts

CSP in computer vision: Line drawing interpreta+on
An example polyhedron:
Desired output:
Variables: edges Domains: +, –, →, ←
David Waltz, 1975

CSP in computer vision: Line drawing interpreta+on
Constraints imposed by each vertex type:
Four vertex types:
David Waltz, 1975

CSP in computer vision: 4D Ci+es
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
G. Schindler, F. Dellaert, and S.B. Kang, Inferring Temporal Order of Images From 3D Structure, IEEE Computer Society Conference on Computer Vision and Paiern Recogni+on (CVPR), 2007.
http://www.cc.gatech.edu/~phlosoft/

CSP in computer vision: 4D Ci+es
observed missing occluded
• Goal: reorder images (columns) to have as few viola+ons as possible
Columns: images Rows: points
Satisfies constraints:
Violates constraints:

CSP in computer vision: 4D Ci+es
• Goal: reorder images (columns) to have as few viola+ons 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 +me – that gives you buildings

Summary
• CSPs are a special kind of search problem:
– States defined by values of a fixed set of variables – Goal test defined by constraints on variable values
• Backtracking = depth-first search where successor states are generated by considering assignments to a single variable
– Variable ordering and value selec/on heuris+cs can help significantly
– Forward checking prevents assignments that guarantee later failure
– Constraint propaga/on (e.g., arc consistency) does addi+onal work to constrain values and detect inconsistencies
• Complexity of CSPs
– NP-complete in general (exponen+al worst-case running +me)
– Efficient solu+ons possible for special cases (e.g., tree-structured CSPs)
• Alterna+ves to backtracking search: local search

Related Posts