CS 4365 CSP

Constraint satisfaction problems (CSP) on finite domains are typically solved using a form of search: ?, ?, ?

backtracking,

constraint propagation, local search.

In CSP, ? is a recursive algorithm. It maintains a partial assignment of the variables. In this algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned.

backtracking

In CSP, every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is called ?

constraint propagation

Arc-consistency and path-consistency are the most known and used forms of ?

local consistency

? is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied.

Local search

A type of constraint which restricts the value of a single variable is ?

unary constraint

A constraint involving an arbitrary number of variable is called ?

global constraint

In constraint hypergraph a hyper-node represents ?

n-ary constraints

? is a type of inference: using constraints to reduce the number of legal values in CSP

Constraint propagation

The key idea to reduce the number of legal values in CSP is ?

local consistency

A variable in a CSP is ? if all the values in the variable's domain satisfy the variable's unary constraints.

node-consistent

A variable in a CSP is ? if every value in its domain satisfies the variable's binary constraints.

arc-consistent

The most popular algorithm for arc-consistent is called ?

AC-3 algorithm

Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Then the complexity of AC-3 algorithm for the worst case time is ?

O(c*d*d*d)

? tightens down the domains (unary constraints) using the binary constraints.

Arc consistency

? tightens down the binary constraints using implicit constraints that are inferred by looking at triples of variables.

Path consistency

A CSP is ? if, for any set of k-1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any k-th variable.

k-consistent

A CSP is strongly k-consistent if it is k-consistent and is also x-consistent for all x which is ?

greater than 0 and less than k

Assume a CSP with n variables, each with domain size at most d, and with c binary constraints (arcs). Then the worst case time-complexity for any algorithm to check n-consistency is ?

O(e^n)

The Alldiff constraint in CSP says that all the variables (Vars) involved must have distinct values (as discussed in book and class). In SWI-Prolog CLP, it is done through ?

all_different(Vars)

One important higher-order constraint is the resource constraint, sometimes called the Atmost constraint. For example in a scheduling problem, let P1, P2, P3, P4 denote the numbers of personnel assigned to each of four tasks. The constraint that no more than 10 personnel are assigned in total is written as ?

Atmost(10, P1, P2, P3, P4)

A CSP is ? if for every variable X, and for both the lower-bound and upper-bound values of X, there exists some value of Y that satisfies the constraint between X and Y for every variable Y.

bounds consistent

Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. For a CSP with n variables of domain size d, one may generate a tree with ? leaves. That is, n factorial times (d to the power of n).

O(n! * (d^n))

Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. For a CSP with n variables of domain size d, there are only ? possible complete assignments.

O(d^n)

Applying a standard depth-first search for a CSP problem, a state would be a partial assignment where each action (generating a child node) is to assign a value (from a domain of size d) to a variable. In particular, a CSP problem is ? if the order of application of any given set of actions has no effect on the outcome.

commutative

? search is used for a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign.

Backtracking

The intuitive idea of choosing the variable with the fewest legal values is called the ?heuristics.

minimum-remaining-values (MRV)

This ? attempts to reduce the branching factor on future choices by selecting the variable that is involved in the largest number of constraints on other unassigned variables.

degree heuristic

The ? heuristic can be effective in some cases as it prefers the value that rules out the fewest choices for the neighboring variables in constraint graph.

Least Constraint Value (LCV)

Although forward checking detects many inconsistencies, it does not detect all of them. The problem is that it makes the current variable arc-consistent, but does not look ahead and make all the other variables arc-consistent. The ? algorithm detects this inconsistency.

Maintaining Arc Consistency (MAC)

The ? method backtracks to the most recent assignment in the conflict set.

backjumping

In choosing a new value for a variable, the most obvious heuristic is to select the value that results in the minimum number of conflicts with other variables. This is ? in local search for CSP.

min conflicts heuristics

One efficient heuristic to solve a complicated case of CSP graph is to make it a tree after removal of a subset S of the CSP's variables, and first to find each possible assignment to the variables in S to solve all the constraints on S. Here S is called a ?.

cycle cutset

If each variable domain is of size d and there are e constraints to be tested, then the algorithm GAC does ? consistency checks.

O(ed^3)