Using metalevel constraint knowledge to reduce constraint checking

Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values for 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. Specifically, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a flmdamental constraint-based reasoning technique. A general AC-lnference schema is presented and various forms of inference discussed. Some of these apply only to special classes of contraints. However, a specific new algorithm, AC-7, is developed that takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform.