Using constraint metaknowledge to reduce arc consistency computation

Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values fur problem variables subject to constraints that specify which combinations of values are consistent. Knowledge about properties of the constraints can permit inferences that reduce the cost of consistency checking, In particular, such inferences can be used to reduce the number of constraint checks required in establishing are consistency, a fundamental constraint-based reasoning technique. A general AC-Inference algorithm schema is presented and various forms Of inference discussed. A specific algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other are consistency algorithms perform. Thr effectiveness of this approach is demonstrated analytically, and experimentally. (C) 1999 Elsevier Science B.V. All rights reserved.