Week 3b - Constraint Satisfaction Problems I
===

{%hackmd theme-dark %}

Outline & Objective
---
- Understand the differences between standard search problems and constraint satisfaction problems
- Able to formulate a constraint satisfaction problem
- Understand the workings behind backtracking search and the various heuristics (not the heuristics mentioned in the previous chapter) used to enhance its efficiency
- Able to use backtracking search to solve a CSP

Standard Search Problem vs CSP
---
### Standard Search Problems
- More interested in the sequence of actions (path) to the goal
- Paths have various costs, depths (no of steps)
- Heuristics give problem-specific guidance

### Constraint Specific Problems
- More interested in the goal itself, not the sequence of actions (path) to reach the goal
- All paths at the same depth (for some formulations)
- CSPs are specialized for this type of task

CSP Formulation
---
- State: Defined by variables X~i~ that takes on values from domain D~i~
- Goal Test: A set of constraints C~i~ specifying allowable combinations of values for subsets of variables
- In contrast to standard search problems, state is a "black box" -- any data structure that supports goal test, evaluation, successor
- Simple example of a formal representation language
- Allows general-purpose algorithms which are more efficient than standard search algorithms

### Formal Problem Formulation
- Finite set of variables $X=\{X_1,X-2,\ldots,X_n\}$
- Non-empty domain D of k possible values for each variable D~i~ where $D_i=\{v_1,\ldots,v_k\}$
- Finite set of constraints $C=\{C_1,C_2,\ldots,C_m\}$, where each constraint C~i~ limits the values that variables can take, e.g. $X_1 \ne X_2$
- In relation to a search problem, we have:
- State is defined by variables X~i~ that takes on values from domain D~i~
- Goal Test is a set of constraints C~i~ specifying allowable combinations of values for subsets of variables

### CSP Assignment Objective
- A complete assignment is where every variable is assigned a value
- A consistent assignment does not violate any constraint
- A CSP solution is a complete and consistent assignment for all variables

### Advantages of CSPs
- Formal representation language that can be used to formalize many problems type
- Represent problem as a CSP and solve with general-purpose solver
- Able to use general-purpose solver, which are generally more efficient than standard search
- Constraints allow us to focus the search to valid branches
- Branches that violate constraints are removed
- Non-trivial to do this for standard search since it needs manual selection of actions.

### Exercise: Map Colouring

Constraint Graph
---

- Similar to search problem, we can represent CSPs using graphs
- Constraint graphs
- Nodes = variables
- Edges = constraints
- Binary CSPs: each constraint related to at most two variables
- General-purpose CSP algorithms use the graph structure to speed up the search (e.g. Tasmania is an independent subproblem)

Varieties of CSPs
---
### Based on Variables
- Discrete variables
- Finite domains: $O(d^n)$ complete assignments for n variables, domain size d.
- e.g. map-colouring, scheduling with time limits
- Infinite domains: Integers, strings, etc.
- e.g. job scheduling (where there is no time limit -> infinite possibilities), variables are start/end days for each job
- Need a constraint language, e.g. $StartJob_1+5 \le StartJob_3$
- Continuous variables
- e.g. start/end times for Hubble Space Telescope observations

### Based on Order
- Unary constraints involve a single variable (e.g. SA ≠ green)
- Binary constraints involve pairs of variables (e.g. SA ≠ WA)
- Higher-order constraints involve 3 or more variables (e.g. cryptarithmetic column constraints)
- Preference (soft constraints) e.g. red is better than green can be represented by a cost for each variable assignment, aka constrained optimization problems (not covered in this course)

### Exercise: Cryptarithmetic

## Solving CSPs
- One idea to solve CSPs as though it were standard search, then we can apply the standard search algorithms. But we need to first formulate this search problem

## CSPs as Standard Search
CSPs can be easily formualted as standard search problems:
- Initial State: Empty assignment {}
- Successor function (actions): Assign a value to an unassigned variable
- Path cost: A constant cost for every step
- Goal test (Implicit): The current assignment is complete and consistent

For CSPs, the sequence of actions or path is not important, only the final goal state. E.g. for map colouring, it does not matter the sequence in which the states are coloured, as long as all states are coloured with no conflicting colours.

Thus, for n variables problem, the solution will appear at depth n. To find the solution, we can use depth-first search. There are potentially $n!d^n$ leaves in the search tree.

Proof of $n!d^n$:

However, $n!d^n$ is a very large search space, how to reduce it? Will be revealed in next lecture!