Transcript ppt

Constraint Satisfaction Problems
ECE457 Applied Artificial Intelligence
Spring 2007
Lecture #4
Outline


Defining constraint satisfaction
problems (CSP)
CSP search algorithms

Russell & Norvig, chapter 5
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 2
States

What do we know about states?





A state might be a goal (goal test)
A state has a value (cost or payoff)
An agent moves from state to state using
actions
The state space can be discreet or
continuous
Ties in with the problem definition

Initial state, goal test, set of actions and
their costs defined in problem
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 3
Definitions

A constraint-satisfaction problem has

A set of variables


Each variable has a domain of values


Xi  Di = {di1, di2, …, din}
A set of constraints on the values each
variable can take


V = {X1, X2, …, Xn}
C = {C1, C2, …, Cm}
A state is a set of assignment of values

S1 = {X1 = d12, X4 = d45}
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 4
Definitions

Consistent (legal) state


Complete state


Does not violate any constraints
All variables have a value
Goal state


Consistent and complete
Might not exist

Proof of inconsistency
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 5
Example: 8-queen

Variables: 64 squares


Values: Queen or no queen


Xi,j  D = {queen, empty}
States: All board configurations


V = {X1,1, X1,2, …, X64,64}
1.8x1014 complete states
Constraints: Attacks


{Xi,j = queen  Xi,j+n = empty,
Xi,j = queen  Xi+n,j = empty,
Xi,j = queen  Xi+n,j+n = empty}
92 complete and consistent states
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 6
Example: 8-queen
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 7
Example: The Einstein Puzzle

There are 5 houses in 5 different colours. In each house lives a person
with a different nationality. These 5 owners drink a certain beverage,
smoke a certain brand of cigar and keep a certain pet. No owners have
the same pet, smoke the same brand of cigar or drink the same drink.
Who keeps the fish?















The
The
The
The
The
The
The
The
The
The
The
The
The
The
The
English lives in a red house.
Swede keeps dogs as pets.
Dane drinks tea.
green house is on the left of the white house.
green house owner drinks coffee.
person who smokes Pall Mall rears birds.
owner of the yellow house smokes Dunhill.
man living in the house right in the centre drinks milk.
Norwegian lives in the first house.
man who smokes Blend lives next to the one who keeps cats.
man who keeps horses lives next to the man who smokes Dunhill.
owner who smokes Blue Master drinks beer.
German smokes Prince.
Norwegian lives next to the blue house.
man who smokes Blend has a neighbour who drinks water.
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 8
Example: The Einstein Puzzle
1

3
4
5
25 variables


2
V = {N1, …, N5, C1, …, C5, D1, …, D5, S1, …, S5,
P1, …, P5}
Domains





Ni  {English, Swede, Dane, Norwegian, German}
Ci  {green, yellow, blue, red, white}
Di  {tea, coffee, milk, beer, water}
Si  {Pall Mall, Dunhill, Blend, Blue Master, Prince}
Pi  {dog, cat, horse, fish, birds}
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 9
Example: The Einstein Puzzle

The Norwegian lives in the first house.


The English lives in a red house.


N1 = Norwegian
(Ni = English)  (Ci = Red)
The green house is on the left of the
white house.



(Ci = green)  (Ci+1 = white)
(C5 ≠ green)
(C1 ≠ white)
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 10
Example: Map Colouring

Colour map of the provinces of Australia



3 colours (red, green, blue)
No adjacent provinces of the same colour
Define CSP
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 11
Example: Map Colouring CSP

Variables


Domain


{WA, NT, SA, Q, NSW,
V, T}
{R, G, B}
Constrains

{WA  NT, WA  SA,
NT  SA, NT  Q,
SA  Q, SA  NSW, SA
 V, Q  NSW, NSW 
V}
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 12
Solving CSP

Iterative improvement methods


Start with random complete state, improve
until consistent
Tree searching

Start with empty state, make consistent
variable assignments until complete
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 13
Iterative Improvement

Algorithm:


Start with random complete state
While not consistent



Not complete



Pick a variable (randomly or with a heuristic)
Change its assignment to minimize number of
violated constraints
Might not search all state space
Might not find a solution even if one exists
We won’t do that in this course
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 14
Tree Search

Formulate CSP as tree



Root node: no variables are assigned a
value
Action: assign a value if it does not violate
any constraints
Solution node at depth n for n-variable
problem
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 15
Backtracking Search


Start with empty state
While not complete


Pick a variable (randomly or with heuristic)
If it has a value that does not violate any
constraints


Assign that value
Else


Go back to previous variable
Assign it another value
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 16
Backtracking Search

Depth-first search algorithm




Algorithm complete



Goes down one variable at a time
In a dead end, back up to last variable whose
value can be changed without violating any
constraints, and change it
If you backed up to the root and tried all values,
then there are no solutions
Will find a solution if one exists
Will expand the entire (finite) search space if
necessary
Depth-limited search with limit = n
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 17
Example: Backtracking Search
WA = G
WA = R
NT = G
NT = B
Q=B
Q=R
NSW = G
NSW
SWA = B
R
SA = B
?
SA = ?
WA = B
V=R
T=R
T=G
ECE457 Applied Artificial Intelligence
T=B
R. Khoury (2007)
Page 18
Conflict-Directed Backjumping

Suppose we colour Australia in this order:







WA – R
NSW – R
T–B
NT – B
Q–G
SA - ?
Dead-end at SA


No possible solution with WA = NSW
Backtracking will try to change T on the way, even
though it has nothing to do with the problem,
before going to NSW
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 19
Conflict-Directed Backjumping

Backtracking goes back one level in the
search tree at a time



Chronological backtrack
Not rational in cases where the previous
step is not involved to the conflict
Conflict-directed backjumping (CBJ)



Should go back to a variable involved in
the conflict
Skip several levels if needed to get there
Non-chronological backtrack
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 20
Conflict-Directed Backjumping

Maintain a conflict set for each variable

List of previously-assigned variables that are
related by constraints
conf(WA) = {}
conf(NSW) = {}
conf(T) = {}
conf(NT) = {WA}
conf(Q) = {NSW,NT}
conf(SA) = {WA,NSW,NT,Q}

When we hit a dead-end, backjump to the
deepest variable in the conflict set
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 21
Conflict-Directed Backjumping

Learn from the conflict by updating the
conflict set of the variable we jumped to





Conflict at Xj, backjump to Xi
conf(Xi)={X1,X2,X3} conf(Xj)={X3,X4,X5,Xi}
conf(Xi) = conf(Xi)  conf(Xj) – {Xi}
conf(Xi) = {X1,X2,X3,X4,X5}
Xi absorbed the conflict set of Xj
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 22
Conflict-Directed Backjumping
conf(WA) = {}
conf(NSW) = {}



conf(T) = {}
conf(NT) = {WA}
conf(Q) = {NSW,NT}
conf(SA) =
{WA,NSW,NT,Q}
SA backjump to Q

Q backjump to NT


conf(Q) = {WA,NSW,NT}
Meaning: “There is no
consistent solution from Q
onwards, given the preceding
assignments of WA, NSW and
NT together”
conf(NT) = {WA,NSW}
NT backjump over T to NSW

conf(NSW) = {WA}
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 23
Heuristics

Backtracking and CDJ searches are
variations of depth-limited search



Uninformed search technique
Can we make it an informed search?
Add some heuristics



Which variable to assign next?
In which order should the values be tried?
How to detect dead-ends early?
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 24
Variable & Value Heuristics

Most constrained variable



Most constraining variable




Choose the variable with the fewest legal values
remaining in its domain
aka Minimum remaining values
Choose the variable that’s part of the most
constraints
Useful to pick first variable to assign
aka Degree heuristic
Least constraining variable


Pick the variable that’s part of the fewest
constrains
Keeps maximum flexibility for future assignments
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 25
Variable & Value Heuristics
Values: 2
Constraints: 2
Values: 2
Constraints: 1
Most constrained &
Mostconstraining
constraining
Most constrained
least
Values:
2
variable
variable
variable
Constraints: 1
ECE457 Applied Artificial Intelligence
Most
Values:
constrained
2
variable
Constraints: 2
Values: 2
Constraints: 2
Mostconstraining
constrained
Most
variable
variable
Least constraining
variable
R. Khoury (2007)
Page 26
Forward Checking


How to detect dead-ends early?
Keep track of the domain of unassigned
variables



Use constraints to prune domain of
unassigned variables
Backtrack when a variable has an empty
domain
Do not waste time exploring further
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 27
Example: Forward Checking
WA
RGB
B
NT
RGB
RG
G
Q
RGB
RB
R
NSW GB
RGB
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
V
RGB
T
RGB
SA
RGB
RG
R
Page 28
Problem with Forward Checking
WA
B
NT
G
Q
G
NSW B
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
V
G
T
RGB
SA
R
Page 29
Constraint Propagation


Propagate the consequences of a
variable’s constraints onto other
variables
Represent CSP as
NT
constraint graph
WA



Nodes are variables
Arcs are constraints
Q
NSW
SA
Check for consistency
V
T
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 30
Checking for Consistency

Node consistency



Arc consistency



Unary constraint (e.g. NT  G)
A node is consistent if and only if all values in its
domain satisfy all unary constraints
Binary constraint (e.g. NT  Q)
An arc Xi  Xj or (Xi, Xj) is consistent if and only if,
for each value a in the domain of Xi, there is a
value b in the domain of Xj that is permitted by
the binary constraints between Xi and Xj.
Path consistency

Can be reduced to arc consistency
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 31
Checking for Consistency

Node consistency


Simply scan domain of values of each
variable and remove those that are not
valid
Arc consistency

Examine edges and delete values from
domains to make arcs consistent
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 32
Checking for Consistency

Remove inconsistent values from a
variable’s domain



Backtrack if empty domain
Maintaining node and arc consistency
reduces the size of the tree
More computationally expensive than
Forward Checking, but worth it
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 33
AC-3 Algorithm


Keep queue of arcs (Xi, Xj) to be
checked for consistency
If checking an arc removes a value from
the domain of Xi, then all arcs (Xk, Xi)
are reinserted in the queue
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 34
AC-3 Algorithm


Add all arcs to queue
While queue not empty


Get next arc from queue
For each value di of Xi

If there is no consistent value dj in Xj


Delete di
If a value di was deleted

For each neighbour Xk of Xi

Add arc (Xk, Xi) to queue
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 35
AC-3 Algorithm

Advantages



Prunes tree, reduces amount of searching
For n-node CSP that’s n-consistent,
solution is guaranteed with no backtracking
Disadvantage

Computationally expensive

If pruning takes longer than searching, it’s not
worth it
ECE457 Applied Artificial Intelligence
R. Khoury (2007)
Page 36