Introduction to Constraint Satisfaction Problems and Local Search

Constraint Satisfaction Problems Recap

The primary distinction between search problems (state space problems) and Constraint Satisfaction Problems (CSP) is the focus of the solution. In CSP, the path taken to reach the goal is irrelevant; the focus is entirely on the structure of the goal state itself.
A solution in CSP is defined as an assignment of values to every variable in the problem such that all specified constraints are satisfied.
Backtracking is the fundamental algorithm for CSP, functioning essentially as a Depth-First Search (DFS).
Enhancements to the backtracking algorithm include:
- Variable and Value Ordering: Selecting the order in which variables are assigned and values are tested to improve efficiency.
- Failure Detection: Algorithms like Forward Checking and Arc Consistency (specifically the $AC-3$ algorithm) allow for the early detection of conflicts, pruning the search space significantly.

Domain Splitting

Domain splitting is a modification that can be used in conjunction with backtracking and $AC-3$ to improve memory and speed efficiency.
The core idea involves taking a variable with a large domain and splitting that domain into two or more equal sub-domains.
This approach effectively divides a single large search space into smaller subspaces, creating multiple independent CSP instances.
Advantages of Domain Splitting:
- Reduced search complexity within each sub-problem.
- Facilitates parallel solving: If computation can be performed in parallel, the total time required to find a solution is significantly reduced.
- Enables targeted pruning of the search space.
Example of Domain Splitting:
- Consider variables $x$ , $y$ , and $z$ with a constraint involving all three.
- If the domain of $x$ is $\{1, 2, 3, 4, 5, 6\}$ , it can be split into two problems: one where $x \in \{1, 2, 3\}$ and another where $x \in \{4, 5, 6\}$ .
- In the backtracking tree, the first step for one problem would generate three neighbors (where $x = 1, 2, 3$ ) and the other would generate the remaining three. Each sub-problem is then solved separately through the standard backtracking process.

Variable Elimination Algorithm

Variable elimination is a distinct approach from backtracking. It functions by systematically removing variables from the problem and constructing more complex constraints between the remaining variables.
The goal is to reduce the problem until only one variable remains under a complex constraint. Once that variable is solved, the algorithm backtracks to infer the values of all previously eliminated variables.
The Variable Elimination Process:

If only one variable remains, return the intersection of its unary constraints.
Otherwise, select a variable $x$ (potentially chosen randomly).
Join all constraints where variable $x$ appears to form a new intermediate constraint, often referred to as $r_1$ .
Project constraint $r_1$ onto all variables involved except for $x$ . This resulting constraint is referred to as $r_2$ .
Replace all original constraints involving $x$ with the new constraint $r_2$ .
Repeat the process until only one variable is left.

Variable Elimination: Practical Example

Imagine a problem with variables $a, b, c, d, e$ and constraints: $a \neq b$ , $e \neq c$ , $e \neq d$ , and $e - a = \text{odd}$ . Additionally, there is an inequality $c > d$ .
Variable domains are defined (e.g., $c \in \{3, 4\}$ , $d \in \{2, 3\}$ , $e \in \{2, 3, 4\}$ ).
Step-by-Step for Eliminating Variable $c$ :
- Identify constraints involving $c$ : $c > d$ and $c \neq e$ .
- Create tables for these constraints:
- For $c > d$ : Possible pairs $(c, d)$ are $(3, 2), (4, 2), (4, 3)$ .
- For $c \neq e$ : Possible pairs $(c, e)$ are $(3, 2), (3, 4), (4, 2), (4, 3)$ .
- Form the join ( $r_1$ ) involving $c, d, e$ :
- Row 1: $c=3, e=2, d=2$
- Row 2: $c=3, e=4, d=2$
- Row 3: $c=4, e=2, d=2$
- Row 4: $c=4, e=2, d=3$
- Row 5: $c=4, e=3, d=2$
- Row 6: $c=4, e=3, d=3$
- Project to form $r_2$ : Remove variable $c$ and eliminate duplicate rows for variables $d$ and $e$ . This results in a new constraint between $e$ and $d$ to be added to the graph, effectively replacing $c$ .
Once variables are eliminated, the solution is found by solving the final variable and moving backwards through the saved tables to find consistent assignments for eliminated variables.
Variable elimination is capable of finding all possible solutions to a CSP.

Local Search and Optimization Problems

Local search strategies are primarily used for optimization problems, where the goal is to find a configuration that minimizes or maximizes a specific criterion.
In these problems, the path to the goal is irrelevant; only the final state (the optimal configuration) matters.
Unlike exhaustive search, local search does not track all possible states or maintain a frontier of unexpanded nodes. Instead, it only focuses on the current state and its immediate neighbors.
Local search does not guarantee completeness or that the global optimal solution will be found. It is "local" because it does not consider the global problem space.
Advantages: Local search is extremely fast and effective for finding "good enough" solutions where a perfect score or shortest path is not strictly required.

Generic Local Search Framework

The search space consists of all possible configurations of variable assignments.
Generic Local Search Procedure:

Initial State: Start with a random initial assignment of values to all variables. (Contrasts with backtracking, which starts with an empty assignment).
Evaluation: Use an evaluation function or heuristic function to determine how close a state is to being optimal.
Successor Selection: Generate neighbors by slightly changing variable values and select one that improves the evaluation criteria.
Iteration: Continue the loop of updating variables and evaluating neighbors until a stopping criterion is met.
Termination: Return the current assignment.

Stopping Criteria can include:
- Reaching a state where no successor improves the current heuristic value.
- Reaching a maximum allowed number of iterations or time limit (e.g., 5 minutes).
- Reaching a solution that is "good enough" for the specific task.

Iterative Best Improvement (IBI)

IBI is a greedy local search algorithm that evaluates all possible neighbors and selects the one that provides the maximum improvement to the evaluation function.
Converting CSP to Optimization: A CSP can be treated as an optimization problem by defining the heuristic function as the number of violated constraints. The goal is to minimize this number to zero.
Example: The $n$ -queens problem:
- Task: Place $n$ queens on an $n \times n$ board so that no two queens attack each other (horizontally, vertically, or diagonally).
- Initial State: Random placement on the board.
- Heuristic ( $h$ ): Number of conflicts (pairs of queens attacking each other).
- In a specific $4 \times 4$ instance, a random setup may have $h = 5$ .
- Moving one queen at a time, the algorithm checks all rows to find the position that minimizes conflicts. Moving the second queen to the top row might reduce conflicts to $h = 2$ . Moving the third queen might result in $h = 0$ , solving the problem.

Hill Climbing Variations and Issues

Simple Hill Climbing: Unlike IBI, simple hill climbing takes the first neighbor it finds that improves the current state rather than evaluating all neighbors to find the best one.
Common Limitations of Hill Climbing:
- Local Maxima/Minima: The algorithm reaches a point where all neighbors are worse than the current state, even though a global optimum exists elsewhere.
- Shoulders/Plates: Flat areas in the search space where the heuristic remains the same across many states, making it unclear which direction to take.
- Ridges: Situations where the algorithm must temporarily move to a worse state to eventually reach a better one. This is common in complex scheduling tasks.
Statistical Performance on 8-Queens:
- Standard Hill Climbing gets stuck $86\%$ of the time and succeeds only $14\%$ of the time.
- When it succeeds, it averages only $4$ steps.
- When it fails, it averages $3$ steps before stopping.
- Total expected moves with restarts: $3 \times \frac{0.86}{0.14} + 4 \approx 22$ moves.
Hill Climbing with Sideways Moves:
- This variation allows the algorithm to move to a neighbor with the same heuristic value ( $100$ sideways moves allowed).
- This improves the success rate to $94\%$ (stuck only $6\%$ of the time).
- However, it takes more steps: $21$ on average when succeeding and $65$ on average when getting stuck.
- The total expected moves increase to approximately $25$ .

Advanced Local Search Strategies

Breadth-First Search (BFS) for Local Minima: This approach combines hill climbing with BFS. When the algorithm reaches a local minimum where hill climbing fails, it uses BFS to search surrounding states until it finds a neighbor that improves the situation, then reverts to hill climbing.
Taboo Search: This is a modification that prevents the algorithm from cycling through the same states. It maintains a "Taboo List" (similar to a closed list in uninformed search) that records recently visited assignments. The algorithm is forbidden from returning to states on the Taboo List.
Stochastic Search: A variation of hill climbing that incorporates elements of probability and stochasticity to improve the search and help escape local optima.

Questions & Discussion

Question: What if there are multiple solutions?
Answer: Variable elimination will find all solutions.
Question: Can you perform variable elimination with more than two inbound arcs, or do you take the intersection of all of them?
Answer: You can do it with as many arcs as you want. Eliminating a variable with only two arcs keeps the table sizes smaller, helping control complexity. If there are many edges, it becomes more difficult and may require intermediate steps.
Question: In the variable elimination example, in the last table, both variables were equal to 3. Is that a problem?
Answer: No, they are different variables ( $e$ and $d$ ) and they are allowed to have the same value because the edge that says $e \neq d$ has not been processed or removed from the graph yet.
Question: When doing domain splitting, if values are in different orders, should we order them first?
Answer: Technically, you can run domain splitting with various algorithms like backtracking. The specific order of splitting doesn't stop the algorithm; you just run the two resulting sub-problems simultaneously.
Question: In the original graph, why are there only values 1, 2, 3, 4 for the variables?
Answer: The values depend on the specific domains (e.g., $c$ can be 3 or 4, $e$ can be 2, 3, or 4). We look at all possible combinations of values from those domains that satisfy the constraints. Two nodes can have the same value unless a specific constraint (like "not equal") forbids it.
Question: Could students get an extension for the assignments if they have the tutorial next week?
Answer: Requests for extensions must be sent via email to check for logistical issues. If there are no issues, a slight extension may be granted.