AC-1, AC-2 and AC-3 algorithms (arc-consistency)

I'm going to give you a fast explanation about backtracking and the AC-3. But if you want to read about this with more detail you should read the book:

Artificial Intelligence: A Modern Approach : Stuart Russel and Peter Norvig 2003 Prentice Hall

this book as a chapter about Constraint satisfaction problems (CSP) that explains all about AC-3 and backtracking.

The first thing you need to understand is what is a CSP. A CSP contains:

A set of variable {A, B, C} to which you want to find a value;
A domain for each variable Da, Db, Dc each containing the possible values that the variable can take;
A set of restrictions like A > B + 2 and C < B ...

Now when you have a CSP you want to attribute values to all the variables and keep respecting the resctictions. The CSP is solved when all the variables have a value and respect all the restrictions at the same time.

Backtracking is a algorithm that allows you to find a solution for this problem. So you start with a empty state {} which means that no variable has a value. Then you pick up one variable from the variables set (the order you use to choose the variable you pick may affect the performance of the algorithm there are some heuristics that you can use for this like MRV - Minimum values remaining ...). Now let's say we choose A first, now we pick up a value from the domain Da (The order you pick this value may also use an heuristic). Imagine Da = {1,2,3}. We pick 1. Now we check if A = 1 has does not violate any restriction, otherwise it's not a good attribution. If it doesn't then let's set A = 1, now we are in the state {A=1}. Now let's keep doing this. Imagine you pick B and a value 1. This will violate the restriction A > B + 2. Now you have two options, if you have another value to test for B, you can try it. If not, this means that A = 1 it's wrong and you'll need to go back to the state {} and try A = 2 and so on.

Here's the pseudocode of the backtracking:

function backtracking (csp) return a solution or fails
    return recursive_backtracking({}, csp) // {} is the initial state

function recursive_backtracking (state, csp) return a solution or fails
    if state is complete then return state // all variable have a value
    var <- selectNotAtributedVariable(csp)
    for each value in orderValues(csp, var) // values of the domain of var
        if var = value is consistent given the restrictions
            add {var = value} to state
            result = recursive_backtracking(state, csp)
            if result != fail then return result
            remove {var = value} from state
    return fail

Note that selectNotAtributedVariable and orderValues are heuristics (they may just return the first element of the set).

Now what is AC-3 and why and when do we use it? First AC-3 is used as a preprocess step. You use it like this:

function solveCSP(csp)
    ac3(csp)
    return backtracking(csp)

this answers to when. Basically AC-3 detects conflicts that you will have in attributions, during the backtracking, and deletes them. How? By cutting the domains of the variables in the CSP. So when two variables share a restriction we say that there's an arc between both. You say that the arc between A and B is consistent if:

A->B is consistent: foreach value a that A can take there's a value b that B can take respecting the restriction.
and B->A is consistent: foreach value b that B can take there's a value a that A can take respecting the restriction.

Imagine you have the following restrictions A > B and B > C. You'll have the following set of arcs: {A->B, B->A, B->C, C->B} Now what AC-3 does is it selects an arc from the set above, A->B, for each value of a that A can takes try to check if there's a value b that B can take respecting the restriction. If so, the domain of A keeps the same, if not remove the value a from the domain of A. Every time a value is removed from the domain, you'll have to recheck the neighbors of A (in this case). I mean you'll need to recheck the arc B->A (not because they are in the set above).

So, here's the pseudocode:

function AC3(csp) returns csp possibly with the domains reduced
    queue, a queue with all the arcs of the CSP
    while queue not empty
         (X,Y) <- getFirst(queue)
         if RemoveConsistentValues(X,Y, csp) then
              foreach Z in neighbor(X) - {Y}
                   add to queue (Z,X)
    return csp

function RemoveConsistentValues(X, Y, csp) returns true if a value was removed
    valueRemoved <- false
    foreach x in domain(X, csp)
        if there's no value of domain(Y, csp) that satisfies the restriction between X and Y then
            remove x from domain(X, csp)
            valueRemoved <- true
    return valueRemoved

Recommended topics

Hot tags