|
Abstract : |
Constraint satisfaction problems are widely used in articial intelligence. They involve nding 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. In particular, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a fundamental constraint-based reasoning technique. A general AC-Inference algorithm schema is presented and various forms of inference discussed. A specic algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform. The eoeectiveness of this approach is demonstrated analytically, and experimentally. 1, |
