‫هوش مصنوعی و کارگاه‬

‫دانشکده ریاضی و علوم کامپیوتر‬

‫دانشگاه صنعتی امیرکبیر‬
‫مدرس کالس‪ :‬مهدی قطعی‬
‫استاد گروه علوم کامپیوتر‬
‫‪www.aut.ac.ir‬‬

‫مدرس کارگاه‪ :‬بهنام یوسفی مهر‬

‫دانشجوی دکتری علوم کامپیوتر‬
Artificial Intelligence & Workshop
o Constraint Satisfaction Problems
CS 188: Artificial Intelligence
Constraint Satisfaction Problems

Instructor: Anca Dragan

University of California, Berkeley
[These slides adapted from Dan Klein and Pieter Abbeel]
 Constraint Satisfaction Problems

N
variables
domain D
constraint
s
x2
x1

states goal test successor

partial complete; satisfies function
assign an unassigned variable
assignment constraints
 What is Search For?
o Assumptions about the world: a single agent, deterministic actions,
fully observed state, discrete state space

o Planning: sequences of actions

o The path to the goal is the important thing
o Paths have various costs, depths
o Heuristics give problem-specific guidance

o Identification: assignments to variables

o The goal itself is important, not the path
o All paths at the same depth (for some formulations)
o CSPs are specialized for identification problems
 Constraint Satisfaction Problems

o Standard search problems:

o State is a “black box”: arbitrary data
structure
o Goal test can be any function over states
o Successor function can also be anything

o Constraint satisfaction problems (CSPs):

o A special subset of search problems
o State is defined by variables Xi with
values from a domain D (sometimes D
depends on i)
o Goal test is a set of constraints specifying
allowable combinations of values for
subsets of variables

o Allows useful general-purpose algorithms

with more power than standard search
algorithms
CSP Examples
 Example: Map Coloring
o Variables:

o Domains:

o Constraints: adjacent regions must

have different colors
Implicit:

Explicit:
o Solutions are assignments satisfying all
constraints, e.g.:
Constraint Graphs
 Example: N-Queens
o Formulation 1:
o Variables:
o Domains:
o Constraints
 Example: N-Queens
o Formulation 2:
o Variables:

o Domains:

o Constraints:

Implicit:

Explicit:
 Example: Cryptarithmetic
X1

o Variables:

o Domains:

o Constraints:
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
o Discrete Variables
o Finite domains
o Size d means O(dn) complete assignments
o E.g., Boolean CSPs, including Boolean
satisfiability (NP-complete)
o Infinite domains (integers, strings, etc.)
o E.g., job scheduling, variables are start/end times
for each job
o Linear constraints solvable, nonlinear
undecidable

o Continuous variables
o E.g., start/end times for Hubble Telescope
observations
o Linear constraints solvable in polynomial time by
LP methods (see cs170 for a bit of this theory)
 Varieties of Constraints
o Varieties of Constraints
o Unary constraints involve a single variable
(equivalent to reducing domains), e.g.:

o Binary constraints involve pairs of variables,

e.g.:

o Higher-order constraints involve 3 or more

variables:
e.g., cryptarithmetic column constraints

o Preferences (soft constraints):

o E.g., red is better than green
o Often representable by a cost for each variable
assignment
o Gives constrained optimization problems
o (We’ll ignore these until we get to Bayes’ nets)
 Real-World CSPs
o Assignment problems: e.g., who teaches what class
o Timetabling problems: e.g., which class is offered when and where?
o Hardware configuration
o Transportation scheduling
o Factory scheduling
o Circuit layout
o Fault diagnosis
o … lots more!

o Many real-world problems involve real-valued variables…

 ‫کوییز‬
‫بیمارستانی ‪ 8‬شیفت کاری دارد‪ .‬در هر بازه زمانی ‪ 2‬ساعته ‪d_i‬‬
‫پرستار نیاز دارد‪ .‬هر پرستار ‪ k<=8‬ساعت می تواند کار کند‪.‬‬
‫شیفت های کاری به صورت بازه های [‪ ]a,b‬که مضربی از ‪ 2‬هستند‬
‫تشکیل شده است‪ .‬ایا بیمارستان با ‪ n=20‬پرستار می تواند نیاز‬
‫خود را پاسخ دهد؟‬
Solving CSPs
 Standard Search Formulation
o Standard search formulation of
CSPs

o States defined by the values

assigned so far (partial
assignments)
o Initial state: the empty
assignment, {}
o Successor function: assign a value
to an unassigned variable
o Goal test: the current assignment
is complete and satisfies all
constraints

o We’ll start with the

 Search Methods
o What would BFS do?

{
}
{NSW=g
{WA=r} … {NT=g} …
}

[Demo: coloring -- dfs]

 Search Methods
o What would BFS do?

o What would DFS do?

o What problems does naïve search have?

[Demo: coloring -- dfs]

Backtracking Search
 Backtracking Search
o Backtracking search is the basic uninformed algorithm for
solving CSPs
o Idea 1: One variable at a time
o Variable assignments are commutative, so fix ordering -> better
branching factor!
o I.e., [WA = red then NT = green] same as [NT = green then WA = red]
o Only need to consider assignments to a single variable at each step

o Idea 2: Check constraints as you go

o I.e. consider only values which do not conflict previous assignments
o Might have to do some computation to check the constraints
o “Incremental goal test”

o Depth-first search with these two improvements

is called backtracking search (not the best name)
o Can solve n-queens for n  25
Backtracking Example

[Demo: coloring -- backtracking]

 Backtracking Search

o Backtracking = DFS + variable-ordering + fail-

on-violation
o What are the choice points?
 Improving Backtracking

o General-purpose ideas give huge gains in

speed

o Ordering:
o Which variable should be assigned next?
o In what order should its values be tried?

o Filtering: Can we detect inevitable failure

early?
 Filtering

Keep track of domains for unassigned variables and cross off bad
 Filtering: Forward Checking
o Filtering: Keep track of domains for unassigned variables and cross
off bad options
o Forward checking: Cross off values that violate a constraint when
added to the existing assignment
NT Q
WA
SA NSW
V

[Demo: coloring -- forward checking]

 Filtering: Constraint Propagation
o Forward checking propagates information from assigned to
unassigned variables, but doesn't provide early detection for all
failures:

NT Q
WA
SA
NSW
V

o NT and SA cannot both be blue!

o Why didn’t we detect this yet?
o Constraint propagation: reason from constraint to constraint
 Consistency of A Single Arc
o 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

NT Q
WA
SA
NSW
V

Forward checking? Delete from the tail!

Enforcing consistency of arcs pointing to each new assignment
 Arc Consistency of an Entire CSP
o A simple form of propagation makes sure all arcs are consistent:

NT Q
WA SA
NSW
V

o Important: If X loses a value, neighbors of X need to be rechecked!

o Arc consistency detects failure earlier than forward checking
o Can be run as a preprocessor or after each assignment Remember: Delete
o from the tail!
What’s the downside of enforcing arc consistency?
Enforcing Arc Consistency in a CSP

o Runtime: O(n2d3), can be reduced to O(n2d2)

o … but detecting all possible future problems is NP-hard –
why?
 Limitations of Arc Consistency

o After enforcing arc

consistency:
o Can have one solution left
o Can have multiple
solutions left
o Can have no solutions left
(and not know it)

o Arc consistency still runs

inside a backtracking [Demo: coloring -- forward checking]
[Demo: coloring -- arc consistency]
 K-Consistency
o Increasing degrees of consistency
o 1-Consistency (Node Consistency): Each single node’s
domain has a value which meets that node’s unary
constraints
o 2-Consistency (Arc Consistency): For each pair of
nodes, any consistent assignment to one can be
extended to the other
o K-Consistency: For each k nodes, any consistent
assignment to k-1 can be extended to the kth node.

o Higher k more expensive to compute

o (You need to know the k=2 case: arc

consistency)
 Strong K-Consistency
o Strong k-consistency: also k-1, k-2, … 1 consistent
o Claim: strong n-consistency means we can solve without
backtracking!
o Why?
o Choose any assignment to any variable
o Choose a new variable
o By 2-consistency, there is a choice consistent with the first
o Choose a new variable
o By 3-consistency, there is a choice consistent with the first 2
o …

o Lots of middle ground between arc consistency and n-consistency!

(e.g. k=3, called path consistency)