Synthesizing constraint expressions

ABSTRACT

A constraint network representation is presented for a combinatorial search problem: finding values for a set of variables subject to a set of constraints. A theory of consistency levels in such networks is formulated, which is related to problems of backtrack tree search efficiency. An algorithm is developed that can achieve any level of consistency desired, in order to preprocess the problem for subsequent backtrack search, or to function as an alternative to backtrack search by explicitly determining all solutions.

REFERENCES

• 1: Barrow, H.G., and Tenenbaum, J.M. MSYS: A system for reasoning about scenes. Tech. Note 121, A.I. Ctr., Stanford Research Inst., Menlo Park, Calif., April 1976.
• 2: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 3: Clowes, M.B. On seeing things. Artif Intell. 2 (1971), 79-116.
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: Fikes, R.E. REF-ARF: A system for solving problems stated as procedures. Artif. Intell. 1, 1(1970), 27-120.
• 6: Freuder, E.C. Synthesizing constraint expressions, A.I. Memo 370, A.I. Lab., M.I.T., Cambridge, Mass., 1976.
• 7: R. W. Grossman, SOME DATA BASE APPLICATIONS OF CONSTRAINT EXPRESSIONS, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 8: HoIn, B.K.P. Determining lightness from an image. Comptr. Graphics and Image Processing 3, 4(Dec. 1974), 277-299.
• 9: Huffman, D.A. Impossible objects as nonsense sentences. In Machine Intelligence 6, B. Meltzer and D. Michie, Eds., Edinburgh U. Press, Edinburgh, 1971, pp. 295-323.
• 10: Mackworth, A.K. Consistency in networks of relations. Artif. Intell. 8, 1(1977), 99-118.
• 11: Marr, D. Simple memory: A theory for archicortex. Philos. Trans. Roy. Soc. B. 252 (1971), 23-81.
• 12: D. Marr , T. Poggio, Cooperative Computation of Stereo Disparity, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 13: Minsky, M., and Papert, S. Perceptrons. M.I.T. Press, Cambridge, Mass., 1968.
• 14: Montanari, U. Networks of constraints: Fundamental properties and applications to picture processing. Inform. Sci. 7, 2(April 1974), 95-132.
• 15: Rosenfeld, A., Hummel, R., and Zucker, S.W. Scene labelling by relaxation operations. IEEE Trans. Systems, Man, and Cybernetics SMC-6, 6(June 1976), 420-433.
• 16: Sussman, G.J., and McDermott, D.V. From PLANNER to CONNIVER--a genetic approach. Proc. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 1171-1179.
• 17: Sussman, G.J., and Stallman, R.M. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. A.I. Memo 380, A.I. Lab., M.I.T., Cambridge, Mass., 1976.
• 18: Tenenbaum, J.M., and Barrow, H.G. IGS: A paradigm for integrating image segmentation and interpretation. In Pattern Recognition and Artificial Intelligence, C. H. Chen, Ed., Academic Press, New York, 1976, pp. 472-507.
• 19: Ullman, J.R. Associating parts of patterns. Inform. and Control 9, 6(Dec. 1966), 583-601.
• 20: Ullman, J. R. Pattern Recognition Techniques. Crane Russak, New York, 1973.
• 21: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 22: Stephen H. Unger, GIT—a heuristic program for testing pairs of directed line graphs for isomorphism, Communications of the ACM, v.7 n.1, p.26-34, Jan. 1964 [doi>10.1145/363872.363899]
• 23: David L. Waltz, Generating Semantic Descriptions From Drawings of Scenes With Shadows, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 24: Zucker, S.W. Relaxation labelling, local ambiguity, and low-level vision. In Pattern Recognition and Artificial Intelligence, C. H. Chen, Ed., Academic Press, New York, 1976, pp. 593-616.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking; Graph and tree search strategies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
backtrack, combinatorial algorithms, constraint networks, constraint satisfaction, graph coloring, network consistency, relaxation, scene labeling, search