A Generic Customizable Framework for Inverse Local Consistency

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Constraint Satisfaction Problems

Local consistency enforcing is at the core of CSP (Constraint Satisfaction Problem) solving. Although arc consistency is still the most widely used level of local consistency, researchers are going on investigating more powerful levels, such as path consistency, k-consistency, (i,j)-consistency. Recently, more attention has been turned to inverse local consistency levels, such as path inverse consistency, k-inverse consistency, neighborhood inverse consistency, that do not suffer from the drawbacks of the other local consistency levels (changes in the constraint definitions and in the constraint graph, prohibitive memory requirements). In this paper, we propose a generic framework for inverse local consistency that includes most of the previously defined levels and allows a rich set of new levels to be defined. The first benefit of such a generic framework is to allow a user to define and test many different inverse local consistency levels, in accordance with the problem or even the instance he has to solve. The second benefit is to allow a generic algorithm to be defined. This algorithm, that is parameterized by the chosen inverse local consistency level, generalizes the AC7 algorithm used for arc consistency, and produces from any instance its locally consistent closure at the chosen level.