Constraint tightness and looseness versus local and global consistency

ABSTRACT

Constraint networks are a simple representation and reasoning framework with diverse applications. In this paper, we identify two new complementary properties on the restrictiveness of the constraints in a network—constraint tightness and constraint looseness—and we show their usefulness for estimating the level of local consistency needed to ensure global consistency, and for estimating the level of local consistency present in a network. In particular, we present a sufficient condition, based on constraint tightness and the level of local consistency, that guarantees that a solution can be found in a backtrack-free manner. The condition can be useful in applications where a knowledge base will be queried over and over and the preprocessing costs can be amortized over many queries. We also present a sufficient condition for local consistency, based on constraint looseness, that is straightforward and inexpensive to determine. The condition can be used to estimate the level of local consistency of a network. This in turn can be used in deciding whether it would be useful to preprocess the network before a backtracking search, and in deciding which local consistency conditions, if any, still need to be enforced if we want to ensure that a solution can be found in a backtrack-free manner. Two definitions of local consistency are employed in characterizing the conditions: the traditional variable-based notion and a recently introduced definition of local consistency called relational consistency.

REFERENCES

• 1: CHEESEMAN, P., KANEFSKY, B., AND TAYLOR, W.M. 1991. Where the really hard problems are. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (Sydney, Australia). Morgan Kaufmann, San Mateo, Calif., pp. 331-337.
• 2: M. C. Cooper, An optimal k-consistency algorithm, Artificial Intelligence, v.41 n.1, p.89-95, Nov. 1989 [doi>10.1016/0004-3702(89)90080-5]
• 3: Martin C. Cooper , David A. Cohen , Peter G. Jeavons, Characterising tractable constraints, Artificial Intelligence, v.65 n.2, p.347-361, Feb. 1994 [doi>10.1016/0004-3702(94)90021-3]
• 4: Rina Dechter, Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition, Artificial Intelligence, v.41 n.3, p.273-312, Jan. 1990 [doi>10.1016/0004-3702(90)90046-3]
• 5: Rina Dechter, From local to global consistency, Artificial Intelligence, v.55 n.1, p.87-107, May 1992 [doi>10.1016/0004-3702(92)90043-W]
• 6: R. Dechter , J. Pearl, Network-based heuristics for constraint-satisfaction problems, Artificial Intelligence, v.34 n.1, p.1-38, Dec. 1987 [doi>10.1016/0004-3702(87)90002-6]
• 7: Rina Dechter , Judea Pearl, Tree clustering for constraint networks (research note), Artificial Intelligence, v.38 n.3, p.353-366, April 1989 [doi>10.1016/0004-3702(89)90037-4]
• 8: Rina Dechter , Itay Meiri, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artificial Intelligence, v.68 n.2, p.211-241, Aug. 1994 [doi>10.1016/0004-3702(94)90068-X]
• 9: Rina Dechter , Peter van Beek, Local and global relational consistency, Theoretical Computer Science, v.173 n.1, p.283-308, Feb. 1997 [doi>10.1016/S0304-3975(97)86737-0]
• 10: Eugene C. Freuder, Synthesizing constraint expressions, Communications of the ACM, v.21 n.11, p.958-966, Nov. 1978 [doi>10.1145/359642.359654]
• 11: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• 12: Eugene C. Freuder, A sufficient condition for backtrack-bounded search, Journal of the ACM (JACM), v.32 n.4, p.755-761, Oct. 1985 [doi>10.1145/4221.4225]
• 13: GASCHNIG, J. 1978. Experimental case studies of backtrack vs. waltz-type vs. new algorithms for satisfying assignment problems. In Proceedings of the 2nd Canadian Conference on Artificial Intelligence (Toronto, Ont., Canada). pp. 268-277.
• 14: HARALICK, R. M., AND ELLIOTT, G. L. 1980. Increasing tree search efficiency for constraint satisfaction problems. Artif. Int. 14, 263-313.
• 15: JEAVONS, P., COHEN, D., AND GYSSENS, M. 1996. A test for tractability. In Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (Cambridge, Mass.). Lecture Notes in Computer Science, vol. 1118. Springer-Verlag, New York, pp. 267-281.
• 16: Lefteris M. Kirousis, Fast parallel constraint satisfaction, Artificial Intelligence, v.64 n.1, p.147-160, Nov. 1993 [doi>10.1016/0004-3702(93)90063-H]
• 17: MACKWORTH, A.K. 1977. Consistency in networks of relations. Artif. Int. 8, 99-118.
• 18: MACKWORTH, A. K. 1987. Constraint satisfaction. In Encyclopedia of Artificial Intelligence, S. C. Shapiro, ed. Wiley, New York.
• 19: Alan K. Mackworth, The logic of constraint satisfaction, Artificial Intelligence, v.58 n.1-3, p.3-20, Dec. 1992 [doi>10.1016/0004-3702(92)90003-G]
• 20: MINTON, S., JOHNSTON, M. D., PHILIPS, A. B., AND LAIRD, P. 1990. Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In Proceedings of the 8th National Conference on Artificial Intelligence (Boston, Mass.). AAAI Press/The MIT Press, Cambridge, Mass., pp. 17-24.
• 21: MONTANARI, U. 1974. Networks of constraints: Fundamental properties and applications to picture processing. Inform. Sci. 7, 95-132.
• 22: Bernard A. Nadel, Constraint satisfaction algorithms, Computational Intelligence, v.5 n.4, p.188-224, Nov. 1990 [doi>10.1111/j.1467-8640.1989.tb00328.x]
• 23: PROSSER, P. 1993. Hybrid algorithms for the constraint satisfaction problem. Computat. Int. 9, 268-299.
• 24: Raimund Seidel, On the Complexity of Achieving K-Consistency, University of British Columbia, Vancouver, BC, Canada, 1983
• 25: TSANG, E. 1993. Foundations of Constraint Satisfaction. Academic Press, Orlando, Fla.
• 26: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 27: Peter van Beek, On the inherent level of local consistency in constraint networks, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.368-373, October 1994, Seattle, Washington, United States
• 28: VAN BEEK, P., AND DECHTER, R. 1994. Constraint tightness versus global consistency. In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (Bonn, Germany). Morgan Kaufmann, San Mateo, Calif., pp. 572-582.
• 29: Peter van Beek , Rina Dechter, On the minimality and global consistency of row-convex constraint networks, Journal of the ACM (JACM), v.42 n.3, p.543-561, May 1995 [doi>10.1145/210346.210347]
• 30: WILLIAMS, C. P., AND HOGG, f. 1992. Using deep structure to locate hard problems. In Proceedings of the lOth National Conference on Artificial Intelligence (San Jose, Calif.). AAAI Press/The MIT Press, Cambridge, Mass., pp. 472-477.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Relation systems

General Terms:
Algorithms, Theory

Keywords:
constraint networks, constraint satisfaction problems, constraint-based reasoning, local consistency, relations