\documentclass{article}
\usepackage{fleqn}
\usepackage{epsf}
\usepackage[dvips]{color}
\usepackage{aima2e-slides}
\def\Astar{A$^*$}
\begin{document}
\begin{huge}
\titleslide{Informed search algorithms}{Chapter 4, Sections 1--2}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Best-first search
\blob {\Astar} search
\blob Heuristics
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Review: Tree search}
\input{\file{algorithms}{tree-search-short-algorithm}}
A strategy is defined by picking the \emph{order of node expansion}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Best-first search}
\note{Idea}: use an \defn{evaluation function} for each node\nl
-- estimate of ``desirability''
$\Rightarrow$ Expand most desirable unexpanded node
\note{Implementation}:\\
\v{fringe} is a queue sorted in decreasing order of desirability
Special cases:\nl
greedy search\nl
{\Astar} 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 \mat{$h(n)$} (\emph{h}euristic)\nl
= estimate of cost from \mat{$n$} to the closest goal
E.g., \mat{$h_{{\rm SLD}}(n)$} = straight-line distance from \mat{$n$} to Bucharest
Greedy search expands the node that \emph{appears} to be closest to goal
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{greedy-progress01.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{greedy-progress02.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{greedy-progress03.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Greedy search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{greedy-progress04.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of greedy search}
\q{Complete}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of greedy search}
\q{Complete} No--can get stuck in loops, e.g., with Oradea as goal,\nl
Iasi $\rightarrow$ Neamt $\rightarrow$ Iasi $\rightarrow$ Neamt $\rightarrow$\\
Complete in finite space with repeated-state checking
\q{Time}
%%%%%%%%%%%% 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} \mat{$O(b^m)$}, but a good heuristic can give dramatic improvement
\q{Space}
%%%%%%%%%%%% 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} \mat{$O(b^m)$}, but a good heuristic can give dramatic improvement
\q{Space} \mat{$O(b^m)$}---keeps all nodes in memory
\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} \mat{$O(b^m)$}, but a good heuristic can give dramatic improvement
\q{Space} \mat{$O(b^m)$}---keeps all nodes in memory
\q{Optimal} No
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search}
\note{Idea}: avoid expanding paths that are already expensive
Evaluation function \mat{$f(n) = g(n) + h(n)$}
\mat{$g(n)$} = cost so far to reach \mat{$n$}\\
\mat{$h(n)$} = estimated cost to goal from \mat{$n$}\\
\mat{$f(n)$} = estimated total cost of path through \mat{$n$} to goal
{\Astar} search uses an \defn{admissible} heuristic\\
i.e., \mat{$h(n) \leq h^*(n)$} where \mat{$h^*(n)$} is the \emph{true} cost from \mat{$n$}.\\
(Also require \mat{$h(n)\geq 0$}, so \mat{$h(G)=0$} for any goal \mat{$G$}.)
E.g., \mat{$h_{{\rm SLD}}(n)$} never overestimates the actual road distance
\note{Theorem}: {\Astar} search is optimal
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress01.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress02.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress03.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress04.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress05.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{{\Astar} search example}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{astar-progress06.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Optimality of {\Astar} (standard proof)}
Suppose some suboptimal goal \mat{$G_2$} has been generated
and is in the queue. Let \mat{$n$} be an unexpanded node
on a shortest path to an optimal goal \mat{$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 \mat{$f(G_2) > f(n)$}, {\Astar} will never select \mat{$G_2$} for expansion
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Optimality of {\Astar} (more useful)}
\note{Lemma}: {\Astar} expands nodes in order of increasing \mat{$f$} value$^*$
Gradually adds ``\mat{$f$}-contours'' of nodes (cf. breadth-first adds layers)\\
Contour \mat{$i$} has all nodes with \mat{$f=f_i$}, where \mat{$f_i < f_{i+1}$}
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\file{figures}{f-circles.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of {\Astar}}
\q{Complete}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of {\Astar}}
\q{Complete} Yes, unless there are infinitely many nodes with \mat{$f \leq f(G)$}
\q{Time}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of {\Astar}}
\q{Complete} Yes, unless there are infinitely many nodes with \mat{$f \leq f(G)$}
\q{Time} Exponential in [relative error in \mat{$h$} $\times$ length of soln.]
\q{Space}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of {\Astar}}
\q{Complete} Yes, unless there are infinitely many nodes with \mat{$f \leq f(G)$}
\q{Time} Exponential in [relative error in \mat{$h$} $\times$ length of soln.]
\q{Space} Keeps all nodes in memory
\q{Optimal}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of {\Astar}}
\q{Complete} Yes, unless there are infinitely many nodes with \mat{$f \leq f(G)$}
\q{Time} Exponential in [relative error in \mat{$h$} $\times$ length of soln.]
\q{Space} Keeps all nodes in memory
\q{Optimal} Yes---cannot expand \mat{$f_{i+1}$} until \mat{$f_i$} is finished
{\Astar} expands all nodes with \mat{$f(n) < C^*$}\\
{\Astar} expands some nodes with \mat{$f(n) = C^*$}\\
{\Astar} expands no nodes with \mat{$f(n) > C^*$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Proof of lemma: Consistency}
A heuristic is \defn{consistent} if \hfill\raisebox{-0.35\textwidth}[0pt][0pt]{\epsfxsize=0.3\textwidth\epsffile{\file{figures}{consistency.ps}}}
\[
h(n) \leq c(n,a,n') + h(n')
\]
If \mat{$h$} is consistent, we have\
\mat{\begin{eqnarray*}
f(n') &=& g(n') + h(n') \\
&=& g(n) + c(n,a,n') + h(n') \\
&\geq& g(n) + h(n) \\
&=& f(n)
\end{eqnarray*}}
I.e., \mat{$f(n)$} is nondecreasing along any path.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Admissible heuristics}
E.g., for the 8-puzzle:
\mat{$h_1(n)$} = number of misplaced tiles\\
\mat{$h_2(n)$} = total \defn{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:
\mat{$h_1(n)$} = number of misplaced tiles\\
\mat{$h_2(n)$} = total \defn{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)$ =} 6\\
\q{$h_2(S)$ =} 4+0+3+3+1+0+2+1 = {14}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Dominance}
If \mat{$h_2(n) \geq h_1(n)$} for all \mat{$n$} (both admissible)\\
then \mat{$h_2$} \defn{dominates} \mat{$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=24$ & IDS $\approx$ 54,000,000,000 nodes \\
& A$^*(h_1)$ = 39,135 nodes \\
& A$^*(h_2)$ = 1,641 nodes
\end{tabular}
Given any admissible heuristics \mat{$h_a$}, \mat{$h_b$},
\mat{\[
h(n) = \max(h_a(n),h_b(n))
\]}
is also admissible and dominates \mat{$h_a$}, \mat{$h_b$}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Relaxed problems}
Admissible heuristics can be derived from the \emph{exact}\\
solution cost of a \emph{relaxed} version of the problem
If the rules of the 8-puzzle are relaxed so that a tile can move
\emph{anywhere}, then \mat{$h_1(n)$} gives the shortest solution
If the rules are relaxed so that a tile can move to \emph{any adjacent
square}, then \mat{$h_2(n)$} gives the shortest solution
Key point: the optimal solution cost of a relaxed problem \\
is no greater than the optimal solution cost of the real problem
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Relaxed problems contd.}
Well-known example: \defn{travelling salesperson problem} (TSP)\\
Find the shortest tour visiting all cities exactly once
\vspace*{0.3in}
\epsfxsize=0.75\textwidth
\fig{\file{figures}{tsp-mst.ps}}
\defn{Minimum spanning tree} can be computed in \mat{$O(n^2)$}\\
and is a lower bound on the shortest (open) tour
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Summary}
Heuristic functions estimate costs of shortest paths
Good heuristics can dramatically reduce search cost
Greedy best-first search expands lowest \mat{$h$}\al
-- incomplete and not always optimal
{\Astar} search expands lowest \mat{$g+h$}\al
-- complete and optimal\al
-- also optimally efficient (up to tie-breaks, for forward search)
Admissible heuristics can be derived from exact solution of relaxed problems
\end{huge}
\end{document}