\documentstyle[fleqn,epsf,aima-slides]{article}
\begin{document}
\begin{huge}
\titleslide{Constraint Satisfaction Problems}{Chapter 3, Section 7 and Chapter 4, Section 4.4}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob CSP examples
\blob General search applied to CSPs
\blob Backtracking
\blob Forward checking
\blob Heuristics for CSPs
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Constraint satisfaction problems (CSPs)}
Standard search problem:\al
\u{state} is a ``black box''---any old data structure\nl
that supports goal test, eval, successor
CSP:\al
\u{state} is defined by {\em variables} $V_i$
with {\em values} from {\em domain} $D_i$\al
\ \al
\u{goal test} is a set of {\em constraints} specifying\nl
allowable combinations of values for subsets of variables
Simple example of a {\em formal representation language}
Allows useful {\em general-purpose} algorithms with more power\\
than standard search algorithms
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: 4-Queens as a CSP}
Assume one queen in each column. Which row does each one go in?
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.6\textwidth}
\u{Variables} $Q_1$, $Q_2$, $Q_3$, $Q_4$ \\
\u{Domains} $D_i = \{1,2,3,4\}$\\
\u{Constraints}\al
$Q_i \neq Q_j$ (cannot be in same row)\al
$|Q_i - Q_j| \neq |i-j|$ (or same diagonal)
\end{minipage}}
&
\epsfxsize=2.3in
\epsffile{\file{figures}{4queens.ps}}
\end{tabular}
Translate each constraint into set of allowable values for its variables
E.g., values for $(Q_1,Q_2)$ are
$(1,3)\ (1,4)\ (2,4)\ (3,1)\ (4,1)\ (4,2)$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Constraint graph}
{\em Binary CSP}: each constraint relates at most two variables
{\em Constraint graph}: nodes are variables, arcs show constraints
\vspace*{0.3in}
\epsfxsize=0.3\textwidth
\centerline{\epsffile{\file{figures}{4queens-graph.ps}}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Cryptarithmetic}
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
\u{Variables}\al
$D\ E\ M\ N\ O\ R\ S\ Y$
\u{Domains}\al
$\{0,1,2,3,4,5,6,7,8,9\}$
\end{minipage}}
&
\hbox{\begin{minipage}{0.3\textwidth}
\begin{tabular}{ccccc}
&S&E&N&D\\
+&M&O&R&E\\
\hline
M&O&N&E&Y
\end{tabular}
\end{minipage}}
\end{tabular}
\u{Constraints}\al
$M\neq 0$, $S\neq 0$ ({\em unary} constraints)\al
$Y = D+E$ or $Y=D+E-10$, etc.\al
$D\neq E$, $D\neq M$, $D\neq N$, etc.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Map coloring}
Color a map so that no adjacant countries have the same color
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.6\textwidth}
\u{Variables}\al
Countries $C_i$
\u{Domains}\al
$\{Red,Blue,Green\}$
\u{Constraints}\al
$C_1 \neq C_2$, $C_1 \neq C_5$, etc.
\end{minipage}}
&
\epsfxsize=2.7in
\epsffile{\file{figures}{map-coloring.ps}}
\end{tabular}
\vspace*{0.2in}
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
Constraint graph:
\end{minipage}}
&
\epsfxsize=2.5in
\raisebox{-2.5in}[0pt][0pt]{\epsffile{\file{figures}{map-coloring-graph.ps}}}
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Real-world CSPs}
Assignment problems\al
e.g., who teaches what class
Timetabling problems\al
e.g., which class is offered when and where?
Hardware configuration
Spreadsheets
Transportation scheduling
Factory scheduling
Floorplanning
\vspace*{0.3in}
Notice that many real-world problems involve real-valued variables
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Applying standard search}
Let's start with the straightforward, dumb approach, then fix it
States are defined by the values assigned so far
\u{Initial state}: all variables unassigned
\u{Operators}: assign a value to an unassigned variable
\u{Goal test}: all variables assigned, no constraints violated
\vspace*{0.3in}
Notice that this is the same for all CSPs!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Implementation}
CSP state keeps track of which variables have values so far\\
Each variable has a domain and a current value
\input{\file{algorithms}{csp-datatypes-algorithm}}
Constraints can be represented\al
\u{explicitly} as sets of allowable values, or\al
\u{implicitly} by a function that tests for satisfaction of the constraint
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Standard search applied to map-coloring}
\vspace*{0.5in}
\epsfxsize=1.0\textwidth
\fig{\file{figures}{map-coloring-tree.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Complexity of the dumb approach}
\q{Max. depth of space $m = {}$}
\q{Depth of solution state $d = {}$}
\q{Search algorithm to use}
\q{Branching factor $b = {}$}
This can be improved dramatically by noting the following:
1) Order of assignment is irrelevant, hence many paths are equivalent\\
2) Adding assignments cannot correct a violated constraint
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Complexity of the dumb approach}
\q{Max. depth of space $m = {}$} $n$ (number of variables)
\q{Depth of solution state $d = {}$} $n$ (all vars assigned)
\q{Search algorithm to use} depth-first
\q{Branching factor $b = {}$} $\mysum_i |D_i|$ (at top of tree)
This can be improved dramatically by noting the following:
1) Order of assignment is irrelevant so many paths are equivalent\\
2) Adding assignments cannot correct a violated constraint
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Backtracking search}
Use depth-first search, but\al
1) fix the order of assignment, ${} \implies b = |D_i|$\nl
(can be done in the {\sc Successors} function)\al
2) check for constraint violations
The constraint violation check can be implemented in two ways:\al
1) modify {\sc Successors} to assign only values that\nl
are allowed, given the values already assigned\al
or 2) check constraints are satisfied before expanding a state
Backtracking search is the basic uninformed algorithm for CSPs
Can solve $n$-queens for $n \approx 15$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Forward checking}
\u{Idea}: Keep track of remaining legal values for unassigned variables\\
\phantom{\u{Idea}: }Terminate search when any variable has no legal values
Simplified map-coloring example:
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
\begin{tabular}{|l|c|c|c|}
\hline
& {\sc red} & {\sc blue} & {\sc green} \\
\hline
$C_1$ & & & \\
\hline
$C_2$ & & & \\
\hline
$C_3$ & & & \\
\hline
$C_4$ & & & \\
\hline
$C_5$ & & & \\
\hline
\end{tabular}
\end{minipage}}
&
\epsfxsize=2.7in
\raisebox{-1in}[0pt][0pt]{\epsffile{\file{figures}{map-coloring2.ps}}}
\end{tabular}
Can solve $n$-queens up to $n \approx 30$
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
.\\
.
.
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
\begin{tabular}{|l|c|c|c|}
\hline
& \phantom{{\sc red}} & \phantom{{\sc blue}} & \phantom{{\sc green}} \\
\hline
\phantom{$C_1$} & \tick & & \\
\hline
\phantom{$C_2$} & \cross & & \\
\hline
\phantom{$C_3$} & & & \\
\hline
\phantom{$C_4$} & \cross & & \\
\hline
\phantom{$C_5$} & \cross & & \\
\hline
\end{tabular}
\end{minipage}}
&
\end{tabular}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
.\\
.
.
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
\begin{tabular}{|l|c|c|c|}
\hline
& \phantom{{\sc red}} & \phantom{{\sc blue}} & \phantom{{\sc green}} \\
\hline
\phantom{$C_1$} & & & \\
\hline
\phantom{$C_2$} & & \tick & \\
\hline
\phantom{$C_3$} & & \cross & \\
\hline
\phantom{$C_4$} & & \cross & \\
\hline
\phantom{$C_5$} & & \cross & \\
\hline
\end{tabular}
\end{minipage}}
&
\end{tabular}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{}
.\\
.
.
\begin{tabular}{lr}
\hbox{\begin{minipage}{0.6\textwidth}
\begin{tabular}{|l|c|c|c|}
\hline
& \phantom{{\sc red}} & \phantom{{\sc blue}} & \phantom{{\sc green}} \\
\hline
\phantom{$C_1$} & & & \\
\hline
\phantom{$C_2$} & & & \\
\hline
\phantom{$C_3$} & & & \tick \\
\hline
\phantom{$C_4$} & & & \\
\hline
\phantom{$C_5$} & & & \cross \\
\hline
\end{tabular}
\end{minipage}}
&
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Heuristics for CSPs}
More intelligent decisions on\al
which value to choose for each variable\al
which variable to assign next
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.7\textwidth}
\q{Given $C_1 \eq Red$, $C_2 \eq Green$, choose $C_3 \eq$}\al
.
\q{Given $C_1 \eq Red$, $C_2 \eq Green$, what next}\al
.
\end{minipage}}
&
\epsfxsize=2.7in
\epsffile{\file{figures}{map-coloring.ps}}
\end{tabular}
Can solve $n$-queens for $n \approx 1000$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Heuristics for CSPs}
More intelligent decisions on\al
which value to choose for each variable\al
which variable to assign next
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.7\textwidth}
\q{Given $C_1 \eq Red$, $C_2 \eq Green$, choose $C_3 \eq$}\al
$C_3 \eq Green$: {\em least-constraining-value}
\q{Given $C_1 \eq Red$, $C_2 \eq Green$, what next}\al
$C_5$: {\em most-constrained-variable}
\end{minipage}}
&
\epsfxsize=2.7in
\epsffile{\file{figures}{map-coloring.ps}}
\end{tabular}
Can solve $n$-queens for $n \approx 1000$
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative algorithms for CSPs}
Hill-climbing, simulated annealing typically work with\\
``complete'' states, i.e., all variables assigned
To apply to CSPs:\al
allow states with unsatisfied constraints\al
operators {\em reassign} variable values
Variable selection: randomly select any conflicted variable
\u{{\em min-conflicts}} heuristic:\al
choose value that violates the fewest constraints\al
i.e., hillclimb with $h(n)$ = total number of violated constraints
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: 4-Queens}
\u{States}: 4 queens in 4 columns ($4^4 = 256$ states)
\u{Operators}: move queen in column
\u{Goal test}: no attacks
\u{Evaluation}: $h(n)$ = number of attacks
\vspace*{0.3in}
\epsfxsize=0.7\textwidth
\epsffile{\file{figures}{4queens-iterative.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Performance of min-conflicts}
Given random initial state, can solve $n$-queens in almost constant time for
arbitrary $n$ with high probability (e.g., $n$ = 10,000,000)
The same appears to be true for any randomly-generated CSP\\
\u{except} in a narrow range of the ratio
\[
R = \frac{\mbox{number of constraints}}{\mbox{number of variables}}
\]
\vspace*{0.2in}
\epsfxsize=0.6\textwidth
\fig{\file{figures}{random-csp-runtime.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Tree-structured CSPs}
%%%%% Note: this material does not appear AIMA/1e
\vspace*{0.3in}
\epsfxsize=0.5\textwidth
\centerline{\epsffile{\file{figures}{abcdef-graph.ps}}}
\u{Theorem}: if the constraint graph has no loops, the CSP can be solved in
$O(n|D|^2)$ time
Compare to general CSPs, where worst-case time is $O(|D|^n)$
This property also applies to logical and probabilistic reasoning:\\
an important example of the relation between
syntactic restrictions and complexity of reasoning.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Algorithm for tree-structured CSPs}
Basic step is called {\em filtering}:
${\sc Filter}(V_i,\, V_j)$\al
removes values of $V_i$ that are inconsistent with ALL values of $V_j$
Filtering example:
\vspace*{0.3in}
\epsfxsize=0.65\textwidth
\epsffile{\file{figures}{csp-filter.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Algorithm contd.}
\vspace*{0.3in}
\epsfxsize=0.5\textwidth
\centerline{\epsffile{\file{figures}{abcdef-graph.ps}}}
1) Order nodes breadth-first starting from any leaf:
\epsfxsize=0.7\textwidth
\centerline{\epsffile{\file{figures}{abcdef-ordered.ps}}}
2) For $j = n$ to $1$, apply ${\sc Filter}(V_i,\, V_j)$
where $V_i$ is a parent of $V_j$
3) For $j = 1$ to $n$, pick legal value for $V_j$ given parent value
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Summary}
CSPs are a special kind of problem:\al
states defined by values of a fixed set of variables\al
goal test defined by {\em constraints} on variable values
Backtracking = depth-first search with\al
1) fixed variable order\al
2) only legal successors
Forward checking prevents assignments that guarantee later failure
Variable ordering and value selection heuristics help significantly
Iterative min-conflicts is \u{usually} effective in practice
Tree-structured CSPs can \u{always} be solved very efficiently
\end{huge}
\end{document}