Proceedings

An Efficient Arc Consistency Algorithm for a Class of CSP Problems

Download BibTeX Cite

Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 325-329.

© 1991 International Joint Conferences on Artificial Intelligence

Abstract

Consistency Techniques have been studied extensively in the past as a way of tackling Constraint Satisfaction Problems (CSP). In particular various arc consistency algorithms have been proposed, originating from Waltz's filtering algorithm [20] and culminating in the optimal algorithm AC-4 of Mohr and Henderson [13]. AC-4 runs in O(ed 2 ) in the worst case where e is the number of arcs (or constraints) and d is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints. In this paper, we present a new generic arc consistency algorithm AC-5. The algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC4. More important, AC-5 can be instantiated to produce an 0(ed) algorithm for two important classes of constraints: functional and monotonic constraints. We et.lso show that AC-5 has an important application in Constraint Logic Programming over Finite Domains [18]. The kernel of the constraint-solver for such a programming language is an arc consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time O(ed).

  1. R. Decbter and J. Pearl. Network-baaed heuristics for constraint satisfaction problema. Artificial Intelligence, 34:1-38, 1988.
  2. M . Dincbaa, H. Simonis, and P. Van Hentenryck. Solving Lar11e Combinatorial Problema in Logic Programming. Journal of Log•c Programming, S(l-:1):75-93, 1990.
  3. M. Dincbaa and al. The Constraint Logic Programming Language CHIP. In FGCS-88, Tokyo, 1988.
  4. E.C. Freuder. Syntheai•ing Constraint Expressions. CACM, :11:958-966, 1978.
  5. J. Gaachnig. A Constraint Satisfaction Method for Inference Mak- ing. In Annual Conf. on Circuit S111tem Theof11, 1974.
  6. R.M. Haralick and G.L. Elliot. Increasing Tree Search Effi- ciency for Constraint Satisfaction Problema. Artificial Intelli- gence, 14:~63-313, 1980.
  7. J. Jaffar and S. MichayloY. Methodology and Implementation of a CLP System. In ICLP-87, Melbourne 1987.
  8. S. Kaaif. On the Parallel Complexity of Discrete Relaxation in Constraint Satisfaction Networks. AI Journa~ 45:~75-~86, 1990.
  9. J-L. Lauriere. A Language and a Program for Statin' and SolYing Combinatorial Problema. Artificial Intelligence, lOp), 1978.
  10. A.K. Mack worth. Consistency in Networks of Relations. AI Jour- na~ 8{1):99-118, 1977.
  11. A.K. Mackworth. Con1traint Sati•faction, Yolume Encyclopedia of Artificial Intelligence. Wiley, 1987. [1:1)
  12. A.K. Mackworth and E. C. Freuder. The Complexity of some Poly- nomial Network Consistency Algorithms for Constraint Satisfac- tion Problema. Artificial Intelligence, ~5:65-74, 1985.
  13. R. Mohr and T .C. Henderson. Arc and Path Consistency ReYis- ited. Artificial Intelligence, :18 : ~~5-~33, 1986.
  14. U . Montanari. Networks of Constraints: Fundamental Properties and Applications to Picture Processing. Information Science, 7(~) : 95-13:1, 1974.
  15. Montanari, U and Rossi, F. Constraint Relaxation May Be Perfect In To Appear in Artificial Intelligence.
  16. B. Nadel. Constraint Satisfaction Algorithms . Computational Intelligence, 5( 4):~88-~~4, 1989.
  17. P. Van Hentenryck. A Framework for Consistency Techniques in Logic Programming. In IJCAI-87, Milan, 1987.
  18. P. Van Hentenryck. Con1traint Sati•faction in Logic Program- ming. The MIT Press, Cambridge, MA, 1989.
  19. P. Van Hentenryck and M. Dincbaa. Domains in Logic Program- ming. In AAAI-86, Philadelphia, PA, August 1986.
  20. D. Walt.. Generating Semantic Descriptions from Drawings of Scenes with Shadows. Technical Report Al271, MIT, MA, 1972.

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

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