CS & AI Student | Aspiring Software Developer | Passion for ML and Wolfram
A Constraint Satisfaction Problem (CSP) is a search problem defined by:
In this lesson, we will look at four CSP algorithms/techniques:
In the context of CSPs, a solution is a full mapping from variables to values that satisfies all constraints. Building on this, if we were to gradually start assigning values to variables, we can treat any partial mapping of the variables as a state on the way to our possible solution. Hence, using this idea of gradually filling in the values of the variables, we can construct a graph of all possible states (some of which are solutions), known as a constraint graph. Consequently, we can use this approach to treat any CSP as a search problem. Of course, you might start to see the problem that, in the general case, the constraint graph is exponential in size. This is because the number of possible mappings is exponential in the number of variables. Therefore, if we are to reason about CSPs in this way, we need search algorithms that traverse the constraint graph efficiently and prune (remove wastful parts of the search tree) effectively.
Backtracking Search is a classic and simple approach to this search problem; it is essentially just a depth-first search on a constraint graph. When in a state, it traverse into the next deepest state (conceptually, it fills in as many variables as it can) until it either finds a solution or not (if the constraints do not allow there to be a solution). If no solution is found down a certain branch, it backtracks up to the last valid state and searches a different path. Like depth-first search, it is guaranteed to find a solution if one exists, but is not guaranteed to find the best one.
With MRV, we prioritize and fill in variables that are harder to assign and need to be assigned first. With LCV, we prioritize and assign the values that make it as easy to fill in the other variables. These heuristics make it less likely for the Backtracking Search to run into dead ends, speeding up the search in general.
An example of a possible improvement on Backtracking Search is Forward Checking. This is where, after searching a state, the algorithm looks ahead to eliminate any variables that are impossible to fill in. For example, if a variable has only one possible value, it is impossible to fill in any other value for that variable. Therefore, we can remove that variable from the search space and speed up the search. This is a useful extention of Backtracking Search as it indentifies dead ends early and reduce wasted search effort. Hence, forward checking is especially useful on problems with constraint graphs with a large depth factor (and therefore, many variables).
An even stronger improvement, is Maintaining Arc Consistency (MAC). In each assignment, MAC enforces "arc consistency" (ensures that all values are consistent with constraints) across all constraints: every value in a variable’s domain must have a consistent supporting value in connected variables. If any variable’s domain is emptied, the algorithm backtracks immediately. MAC prunes even more rigorously that Forward Checking, again making it favourable for deep constraint graphs with many variables. However, as is common with more rigorous algorithms, it is also more computationally expensive. As always, there is a trade-off between rigour and speed.
The Min-Conflicts algorithm is unique on this list as it is the only one that does not use a constraint graph approach. It is instead a local search algorithm that uses Boolean logic to iteratively remove conflicts between variables. At each stage of the algorithm, it picks the variable whose value is involved in the most conflicts and swaps its value in such a way that minimizes the total number of conflicts. These steps are repeated until the solution is found and there are no conflicts left.
With this section on CSPs, we are approaching something which we might start to consider intelligent behaviour. One can say that all of the algorithms and techniques shown in this section were merely search algorithms and thus involve no intelligent behaviour. However, even if no intelligent or conscious behaviour is involved, we cannot argue that the results are not intelligent. The CSP framework allows to represent very complex problems, everything from Sudoku to complex resource allocation. Hence, I see this as the start of the border between regular computer science and the study of artificial intelligence, as this way of thinking can lead us to intelligent results, even the algorithms cannot reason like you and I.