Recap: CSP algorithm

For each variable X, maintain set D(X) containing all possible values for X.

Run DFS. At each search step:

• Pick a value for one variable. (Back up if no choices are available.)
• Forward checking: prune all the sets D(X) to remove violations of constraints

We may have multi-variate constraints, e.g. sudoku row/column/block values all different. However, let's consider only two-variable constraints for now.

Heuristics for variable assignments

Which variable should we pick?

• Variable with fewest remaining values
• If there are ties, which variable constrains the most other variables (aka degree of node in constraint graph)

Suppose we are coloring the following graph with 3 colors (R,G,B).

     1-----2----3
      \    |   / \
       \   |  /   \ 
        \--4------ 5
            \     /
             \   /
               6

Suppose we color nodes 1 and 2:

     R-----G----3
      \    |   / \
       \   |  /   \ 
        \--4------ 5
            \     /
             \   /
               6

Our first heuristic means that we should color 4 next.

By our second heuristic, we should have started with node 4, because it has the highest degree:

     1-----2----3
      \    |   / \
       \   |  /   \ 
        \--R------ 5
            \     /
             \   /
               6

Which value do we give to the chosen variable?

• The one that leaves the most options open for other variables.

For example, in this graph

       R-----G
       |     |
       |     |
       3-----4

we should use G for node 3 rather than B, because that leaves two color options for node 4.

When we assign a value to variable X, forward checking only checks variables that share a constraint with X, i.e. are adjacent in the constraint graph.

Suppose we are coloring this graph with {R,G,B} and we have just colored one node

     R-----2----3
      \    |   / \
       \   |  /   \ 
        \--4------ 5
            \     /
             \   /
               6

Then forward checking removes R from D(2) and D(4). Suppose we then color node 3 as follows

     R-----2----G
      \    |   / \
       \   |  /   \ 
        \--4------ 5
            \     /
             \   /
               6

Forward checking adjusts the neighbors of the newly assigned node. So D(2) and D(4) become {B}, D(5) becomes {R,B} But then forward checking stops.

Constraint propagation does the same kind of pruning, but keeps going and looks at neighbors of any nodes whose domain has changed. It only stops when it finds no more changes.

In this case,

• D(4) = {B} implies that D(5) must be reduced to {R}. So then means that D(6) will be reduced (in two steps) to {G}.
• D(2) = D(4) = {B} is inconsistent. So the first one considered will have its domain reduced to the empty set.

The ordering of these updates is not entirely determined. But our constraint checking tells us that the coloring can't be completed and we need to backtrack.

Using constraint propagation

Constraint propagation greatly reduces the number of assignments we need to search. Also it detects failure (triggers backtracking) much earlier. It can be used at two points in the search

• At the start of search
• Upgrade to forward checking in backtracking search

Sometimes constraint propagation can completely solve a problem by itself. Line labelling from Lana Lazebnik based on David Waltz's 1972 thesis. Contemporary video of the solver in action.

AC-3

Fullly working contraint propagation algorithm AC-3, by David Waltz and Alan Mackworth (1977).

The constraints themselves are symmetric (aka not directional). However, we view constraints between variables ("arcs") as ORDERED pairs. So the pair (X,Y) will represent contraint flowing from Y to X.

Revise(X,Y) prunes values of D(X) that are inconsistent with what's currently in D(Y).

Maintain queue of pairs ("arcs") that still need attention.

Initialize queue. Two options

• all constraint arcs in problem [for starting up a new CSP search]
• all arcs (X,Y) where Y's value was just set [for use during CSP search]

Loop:

• Remove (X,Y) from queue. Call Revise(X,Y).
• If D(X) has become empty, halt returning a value that forces main algorithm to backtrack.
• If D(X) changed, push (C,X) onto the queue for every C that shares a constraint with X, but don't push (Y,X).

Stop when queue is empty

Exercise for the reader

Near the end of AC-3, we push all arcs (C,X) onto the queue, but we don't push (Y,X). Why don't we need to push (Y,X)?

Hill climbing

Another approach to CSP problems involves randomly picking a full set of variable assignments, then trying to tweak it into a legal solution. At each step, we change the value of one variable to try to reduce the number of conflicts.

Hill-climbing n-queens (from Lana Lazebnik, Fall 2017).

This seems to be how people solve certain complicated graph-coloring problems such as avoiding/reducing conflicts in final exam scheduling.

Hill climbing can be very effective, but it can get stuck in local optima. So algorithms often add some randomization:

• Randomly pick a new starting configuration when apparently stuck.
• Add a random component to the movement algorithm, so it sometimes moves to a higher-cost configuration ("simulated annealing").

AI in action

Maybe speech recognition caused unwanted dollhouse orders or maybe it never happened.