CSCE 420 Lecture 9

« previous | Tuesday, February 12, 2013 | next »

CSP

Backtracking

Choose random variable, set it to random value, and continue with remaining variables/values until constraint is violated (backtrack) or no variables remain (complete)

Forward Checking

Every time we make a choice ($x_i=v_i$), we remove inconsistent values from domain of "neighboring" (in constraint graph) variables.

Constraint-Propagation: update the remaining choices of other nodes, and backtrack if any node has no choices left in domain.

Take advantage of heuristics by changing order of variables and values

• Minimum Remaining Values (MRV): Choose variable with fewest values remaining in domain; thereby reducing effective branching factor
• Least Constraining Value (LCV): Choose value that has least effect on neigboring variables

Arc-Consistency

A constraint graph is arc-consistent if for every edge $(x_i,x_j)$ and for every value in the domain of $x_i$, there is some value $v_j$ in the domain of $x_j$ that is consistent

For example, the following graph is arc-consistent:

          X1 != X2
X1(0,1) ------------ X2(0,1)
  |
  | X1 != X3
  |
X3(0,1)

and the following graph is not:

          X1 != X2
X1(0,1) ------------ X2(0,1)
  |
  | X1 != X3
  |
X3(1)

Algorithm: AC-3

Makes a graph arc-consistent by mantaining a queue of edges for the graph

def ac3 csp, start_node = nil
  queue = start_node.nil? ? csp.graph.nodes[start_node].neighbors : Queue.new(csp.graph.edges)
  until queue.empty?
    edge = queue.pop
    # remove value v_i from csp.domain[edge.source] that do not have consistent choice in csp.domain[edge.domain]
    return false if csp.domain[edge.source].empty? # inconsistent
    edge.source.neighbors.each { |neighbor| queue.push Edge.new(neighbor, edge.source) }
  end

  return true # reduced domains
end

AC-3 does not solve constraint satisfaction problem, but it can be used:

1. as a preprocessing agent (before search)
2. interleaved between choice selections during search (Make Arc-Consistent (MAC))

Algorithm: Make Arc-Consistent

Time complexity

$O(n^{2}d)$, where $n$ is the number of variables and $d$ is the max domain size.

Also depends on number of constraints ($O(n^2)$), so running time may actually be $O(n^4)$

BUT CSP IS NP-COMPLETE!?

MAC: Four Queens Problem

Pass 0: AC3 does nothing; complete constraint graph
C = 3
Pass 1:
    init queue (A,C), (B,C), (D,C)
    pop (A,C) -- dom(A) \= {1,3}      (note: \= is 'set-minus equal')
    push (B,A), (C,A), (D,A)
    pop (B,A) -- dom(B) \= {3}
    push (A,B), (C,B), (D,B)
    pop (A,B) -- no change
    pop (C,B) -- already done
    pop (D,B) -- no change
    pop (C,A) -- already done
    pop (D,A) -- already done
    pop (B,C) -- dom(B) \= {2,4}
    push (A,B), (C,B), (D,B)
    ...
    pop (D,C)
    ...
    return false
C = 4
Pass 2:
...