Arc-consistency for continuous variables

✍ Scribed by Boi Faltings

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 703 KB
• Volume: 65
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(94)90022-1

✦ Synopsis

Faltings, B., Arc-consistency for continuous variables (Research Note), Artificial Intelligence 65 (1994) 363-376. 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.