Proceedings

Local Consistency for Ternary Numeric Constraints

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 392-396.

© 1997 International Joint Conferences on Artificial Intelligence

Abstract

We consider algorithms of the Waltz type for computing local consistency (also called arcconsistency) for constraints over numeric domains. Many commonly used propagation rules do not in fact enforce local consistency. We extend the propa&ation rule given by Faltings [Faltings, 1994j to the case of ternary constraints. Since any general n-ary continuous constraint can be represented as a collection of ternary ones, this also covers n-ary constraints in general. We show how the propagation can be implemented efficiently. The new algorithm gives significantly tighter labellings than previous propagation algorithms on most problems.

  1. -10, 10) l-10, 10J l-10, 101 x2 [-10, 7.2] [-10,10] [-8, 85, 7.2] x3 [-10, 10] [-10,10] [-10,10] x~ [-10, 5.25] [-10, 5.25] [-10, 5.25] x6 [-6.86, 7.33] [-10, 7.33] [ -5.35, 7.33] Xe [-10, 10] [-10,10] [-9 .84, 10] x1 [-9.4, 10] [-10,10] [-9.4, 10] Xs [-10, 9.4] [-10, 10] [-10, 7.16] Xs [-4.6, 10] [-4.6, 10] [-3.41, 10] X1o [-10, 10] [-10, 10] [-10,10]
  2. [Benhamou et al., 1994] F. Benhamou, D. McAllester, P. Van Henten- ryck: "CLP(Intervals) Revisited," Technical Report No. CS-94-18, Universite Aix-Marseille, April 1994
  3. [Davis, 1987] Ernest Davis: "Constraint Propagation with Interval Labels," Artificial Intelligence 32, 1987, pp. 281-331
  4. [Faltings, 1994] Boi Faltings: "Arc-consistency for continous variables," Artificial Intelligence 65, 1994, pp. 363-376
  5. [Freuder, 1982] Eugene Freuder: "A sufficient condi- tion for backtrack-free search," Journal of the ACM 29(1), 1982, pp. 24-32
  6. [Hyvonen, 1992] E. Hyvonen: "Constraint reasoning based on interval arithmetic: the tolerance propaga- tion approach," Artificial Intelligence 58(1992), pp. 71-112 [
  7. [Lhomme, 1993] Lhomme: "Consistency Tech- niques for Numeric CSPs," Proceedings of the 13th IJCAI, 1993, pp. 232-238 IJCAI
  8. [Sam-Haroud and Faltings, 1996] Djamila Sam- Haroud, Boi Faltings: "Consistency Techniques for Continous Constraints," Constraints 1(1), 1996, pp. 85-118
  9. [Waltz, 1975] David Waltz: "Understanding line drawings • of scenes with shadows," in P.H. Win- ston( ed. ): The Psychology of Computer Vision, McGraw-Hill, NY 1975

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards