Using inference to reduce arc consistency computation

TLDR

Constraint satisfaction problems are widely used in artificial intelligence, involving assigning values to variables under constraints; knowledge of constraint properties can reduce consistency‑checking cost, especially by cutting the number of checks needed for arc consistency. The paper proposes a general AC‑Inference schema and discusses various inference forms. The authors introduce AC‑7, an algorithm exploiting a common binary‑constraint property to eliminate unnecessary checks in arc consistency. Analytical and experimental results on real‑world problems confirm the effectiveness of the approach.

Abstract

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. 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 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 arc consistency algorithms perform. The effectiveness of this approach is demonstrated analytically, and experimentally on real-world problems.