Transcript constraints

Quick warm-up
Assign Red, Green, or Blue
Neighbors must be different
Sudoku
1
2 1
3
4
1) What is your brain doing to solve these?
2) How would you solve these with search (BFS, DFS, etc.)?
Announcements
 Upcoming due dates
 Monday 9/21 11:59 pm HW 3 (edX)
 Friday 9/25 5:00 pm Project 1
 Discussion Sections
 Next week 9/22-23, official sign-up for section
 Sign up in person at section
 If overfull, priority goes to those who sign up and are registered for that section
 If you don’t show up in person, you may get bumped to another section
 Probability Sessions
 Weekly, until we’re done with probability!
 W 9-10 am, 299 Cory
 W 6-7 pm, 531 Cory
 Worksheets are posted on edX syllabus
 My office hours: Friday 9am 511 Soda; Monday 11am 310 Soda
AI in the News
With the help of A.I.,
America’s most famous
doll tries to fulfill a timeless
dream – convincing little
girls that she’s a real friend.
What happens if they
believe her?
CS 188: Artificial Intelligence
Constraint Satisfaction Problems
Instructor: Stuart Russell
University of California, Berkeley
Standard Search Problems
 Standard search problems:




State is a black box: arbitrary data structure
Goal test is a black box test on states
Actions are black box data structures
Transition model is a black box function
 Consequences:
 Have to write new code for every new problem
 Have to devise heuristics for each new problem
 Cannot just choose actions that achieve the goal!
 Solution: formal representation for states, actions, goals
Spectrum of representations
Search,
game-playing
CSPs, planning,
propositional logic,
Bayes nets, neural nets
First-order logic,
databases,
probabilistic programs
Constraint Satisfaction Problems
 State consists of variables Xi with values from a
domain D (or Di)
 Goal test is a set of constraints specifying allowable
combinations of values for subsets of variables
 Path to goal (order of assignments) doesn’t matter
 Consequences:
 Generic CSP algorithms much faster than standard search
 Generic heuristics apply to all CSPs
 Solve new problems without writing new code
Example: Map Coloring
 Variables: WA, NT, Q, NSW, V, SA, T
 Domains: {red, green, blue}
 Constraints: adjacent regions must have
different colors
Implicit: WA  NT
Explicit: (WA, NT)  {(red,green), (red,blue), … }
 Solutions are assignments satisfying all
constraints, e.g.:
{ WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green }
Example: N-Queens
 Formulation 1:
 Variables: Xij
 Domains: {0, 1}
 Constraints
 i, j, k
 i, j, k
 i, j, k
 i, j, k
(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)}
i,j Xij = N
Space of assignments:
2
2N
Example: N-Queens
 Formulation 2:
 Variables: Qk
 Domains: {1,2,3, … N}
 Constraints:
Implicit:  i, j non-threatening(Qi , Qj)
Explicit: (Q1 , Q2)  {(1,3), (1,4), … }
(Q1 , Q3)  etc.
Space of assignments:
NN
Which is bigger?
2
N
2

vs NN
2
N
 log2 2 vs log2 NN
 N2
vs N log2 N
 N=10: 1030 vs 1010
Constraint Graphs
Constraint Graphs
 Binary CSP: each constraint relates (at most) two
variables
 Binary constraint graph: nodes are variables, arcs
show constraints
 General-purpose CSP algorithms use the graph
structure to speed up search. E.g., Tasmania is an
independent subproblem!
 Every non-binary CSP can be converted to a binary
CSP (possibly with extra variables): AIMA Ex. 6.6
Example: Cryptarithmetic
 Variables:
 F T U W R O X1 X2 X3
 Domains:
 {0,1,2,3,4,5,6,7,8,9}
 Constraints:





alldiff( F,T,U,W,R,O )
O + O = R + 10 * X1
X1 + W + W = U + 10 * X2
X2 + T + T = O + 10 * X3
X3 = F
(X3) (X2) (X1)
Example: Sudoku



Variables:
 Each (open) square
Domains:
 {1,2,…,9}
Constraints:
9-way alldiff for each column
9-way alldiff for each row
9-way alldiff for each region
(or can have a bunch of
pairwise inequality
constraints)
Varieties of CSPs and Constraints
Varieties of CSPs
 Discrete Variables
 Finite domains, n variables with domain size d
 O(dn) complete assignments
 E.g., Boolean CSPs, d=2, including Boolean satisfiability where
constraints are clauses (SAT is NP-complete, so are most CSPs)
 Infinite domains (integers, strings, etc.)
 E.g., job scheduling with slots, variables are start slots for each job
 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 (see
cs170 for a bit of this theory)
Varieties of Constraints
 Varieties of Constraints
 Unary constraints involve a single variable (equivalent to
reducing domains), e.g.:
 SA  green
 Binary constraints involve pairs of variables, e.g.:
 SA  WA
 Higher-order constraints involve 3 or more variables:
e.g., cryptarithmetic column constraints
 Preferences (soft constraints):
 E.g., red is better than green
 Cost function for assignments; infinite cost for hard violations
 Gives constrained optimization problems
Real-World CSPs








Assignment problems: e.g., who teaches what class
Timetabling problems: e.g., which class is offered when and where?
Hardware configuration
Transportation scheduling
Factory scheduling
Circuit layout
Fault diagnosis
… lots more!
 Many real-world problems involve real-valued variables…
Break quiz
Given a search problem P expressed in the usual way:
 initial state s0, states S, actions A, goal test G, transition model Result(s,a)
and a time horizon T, construct a CSP C such that C has a solution
exactly when P has a solution of length T, and the solution to P can
be read off from the solution to C
Hint: You’ll need some variables for each time step, including At (the
action taken at time t). What are the constraints between time
steps? Other constraints on particular time steps?
Break quiz answer
Variables of the CSP are
 Action variables A0 ,…, AT-1 each with domain A
 State variables S0 ,…, ST , each with domain S
Constraints of the CSP are
 S0=s0
 ST satisfies goal test G
 For t=0,…,T-1, St+1=Result(St, At)
Solving CSPs
Standard Search Formulation
 States defined by the values assigned
so far (partial assignments)
 Initial state: the empty assignment, {}
 Actions(s): assign a value to an
unassigned variable
 Result(s,a): the variable has the value
 Goal-Test(s): the current assignment is
complete and satisfies all constraints
 We’ll start with the straightforward,
naïve approach, then improve it
Search Methods
 What would BFS do?
 What would DFS do?
 What problems does naïve search have?
Demo: applying DFS naïvely to graph coloring
Backtracking Search
Backtracking Search
 Backtracking search is the basic uninformed algorithm for solving CSPs
 Idea 1: One variable at a time
 Variable assignments are commutative, so fix ordering
 I.e., [WA = red then NT = green] same as [NT = green then WA = red]
 Only choose assignment for a single variable at each step: reduce b from nd to d
 Idea 2: Check constraints as you go
 I.e., consider only values which do not conflict with previous assignments
 Might have to do some computation to check the constraints
 “Incremental goal test”
 Depth-first search with these two improvements
is called backtracking search
 Can solve n-queens for n  25
Backtracking Example
Backtracking Search
function BACKTRACKING-SEARCH(csp) returns a solution, or failure
return BACKTRACK({ }, csp)
function BACKTRACK(assignment,csp) returns a solution, or failure
if assignment is complete then return assignment
var ← SELECT-UNASSIGNED-VARIABLE(csp,assignment)
for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
if value is consistent with assignment then
add {var = value} to assignment
inferences ←INFERENCE(csp,var,assignment)
if inferences ̸= failure then
add inferences to assignment
result ← BACKTRACK(assignment, csp)
if result ̸= failure then return result
remove {var = value} and inferences from assignment
return failure
Demo: applying backtracking to graph coloring
Improving Backtracking
 General-purpose ideas give huge gains in speed
 Ordering:
 Which variable should be assigned next?
 In what order should its values be tried?
 Filtering: Can we detect inevitable failure early?
 Structure: Can we exploit the problem structure?
Ordering
Variable Ordering
 var ← SELECT-UNASSIGNED-VARIABLE(csp,assignment)
 Variable Ordering: Minimum remaining values (MRV):
 Choose the variable with the fewest legal left values in its domain
 Why min rather than max?
 “Fail-fast” ordering; lower branching
 Break ties using degree heuristic
 Choose variable with most connections to others
Demo: backtracking+MRV for graph coloring
Value Ordering
 for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
 Choose the Least Constraining Value (LCV)
 I.e., the one that rules out the fewest values in the
remaining variables
 Why least rather than most?
 Combining these ordering ideas makes
1000 queens feasible
Filtering
inferences ←INFERENCE(csp,var,assignment)
if inferences ̸= failure then
add inferences to assignment
…
Filtering: Forward Checking
 Filtering: Keep track of domains for unassigned variables and cross off bad options
 Simple example: forward checking
 Cross off values that violate a constraint when added to the existing assignment
Demo: backtracking+FC for graph coloring
More advanced inference
The MAC (maintaining arc consistency) algorithm detects many
more failures earlier than forward checking
 See AIMA Section 6.2 for details
 We’ll see a definition and application of arc consistency shortly
(and in HW4)
Structure
Problem Structure
 Extreme case: independent subproblems
 Example: Tasmania and mainland do not interact
 Independent subproblems are identifiable as
connected components of constraint graph:
 Divide and Conquer!
 Suppose a graph of n variables can be broken into
subproblems of only c variables each:
 Worst-case solution cost is …
 O((n/c)(dc)), linear in n
 E.g., n = 80, d = 2, c =20, search 10 million nodes/sec
 Original problem: 280 = 4 billion years
 Four subproblems: 4 x 220 = 0.4 seconds
Tree-Structured CSPs
 Theorem: if the constraint graph has no loops, the CSP can be solved in O(n d2) time
 Compare to general CSPs, where worst-case time is O(dn)
 This property also applies to probabilistic reasoning (later): an example of the relation
between syntactic restrictions and the complexity of reasoning
Useful notion: Consistency of an arc
 An arc X  Y is consistent iff for every x in the tail there is some y in the head which
could be assigned without violating a constraint
This is an example of
constraint propagation
via arc consistency checks.
More powerful than simple
forward checking.
Delete from the tail!
 Forward checking: Enforcing consistency of arcs pointing to each new assignment
Tree-Structured CSPs
 Algorithm for tree-structured CSPs:
 Order: Choose a root variable, order variables so that parents precede children
X
X
X
 Remove backward: For i = n : 2, apply RemoveInconsistent(Parent(Xi),Xi)
 Assign forward: For i = 1 : n, assign Xi consistently with Parent(Xi)
 Runtime: O(n d2)
Improving Structure
Nearly Tree-Structured CSPs
 Conditioning: instantiate a variable, prune its neighbors' domains
 Cutset conditioning: instantiate (in all ways) a set of variables such that
the remaining constraint graph is a tree
Cutset Conditioning
Choose a cutset
SA
Instantiate the cutset
(all possible ways)
SA
Compute residual CSP
for each assignment
Solve the residual CSPs
(tree structured)
SA
SA
Isn’t that a lot of extra work?
 Assume (as usual) n variables with domain size d
 Remember a tree with m variables is solvable in time md2
 Cutset size c gives runtime …
 O( (dc) (n-c) d2 ), very fast for small c
 E.g., 80 variables, c=10, 4 billion years -> 0.029 seconds
A quick note on local search for CSPs
Min-conflicts algorithm
 Like hill-climbing, but not quite!
 Algorithm: While not solved,
 Variable selection: randomly select any conflicted variable
 Value selection: min-conflicts heuristic:
 Choose a value that violates the fewest constraints
 Break ties randomly
Demo: min-conflicts for graph coloring
Performance of Min-Conflicts
 Given random initial state, can solve n-queens in almost constant time for arbitrary
n with high probability (e.g., n = 10,000,000)!
 The same appears to be true for any randomly-generated CSP except in a narrow
range of the ratio
Summary: CSPs
 CSPs are a special kind of search problem:
 States are (partial) assignments of values to variables
 Goal test defined by constraints
 Formal language => general algorithms and heuristics
 Basic algorithm: backtracking search
 Speed-ups:
 Ordering
 Filtering and constraint propagation
 Structure (decomposition, trees and near-trees)
 Local search with min-conflicts is often effective in practice