About Look-Ahead Algorithms in Constraint Satisfaction Problems

Many problems in Artificial Intelligence can be solved using the Constraint Satisfaction Problems (CSPs) techniques. CSPs are, generally, solved using backtrack based algorithms. A large variety of algorithms has been proposed to deal with CSPs. In this paper, we focus on the look-ahead algorithms in CSPs (namely the most popular ones: Forward-Checking and Maintaining Arc-Consistency), and we propose a generic approach which maintains a restricted form of arc-consistency during the search process. We also give a way to exploit another form of local consistency: the Directed Path-Consistency.