Constraint Satisfaction Problems (AI)

A Constraint Satisfaction Problem is defined by:

(1)
\begin{align} \text{A set of variables } X_i \text{, each with a domain } D_i \text{ of possible values, and a set of constraints } C. \end{align}
Solution
assignment of the variables from the domains such that none of the constraints are violated.

Examples

Map Colouring

  • $X_i$ = WA, NT, QLD, NSW, VIC, SA, TAS, ACT
  • $D_i$ = red, green, blue
  • $C$ = Adjacent regions must have different colours.

N-Queens

  • $X_i$ = Q1, Q2, … Qn
  • $D_i$ = Each grid reference on the chessboard
  • $C$ = No queen can have the same j (row), k (col) or j-k (diagonal)

Real World

Timetabling and other administration problems are all CSPS, where the domain is the available times, the constraints are clashes and the variables are the busses or classes or etc.

Types of Constraints

  • Unary
    • Involving a single variable.
    • e.g. $N \neq 0$
  • Binary
    • Involving pairs of variables
    • e.g. $SA \neq WA$
  • Higher Order
    • Involving 3+ variables
    • e.g.$Y = D + E$
  • Inequality Constraints on Continuous Variables
    • e.g. $Job_1 + 5 \leq Job_2$
  • Soft Constraints
    • Preferences
    • e.g. 11am lecture is better than 8am lecture

Standard Search Formula

The most basic, works-for-all-problems search is a DFS. When this is performed with one changing variable we refer to it as backtracking.

(As in, each time we expand out a state we've just assigned one extra variable).

Commutativity

Variable assignments are commutative. i.e. if WA = red implies that NT = green, then NT = green implies that WA = red.

Improvements to Backtracking

We can greatly improve this basic search in a couple of easy ways:

  1. What variable should be assigned next?
    • The one with the Fewest Legal Values (i.e. the most constraints on it)
    • e.g. Minimum Remaining Values (MRV)
  2. What order should values be tried?
    • The order that puts the least constraints on other values
    • e.g. Least Constraining Value (LCV)
  3. Can we detect failure early?
    • Forward Checking.

Forward Checking

If we keep track of remaining legal values for unassigned variables we can look forward to see if our solution will become unsolveable. It propagates information from assigned variables to unassigned variables, however it doesn't provide early detection for all failures.

Example

For instance if we colour WA Red, then NT and SA have one less valid value. Colouring NT blue hence reduces SA to being green, and forces QLD to be red or green.

Implementation Tricks

Store the depth at which something becomes impossible in an array, rather than keeping a 2d array of possibilities.

Constraint Propagation and Arc Consistency

Constraint propagation repeatedly enforces constraints locally. The simplest method of constraint propagation is called Arc Consistency.

Arc Consistency makes each 'Arc' consistent. i.e.

(2)
\begin{align} \forall x \in X, x \rightarrow y \text { is consistent if there is some allowed y } \end{align}

e.g. NSW = red is okay if that doesn't mean SA has no possible values.

This is an alternative to backtracking, a different kind of algorithm. We pick 2nd most constrained -> first most constrained, see if the situation is stil valid, mark down what we know, and repeat.

This can sometimes speed backtracking up enormously. E.g. if there are lots of variables then backtracking takes ages, but this targets potential problems and provides a level of parallelism.

Local Search (or Iterative Improvement)

These type of algorithms automatically assign all variables to a random domain initially, and then adjust one variable per expansion to reduce the number of constraint violations.

Hill Climbing by Min-Conflicts

Hill Climbing by Min-Conflicts takes any conflicted variable and adjusts it. It choose its new value as the one that violates the fewest constraints.

Phase-Transition in CSPs

Randomly generated CSPs tend to be easy if there are either very few (lots of freedom, many solutions) or very many (no freedom, know exactly when we find a solution) constraints. There's a small spike where they become very hard in a narrow range of the ratio:

(3)
\begin{align} \frac {number of constraints}{number of variables} \end{align}

Flat Regions and Local Optima

Sometimes we have to go sideways/backwards (i.e. to an equally bad or worse state) in order to improve overall.

Example

Like when solving a Rubik's Cube, sometimes you have to appear to mess the cube up in order to complete the solution.

Simulated Annealing

Simulated Annealing gets its name from the magnetising of iron (slowly cooling it down to allow for adjusting the spin of each atom to create the desired affect).

It's essentially stochastic hill climbing based on the differences between the current state (h0) and the new state (h1).

  • If h1 < h0 then we switch to the new state (as it has less constraints).
  • Else we make the change with the following probability:
(4)
\begin{align} e^{\frac{-(h_1 - h_0)}{T}} \end{align}

where T is 'temperature' (an adjustable parameter).

Ordinary hill climbing happens with T = 0. A totally random search happens as T approaches infinity.

If T is fixed we call this 'metropolis', the whole point of the annealing is to gradually decrease T during the search (slowly cooling it).

Simulated Annealing can help to escape from local optima (forcing us into the non-intuitive worse state necessary to improve).