Skedbooks
←
Artificial Intelligence

Consistency Driven Techniques

Consistency Driven Techniques: Consistency techniques effectively rule out many inconsistent labeling at a very early stage, and thus cut short the search for consistent labeling. These techniques have since proved to be effective on a wide variety of hard search problems. The consistency techniques are deterministic, as opposed to the search which is non-deterministic. Thus the deterministic computation is performed as soon as possible and non-deterministic computation during search is used only when there is no more propagation to done. Nevertheless, the consistency techniques are rarely used alone to solve constraint satisfaction problem completely (but they could).
In binary CSPs, various consistency techniques for constraint graphs were introduced to prune the search space. The consistency-enforcing algorithm makes any partial solution of a small subnetwork extensible to some surrounding network. Thus, the potential inconsistency is detected as soon as possible.

Node Consistency: The simplest consistency technique is refered to as node consistency and we mentioned it in the section on binarization of constraints. The node representing a variable V in constraint graph is node consistent if for every value x in the current domain of V, each unary constraint on V is satisfied. If the domain D of a variable V containts a value "a" that does not satisfy the unary constraint on V, then the instantiation of V to "a" will always result in immediate failure. Thus, the node inconsistency can be eliminated by simply removing those values from the domain D of each variable V that do not satisfy unary constraint on V.

Arc Consistency: If the constraint graph is node consistent then unary constraints can be removed because they all are satisfied. As we are working with the binary CSP, there remains to ensure consistency of binary constraints. In the constraint graph, binary constraint corresponds to arc, therefore this type of consistency is called arc consistency. Arc (Vi,Vj) is arc consistent if for every value x the current domain of Vi there is some value y in the domain of Vj such that Vi=x and Vj=y is permitted by the binary constraint between Vi and Vj. Note, that the concept of arc-consistency is directional, i.e., if an arc (Vi,Vj) is consistent, than it does not automatically mean that (Vj,Vi) is also consistent. Clearly, an arc (Vi,Vj) can be made consistent by simply deleting those values from the domain of Vi for which there does not exist corresponding value in the domain of Dj such that the binary constraint between Vi and Vj is satisfied (note, that deleting of such values does not eliminate any solution of the original CSP).

The following algorithm does precisely that.

Algorithm REVISE

  1. procedure REVISE(Vi,Vj)
  2. DELETE <- false;
  3. for each X in Di do
  4. if there is no such Y in Dj such that (X,Y) is consistent, then
  5. delete X from Di;
  6. DELETE <- true;
  7. endif;
  8. endfor;
  9. return DELETE;
  10. end REVISE

To make every arc of the constraint graph consistent, it is not sufficient to execute REVISE for each arc just once. Once REVISE reduces the domain of some variable Vi, then each previously revised arc (Vj,Vi) has to be revised again, because some of the members of the domain of Vj may no longer be compatible with any remaining members of the revised domain of Vi. The following algorithm, known as AC-1, does precisely that.

Algorithm AC-1

  1. procedure AC-1
  2. Q <- {(Vi,Vj) in arcs(G),i#j};
  3. repeat CHANGE <- false;
  4. for each (Vi,Vj) in Q do
  5. CHANGE <- REVISE(Vi,Vj) or CHANGE;
  6. endfor
  7. until not(CHANGE)
  8. end AC-1

This algorithm is not very efficient because the succesfull revision of even one arc in some iteration forces all the arcs to be revised again in the next iteration, even though only a small number of them are really affected by this revision. Visibly, the only arcs affected by the reduction of the domain of Vk are the arcs (Vi,Vk). Also, if we revise the arc (Vk,Vm) and the domain of Vk is reduced, it is not necessary to re-revise the arc (Vm,Vk) because non of the elements deleted from the domain of Vk provided support for any value in the current domain of Vm. The following variation of arc consistency algorithm, called AC-3, removes this drawback of AC-1 and performs re-revision only for those arcs that are possibly affected by a previous revision.

Algorithm AC-3

  1. procedure AC-3
  2. Q <- {(Vi,Vj) in arcs(G),i#j};
  3. while not Q empty
  4. select and delete any arc (Vk,Vm) from Q;
  5. if REVISE(Vk,Vm) then
  6. Q <- Q union {(Vi,Vk) such that (Vi,Vk) in
  7. arcs(G),i#k,i#m}
  8. endif
  9. endwhile
  10. end AC-3

When the algorithm AC-3 revises the edge for the second time it re-tests many pairs of values which are already known (from the previous iteration) to be consistent or inconsistent respectively and which are not affected by the reduction of the domain. As this is a source of potential inefficiency, the algorithm AC-4 was introduced to refine handling of edges (constraints). The algorithm works with indiviual pairs of values as the following example shows.