5 CSP II

• efficient solutions for csps
  • ordering
  • filtering
  • structure
    • If there is a way to exploit the constraints and build the graph in a particular way, then maybe we can find a better solution

RECAP

• CSP recap
  • variables
  • domains
  • constraints
    • implicit (provide code to compute)
    • explicit (provide a list of n-legal tuples)
    • Unary/Binary/N-ary

• Goals

  • Here: find any solution
  • Also: find all, find best, etc

• Backtracking search

function BACKTRACKING-SEARCH(csp): # returns solution/failure
    return RECURSIVE-BACKTRACKING({}, csp)

function RECURSIVE-BACKTRACKING(assignment, csp): # returns soln/failure
    if assignment is complete: return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    for value in ORDER-DOMAIN-VALUES(var, assignment, csp):
        if value is consistent with assignment:
            add {var = value} to assignment
            result ← RECURSIVE-BACKTRACKING(assignment, csp)
            if result ≠ failure: return result
            remove {var = value} from assignment
    return failure

We don't wanna explore the tree on every level like DFS, because we dont have to keep track of a row or a path like BFS or DFS. So this one keeps track of a path from the goal to the root.

Tree search vs graph search

general state-space search vs using a tree

There's another reason why we can write such a simple search

What are the properties of DFS that are useful? What isn't?

IMPROVING BACKTRACKING

• General-purpose ideas give huge gains in speed...but it's all NP-Hard
  • Filtering: can we detect inevitable failure early?
  • Ordering
    • Which variable should be assigned next? (MRV)
    • In what order should its values be tried? (LCV)
  • Structure: Can we exploit the problem structure?

WHAT IS ARC CONSISTENCY - An arc X->Y is consistent iff for every x in the tail, there is some y in the head which could be assigned without violating a constraint (head = the arrow!) - A simple form of propagation makes sure all arcs are consistent - arc consistency detects failure earlier than forward checking - Important: if X loses a value, the neighbors of X need to be rechecked - must return after each assignment

Enforcing the Arc Consistency of a CSP

function AC_3(csp) # returns the csp, possibly with reduced domains
    inputs: csp # a binary csp with variables {x1, x2, x3, ...}
    local variables: queue # a queue of arcs initially all the arcs in csp
    while queue is not empty:
        (xi, xj) = REMOVE_FIRST(queue)
        if REMOVE_INCONSISTENT_VALUES(xi, xj):
            for each xk in NEIGHBORS[xi]:
                add (xk, xi) to queue

function REMOVE_INCONSISTENT_VALUES(xi, xj) # returns true iff succeeds
    removed = false
    for each x in DOMAIN[xi]:
        If no y in DOMAIN[xj] where (x, y) satisfies xi<->xj.
            delete x from DOMAIN[xi]: removed = true
    return removed

runtime: \(O(n^2d^3)\) can be reduced to \(O(n^2d^2)\)

Can you explain how this works

In the worst case, there are n^2 in the queue; then it's just those. But if we add back to the queue the items we deleted, we get d.

K-consistency

• increasing degrees
  • 1-consistency: every single node's domain has a value that meets that node's unary constraints
  • 2-consistency (arc consistency): for each pair of nodes, any consistent assignment to one can be extended to the other
    • The way we said this before: for any assignment to the tail, there is an assignment to the head
  • K-consistency: for each K nodes, any consistent assignment to k-1 can be extended to the kth node
• higher k is more expensive to compute, but makes filtering better (trade-off)

stronger definition of consistency - If a graph is k-consistent, at any n levels down, it is also consistent. - If it is k-consistent, it is also k-1, k-2, k-n consistent - Strong n-consistency means we can solve without backtracing - Why - Choose any assignment to any variable - Choose a new variable - By 2 consistency, there is a choice consistent with the first - Choose a new variable - by 3 consistency, there is a consistent choice for the first 2 - ... - Establishing strong n-consistency is great but very expensive. - strong consistent: - - lots of middle ground between arc consistency and n-consistency

FILTERING:

ORDERING:

• variable ordering: minimum remaining values
  • Choose the variable with the fewest legal values left in the domain
• Why min rather than max?
• also called "most constrained variable"

• "fail fast" ordering

• Least constraining value

  • Given a choice of variable, choose the least constraining value
  • i.e the one that rules out the lowest values in the remaining variables
  • Note that it may take more computation to determine (rerunning filtering)
• Why least rather than most
• Combining these ordering ideas makes 1000 queens feasible

STRUCTURE:

• Up until now, we just had a graph representation, so we haven't really used the graph in any other meaningful way.
• an extreme case: independent subproblems:
  • Tasmania and mainland Australia do not interact, so the graph has two unconnected components
• independent subproblems are identifiable as connected components of a constraint graph
• Suppose a graph of n variables can be broken into subproblems of only c variables
  • The worst-case solution cost is \(O((n/c)(d^c))\)
  • eg n = 80, d = 2, c = 20
  • \(2^{80}\) = 4 billion years at 10 million nodes per second (yikes)
  • (4)2^20 = 0.4 s at 10 million nodes per second (much better)

Tree strucutred CSPs - theorem: if the constraint graph has no loops, the CSP can be solved in \(O(nd^2)\) time - compare to general csps where worst-case is \(O(d^n)\) - this property also applies to probabilistc reasoning (later): an expme of the relation between syntactic...

• algorithm for tree structured CSPs
  • order: choose a root variable, order variables so that parents precede children
  • remove backward: for i = n : 2, apply RemoveInconsistent(parent(xi), xi)
  • assign forward: for i = 1 : n, assign xi consistenly with parent(xi)
• runtime: \(O(nd^2\))