Constraint Propagation Techniques

Constraint Propagation Techniques

• While selecting unassigned variable for computation if we look at some of the constraints earlier in the search (or even before search begins), we can drastically reduce search space. Following are techniques which are helpful for earlier constraints checks.

Forward Checking (FC)

1. Forward checking is one of the potential technique which uses constraints more effectively during search.

2. It removes values in neighbouring unassigned variables domain that conflict with assigned variable.

3. Forward checking uses MRV to select assigned variable.

4. Backtracking search is performed if failure occurs.

5. Search terminates when any variable has no legal values.

6. Generic method, do

i) Assigns variable X.

ii) Forward checking remarks unassigned variable Y connected to X.

iii) Remove values from D, where value is inconsistent with X.

Constraint Propagation

1. A combined approach of heuristic plus forward checking gives more reliable, accurate and efficient results than a singular approch.

2. The forward checking propagates information from assigned to unassigned variables but can not avoid or detect all failure.

3. Constraint propagation repeatedly enforces constraints locally.

4. The idea of arc consistency provides a fast method of constraint propagation that is substantially stronger than forward checking. Here "arc" refers to a directed arc in the constraint graph.

Constraint Propagation using Arc Consistency

1. It is fast method of constraint propagation.

2. X→Y is consistent if (for every value of X there is some allowed value Y. For (a) example [V₂ → V₁, is consistent iff V₁ = Red, V₂ = Blue] (i.e. for every value of x in X there is some allowed value y in Y). This is directed property example - [V₁ = V₂]

V₁ = V₂ is consistent iff

V₁ = Red and V₂ = Blue

3. As directed arcs between variables represent the domains of specified variables, they are consistent with each other.

4. Constraint propagation can be applied as preprocessing or propagation step.

i) Before search- Preprocessing.

ii) After search- Propagation.

5. The procedure for maintaining arc consistency, can be applied repeatedly.

Constraint Propagation using K-consistency

1. Arc consistency is not capable of detecing all inconsistencies. Partial assignments [V₁ = Red, V₂ = Red] are inconsistent.

2. K-consistency is very strong form of constraint propagation.

3. A CSP is K-consistency if for any set of K-1 variables and for any consistent assignment to those variable a consistent value can always be assigned to any K^th variable.

Note

1. Consistency means that each individual variable by itself is consistent; this is also called as node consistency.

2. Consistency is the same as arc consistency.

3. Consistency means that any pair of adjacent-variables can always be extended toa third neighboring variable; this is also called as path consistency.

4. Strongly, K-consistency graph exhibit some properties mentioned below -

i) It is K-consistent.

ii) It is also (K-1) consistent, (K-2) consistent all the way down to 1 consistent. 5. This is an idealist solution which requires O (nd) time instead of O (n² d³).