\documentstyle[fleqn,epsf,aima-slides]{article}
\begin{document}
\begin{huge}
\titleslide{Informed search algorithms}{Chapter 4, Sections 1--2, 4}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Best-first search
\blob A$^*$ search
\blob Heuristics
\blob Hill-climbing
\blob Simulated annealing
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Review: General search}
\input{\file{algorithms}{general-search-algorithm}}
A strategy is defined by picking the {\em order of node expansion}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Best-first search}
Idea: use an {\em evaluation function} for each node\nl
-- estimate of ``desirability''
$\Rightarrow$ Expand most desirable unexpanded node
\u{Implementation}:\\
{\sc QueueingFn} = insert successors in decreasing order of desirability
Special cases:\nl
greedy search\nl
A$^*$ search
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Romania with step costs in km}
\vspace*{0.3in}
\epsfxsize=1.08\textwidth
\fig{\file{figures}{romania2.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search}
Evaluation function $h(n)$ (\u{h}euristic)\nl
= estimate of cost from $n$ to $goal$
E.g., $h_{{\rm SLD}}(n)$ = straight-line distance from $n$ to Bucharest
Greedy search expands the node that {\em appears} to be closest to goal
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\sfile{figures}{greedy-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\sfile{figures}{greedy-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\sfile{figures}{greedy-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\sfile{figures}{greedy-romania4.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of greedy search}
\q{Complete}
\q{Time}
\q{Space}
\q{Optimal}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of greedy search}
\q{Complete} No--can get stuck in loops, e.g.,\nl
Iasi $\rightarrow$ Neamt $\rightarrow$ Iasi $\rightarrow$ Neamt $\rightarrow$\\
Complete in finite space with repeated-state checking
\q{Time} $O(b^m)$, but a good heuristic can give dramatic improvement
\q{Space} $O(b^m)$---keeps all nodes in memory
\q{Optimal} No
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{A$^*$ search}
Idea: avoid expanding paths that are already expensive
Evaluation function $f(n) = g(n) + h(n)$
$g(n)$ = cost so far to reach $n$\\
$h(n)$ = estimated cost to goal from $n$\\
$f(n)$ = estimated total cost of path through $n$ to goal
A$^*$ search uses an {\em admissible} heuristic\\
i.e., $h(n) \leq h^*(n)$ where $h^*(n)$ is the {\em true} cost from $n$.
E.g., $h_{{\rm SLD}}(n)$ never overestimates the actual road distance
\u{Theorem}: A$^*$ search is optimal
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania4.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania5.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{A$^*$ search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-romania6.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Optimality of A$^*$ (standard proof)}
Suppose some suboptimal goal $G_2$ has been generated
and is in the queue. Let $n$ be an unexpanded node
on a shortest path to an optimal goal $G_1$.
\epsfxsize=0.5\textwidth
\fig{\file{figures}{astar-proof.ps}}
\begin{eqnarray*}
f(G_2) & = & g(G_2)\qquad {\rm since\ }h(G_2) = 0 \\
& > & g(G_1)\qquad {\rm since\ }G_2 {\rm\ is\ suboptimal} \\
&\geq& f(n) \qquad {\rm since\ }h {\rm\ is\ admissible}
\end{eqnarray*}
Since $f(G_2) > f(n)$, A$^*$ will never select $G_2$ for expansion
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Optimality of A$^*$ (more useful)}
\u{Lemma}: A$^*$ expands nodes in order of increasing $f$ value
Gradually adds ``$f$-contours'' of nodes (cf. breadth-first adds layers)\\
Contour $i$ has all nodes with $f=f_i$, where $f_i < f_{i+1}$
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\file{figures}{f-circles.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of A$^*$}
\q{Complete} Yes, unless there are infinitely many nodes with $f \leq f(G)$
\q{Time} Exponential in [relative error in $h$ $\times$ length of soln.]
\q{Space} Keeps all nodes in memory
\q{Optimal} Yes---cannot expand $f_{i+1}$ until $f_i$ is finished
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Proof of lemma: Pathmax}
For some admissible heuristics, $f$ may {\em decrease} along a path
E.g., suppose $n'$ is a successor of $n$
\vspace*{0.2in}
\epsfxsize=0.35\textwidth
\fig{\file{figures}{pathmax-example.ps}}
But this throws away information!\\
$f(n)=9 \Rightarrow$ true cost of a path through $n$ is $\geq 9$\\
Hence true cost of a path through $n'$ is $\geq 9$ also
Pathmax modification to A$^*$:\\
Instead of $f(n') = g(n') + h(n')$, use $f(n') = max(g(n') + h(n'), f(n))$
With pathmax, $f$ is always nondecreasing along any path
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Admissible heuristics}
E.g., for the 8-puzzle:
$h_1(n)$ = number of misplaced tiles\\
$h_2(n)$ = total \u{Manhattan} distance\nl
(i.e., no. of squares from desired location of each tile)
\epsfxsize=0.5\textwidth
\fig{\file{figures}{8puzzle.ps}}
\q{$h_1(S)$ =} \\
\q{$h_2(S)$ =}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Admissible heuristics}
E.g., for the 8-puzzle:
$h_1(n)$ = number of misplaced tiles\\
$h_2(n)$ = total \u{Manhattan} distance\nl
(i.e., no. of squares from desired location of each tile)
\epsfxsize=0.5\textwidth
\fig{\file{figures}{8puzzle.ps}}
\q{$h_1(S)$ =} 7\\
\q{$h_2(S)$ =} 2+3+3+2+4+2+0+2 = 18
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Dominance}
If $h_2(n) \geq h_1(n)$ for all $n$ (both admissible)\\
then $h_2$ {\em dominates} $h_1$ and is better for search
Typical search costs:
\begin{tabular}{ll}
$d=14$ & IDS = 3,473,941 nodes \\
& A$^*(h_1)$ = 539 nodes \\
& A$^*(h_2)$ = 113 nodes \\
$d=14$ & IDS = too many nodes \\
& A$^*(h_1)$ = 39,135 nodes \\
& A$^*(h_2)$ = 1,641 nodes
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Relaxed problems}
Admissible heuristics can be derived from the {\em exact}\\
solution cost of a {\em relaxed} version of the problem
If the rules of the 8-puzzle are relaxed so that a tile can move
{\em anywhere}, then $h_1(n)$ gives the shortest solution
If the rules are relaxed so that a tile can move to {\em any adjacent
square}, then $h_2(n)$ gives the shortest solution
For TSP: let path be {\em any} structure that connects all cities\nl
$\Longrightarrow$ minimum spanning tree heuristic
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative improvement algorithms}
In many optimization problems, {\em path} is irrelevant;\\
the goal state itself is the solution
Then state space = set of ``complete'' configurations;\nl
find {\em optimal} configuration, e.g., TSP\nl
or, find configuration satisfying constraints, e.g., n-queens
In such cases, can use {\em iterative improvement} algorithms;\\
keep a single ``current'' state, try to improve it
Constant space, suitable for online as well as offline search
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Travelling Salesperson Problem}
Find the shortest tour that visits each city exactly once
\vspace*{0.3in}
\epsfxsize=0.7\textwidth
\fig{\file{figures}{tsp-sequence.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: $n$-queens}
Put $n$ queens on an $n \times n$ board with no two queens
on the same\\
row, column, or diagonal
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\file{figures}{4queens-sequence.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Hill-climbing (or gradient ascent/descent)}
``Like climbing Everest in thick fog with amnesia''
\input{\file{algorithms}{hill-climbing-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Hill-climbing contd.}
Problem: depending on initial state, can get stuck on local maxima
\vspace*{0.3in}
\epsfxsize=0.8\textwidth
\fig{\file{figures}{hill-climbing-maxima.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Simulated annealing}
Idea: escape local maxima by allowing some ``bad'' moves\\
{\em but gradually decrease their size and frequency}
\input{\file{algorithms}{simulated-annealing-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of simulated annealing}
At fixed ``temperature'' $T$, state occupation probability reaches\\
Boltzman distribution
\[
p(x) = \alpha e^{\frac{E(x)}{kT}}
\]
$T$ decreased slowly enough $\Longrightarrow$ always reach best state
\q{Is this necessarily an interesting guarantee}
Devised by Metropolis et al., 1953, for physical process modelling
Widely used in VLSI layout, airline scheduling, etc.
\end{huge}
\end{document}