CSE 250A LECTURE NOTES

ANNOUNCEMENTS

For more information on a major real-world application of CSP methods, see SPIKE: Intelligent Scheduling of Hubble Space Telescope Observations by Mark D. Johnston and Glenn E. Miller.
 
 

ARC CONSISTENCY

An arc (Vi, Vj) can always be made consistent by deleting those values from Di for which the condition is false.  Let this procedure be called Revise(Vi given Vj).  Formally the procedure is as follows:

procedure Revise(Vi given Vj):
    for each x in Di do {
        for each y in Dj do if (x, y) is consistent then next x;
        remove x from Di
        }

Arc consistency is not symmetric in general.  Consider two neighboring countries in a map, say V1 and V2, whose current domains are the sets {red} and {red, blue}.  Then (V1, V2) is arc-consistent but (V2, V1) is not arc-consistent.
 
 

THE AC-3 ALGORITHM

One algorithm that performs Revise repeatedly until no more values can be eliminated from any domain is called AC-3, published by Alan Mackworth in 1977.  AC-3 uses Revise as a subroutine, with a flag to indicate whether each call to Revise(Vi given Vj) actually led to any change in Vi.

procedure Revise(Vi given Vj):
    changedVi := false
    for each x in Di do {
        for each y in Dj do if (x, y) is consistent then next x;
        remove x from Di
        changedVi := true
        }
    return changedVi

procedure AC-3:
    A := { (Vi, Vj) s.t. a constraint links Vi, Vj }
    Q := A
    while Q not empty {
        select and remove one arc (Vk, Vm) from Q
        if Revise(Vk given Vm) == true then
            Q := Q union { (Vi, Vk) in A with i =/= m }
        }

• If the domain Di of any variable is empty, then search should backtrack; the assignments made so far lead to inconsistency.  In this case AC-3 can return immediately.
• If each domain is a singleton set, then these assignments form a consistent solution.
• If all domains are non-empty and at least one domain contains two or more values, then search should continue.

Note that while forward checking can easily be applied to three-way and higher arity constraints, AC-3 constraint propagation is specific to binary constraints.
 
 

A HEURISTIC FOR VARIABLE ORDERING

Note that we have two nested choice points:

• First, we must choose one of the remaining variables.
• Second, we must choose one of the remaining values for this variable.

A good heuristic for reducing computational complexity is always to instantiate next the remaining variable that is most constrained, i.e. the one whose domain contains the fewest remaining values.

Why is this a good idea?  We only need to try one variable, so we would ideally choose the variable that leads to inconsistency being detected the quickest, in order to prune away this whole part of the search tree as quickly as possible.  The most constrained variable is a guess at the ideal variable.

By definition, heuristics are not guaranteed to be effective.  Even when they appear to work in practice, we cannot prove that they will always work, or prove why they work.  It is difficult to do good research on heuristics, because it is difficult to establish conclusions definitively.  For example, the most constrained variable ordering heuristic might be beneficial, but possibly not for the reason suggested above.
 
 

A HEURISTIC FOR VALUE ORDERING

As mentioned above, if a value leads to failure (i.e. inconsistency), we must still try the other values.  Only if a value leads to success (i.e. to a goal node) can we stop searching.  So, we should try first a value that seems most likely to lead to success.  This is a value that causes the smallest reduction in available values for other variables.

In other words, we should choose the value that allows the most flexibility for the still uninstantiated variables.  One way to make this idea precise is as follows:

for each value x of Vi separately, perform forward checking
measure the size of the remaining domains of all uninstantiated variables
sort the values x of Vi according to this measure.