Minimal Forward Checking--a Lazy Constraint Satisfaction Search Algorithm: Experimental And Theoretical Results

Many problems that occur in Artificial Intelligence and Operations Research can be naturally represented as Constraint Satisfaction Problems (CSPs). One of the most popular backtracking search algorithms used to solve CSPs is called Forward Checking (FC). FC performs a limited amount of lookahead during its search attempting to detect future inconsistencies thereby avoiding inconsistent parts of the search tree. In this thesis we describe a new backtracking search algorithm called Minimal Forward Checking (MFC) which maintains FC\u27s ability to detect inconsistencies but which is lazy in is method of doing so. We prove that MFC is sound and complete. We also prove the MFC and FC visit the same nodes in the search tree. Most significantly, we prove that MFC\u27s worst case performance in terms of number of constraint checks performed (the common measure of performance of these algorithms) is the number of constraint checks performed by FC. We then describe how the MFC algorithm can be seen as one algorithm in a family of lazy CSP search algorithms.;As theoretical results on the average case complexity for CSP search algorithms are extremely difficult to derive, empirical comparisons need to be performed. A commonly used testbed is randomly generated problems drawn from a standard model of binary CSPs at a specific location known to contain problems that are relatively hard to solve. We generalize the standard model of binary CSPs and show how to find problems in this model that are relatively hard to solve. We also show that these hard problems are of similar hardness or harder than hard problems drawn from the standard model especially as the problem size grows and the problem has a relatively sparse structure. We perform large empirical studies of many CSP search algorithms including variants of MFC and FC with non-chronological backtracking and variants of the Fail First heuristic on two testbeds of hard random problems, each drawn from one of the two models. Our empirical comparisons on both testbeds indicate that the average case performance of algorithms based on MFC are better than all the other algorithms in the comparison in terms of the number of constraint checks performed