Hi.
In this module, I'm going to be talking about the notion of arc
consistency.
This is going to lead us to look at an algorithm called AC-3
which is going to enable us to prune domains much more
aggressively than before in the context of backtracking search.
Let's begin.
First I want to review backtracking search.
So backtracking search is a recursive procedure
where it takes a partial assignment
x, its weight, and the domains of each
of the variables in the CSP.
If all the variables have already
been assigned in x, then we just see
if it's better than the best assignment we've seen so far
and if so update it.
And then we return.
This is the base case.
Otherwise, we're going to choose an unassigned variable Xi.
We're going to look at all the values in the domain of Xi
and order them, order into some heuristic LCV.
And now we're going to step through each
of the values v in that order.
We're going to compute the weight update based on the Xi's
being set to v. And if this is 0,
then we can just stop recursing right there.
Otherwise, we're going to use this updated assignment
as an input into the lookahead algorithm
to reduce the domains.
And now if any of the domains become empty,
then, again, we stop recursing.
Otherwise, we recurse.
So last time we talked about the heuristics
for choosing unassigned variable, ordering the values,
these are the MCV and LCV heuristics.
And then we looked at forward checking which
was the one step look ahead.
Now, we're going to upgrade that to AC-3.
So before we get into AC-3, I need
to talk about arc consistency.
Let's use a simple example.
So suppose we have just two variables, X1 and Xj.
X1 can be 1, 2, 3, 4, or 5, and Xj can be 1 or 2.
So and Xi and Xj are related, via a single factor
which says that their sum must equal 4 exactly.
So what does it mean to enforce arc consistency on, let's say,
Xi?
This means I'm going to go through each of the values
in the domain of Xi and try to eliminate it
if can't be satisfied by any value in Xj's domain.
OK.
So let's try this.
So look at 1, does there exist any possible setting of Xj
so that I can do 1 plus something to get 4?
1 plus 1 is not 4, 1 plus 2 is not 4,
so therefore one is just impossible without even
knowing the value of Xj.
So let me eliminate it.
What about 2?
Well, I can exchange a 2 to get 4, so that's OK.
Notice that it's fine that 1 plus 2 isn't 4,
it just matters that there exists one of the values in Xj
that work.
So let's leave 2 alone.
But what about 3?
Well, 3 plus 1 is 4.
So that's OK, too.
What about 4?
I can't add 4 to 1 or 2 to get 4,
so that gets eliminated and same with 5.
So in the end, enforcing arc consistency on Xi
results in a smaller domain which only consists of 2 and 3.
So notice I can eliminate values without even knowing
what the exact value of Xj is.
So more formally, arc consistency
is a property which I'll explain.
So a variable Xi is arc consistent with respect
to another variable Xj if for each value in the domain of xi
there exists some other value in the domain of xj such
that essentially all the factors check out.
So formally what that means is that if you
look at all the factors whose scope contains Xi and Xj,
and you evaluate that factor on xi,
xj, then you get something that's not 0.
OK, and forcing arc consistency is a procedure
that takes two variables and just simply removes the values
from domain i, to make Xi arc consistent with respect to Xj.
Exactly what we did on the example on the previous slide.
So let's revisit the Australia example and apply AC-3.
OK.
So here is the empty assignment.
And here are all the domains of each of the variables.
So let's suppose we set WA to be red, OK?
So as before, we eliminate the other values from WA's domain,
of course.
And then we enforce arc consistency
on the neighbors of WA.
In this case, NT and SA.
So out goes red on both of these.
And now we continue to try to enforce our consistency
on the neighbors of NT and SA.
But in this case, I can't actually eliminate anything.
OK.
So now we're going to recurse.
And suppose now in the next level of backtracking,
we assign NT green.
So now, again, we're going to enforce arc consistency
on the neighbors of NT.
So that will eliminate green from these two.
So notice that one step should look very familiar.
This is exactly forward checking.
But AC-3 doesn't stop there.
And then it says, enforce arc consistency
on the neighbors of Q and SA.
OK.
So let's enforce arc consistency on the neighbors of SA,
that eliminates blue from its neighbors.
And now let's enforce arc consistency
on the neighbors of Q. So that eliminates red from neighbors.
And now let's enforce arc consistency
on the neighbors of NSW.
So that eliminates green.
And at this point, we're done.
So notice what happened.
Each of these domains is only left with one value.
So even though we're still in the context of backtracking
search at NT, we're still trying to figure out
what to do with NT.
By looking ahead, we've actually seen
what values are even possible.
And we actually solve the problem.
So now formally we haven't set these values yet,
we just eliminated their domains.
But backtracking search recursing
on the rest of these values should
be really a walk in the park.
You go into SA and you set it to blue, set Q to red,
NSW to green and V to red and you're done.
So this shows you the power of AC-3.
With one fell swoop, it basically
can clean out a lot of the domains
and reveal what the actual assignments values are possible
here.
So here is AC-3 more formally.
So remember, forward checking, what you do
is when you assign the variable Xj
to some value in xj, little xj, you
set the domain to only include that value.
And then you enforce arc consistency
on the neighbors Xi with respect to Xj.
So here's a picture.
So you're setting Xj.
And then you consider all the neighbors of Xj.
For example, Xi and then you enforce arc consistency on Xi.
So you try to propagate what you know about Xj to Xi
and try to eliminate Xi's domain.
So now AC-3 just repeatedly enforces arc consistency
and there's nothing left to do.
So here is the algorithm.
We're going to maintain a working set of variables
that we need to go process, but we
start with Xj, which is the variable that we just assigned.
And while there's still variables to process,
we're going to just remove any Xj from S.
But the order doesn't really matter here.
And then for each of the neighbors Xi of Xj,
we're going to enforce arc consistency on that neighbor
with respect to Xj.
So propagate the constraints out.
And now if the domain of Xi changed,
then we're going to add Xi to S. Because we know more
about Xi now and we can hopefully
propagate the information farther to its neighbors.
So notice that a variable could be revisited multiple times.
So this is kind of like breadth first-search with exception
that you might visit a node more than once because you might
propagate some value to another neighbor
and that value might constrain something else
and then you might get more additional information back
and this can kind of go on for a while.
But it does run in polynomial time.
You can read the notes for a little bit more details
about the running time.
So as great as AC-3 might seem, it's not a panacea,
and it shouldn't be.
And it shouldn't be surprising because solving a CSP should
take an exponential time.
In general, an AC-3 isn't doing any sort
of backtracking search.
So here is a small example that shows
when AC-3 doesn't do anything.
So here we have a Mini Australia here with three variables.
And suppose each of them can either
be red or blue, red or blue, red or blue.
So immediately you should realize
that there is no consistent assignment to three variables
with only two colors such that any pair can't
have the same color.
But what happens if you run AC-3?
OK.
So let's look at this factor here.
So WA, NT.
So this is arc consistent because if I assign WA red,
then NT can be blue.
If I assign WA blue, then NT can be red.
So if I just look at this local configuration,
there's no problem.
And analogously, if I look over here, there's no problem.
And if I look over here, there's no problem.
So AC-3 doesn't detect a problem even though there's
no satisfying assignment.
So the intuition here is that AC-3
in general, arc consistency, all it's doing
is looking locally at the graph and it says,
it only detects problems that are kind of blatantly
wrong which can be detected locally.
But you can't avoid exhaustive search
to actually detect the kind of deep problems.
So let me summarize here.
Enforcing arc consistency is a way
to take what you know about one variable's domain
to propagate that information via the factors
to reduce the domains of its neighbors.
Forward checking only applies arc consistency
to its neighbors.
And this was already somewhat effective.
AC-3 just takes that to the extreme limit
and enforces arc consistency on the neighbors
and their neighbors and their neighbors
and so on until you converge.
It's trying to exhaustively enforce arc consistency as much
as possible to eliminate as much of the values from the domains
as possible.
And, of course, remember that AC-3 forward checking,
ours lookahead algorithms which are
used in the context of backtracking search
to detect inconsistencies so we can prune early
and also to maintain these domains so that we can use them
for heuristics such as MCV and LCV.
And lookahead turns out to be very, very important
for backtracking search.
If you can look ahead and detect inconsistency,
then that saves you the work of actually
having to recurse and explore a combinatorial number
of possibilities.
OK that's the end.