ARC-CONSISTENCY FOR CONTINUOUS-VARIABLES

Davis [1] has investigated the properties of the Waltz propagation algorithm with interval labels in continuous domains. He shows that in most cases the algorithm does not achieve arc-consistency and furthermore is subject to infinite iterations. In this paper, I show that the main reason for Davis' negative results lies in the way he formulates the propagation rule for the Waltz algorithm. For binary constraints, I propose a different propagation rule and show that it guarantees arc-consistency upon quiescence of the propagation. Generalizations to n-ary constraints are possible but involve more complex geometry. Arc-consistency guarantees a minimal network only when the constraint graph is a tree. I show that the new formulation of the propagation algorithm rules out the possibility of infinite iterations for all tree-structured constraint networks, and thus obtain a general and reliable algorithm for arc-consistency in continuous domains.