\documentstyle[fleqn,epsf,aima-slides]{article}
\begin{document}
\begin{huge}
\titleslide{Problem solving and search}{Chapter 3, Sections 1--5}
\sf
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Outline}
\blob Problem-solving agents
\blob Problem types
\blob Problem formulation
\blob Example problems
\blob Basic search algorithms
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Problem-solving agents}
Restricted form of general agent:
\input{\file{algorithms}{simple-PS-agent-algorithm}}
Note: this is {\em offline} problem solving.\\
{\em Online} problem solving involves acting without complete
knowledge of the problem and solution.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Romania}
On holiday in Romania; currently in Arad.\\
Flight leaves tomorrow from Bucharest
\u{Formulate goal}:\nl
be in Bucharest
\u{Formulate problem}:\nl
{\em states}: various cities\nl
{\em operators}: drive between cities
\u{Find solution}:\nl
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: Romania}
\epsfxsize=\maxfigwidth
\fig{\file{figures}{romania.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Problem types}
\u{Deterministic, accessible} $\Longrightarrow$ {\em single-state problem}\\
\u{Deterministic, inaccessible} $\Longrightarrow$ {\em multiple-state problem}
\u{Nondeterministic, inaccessible} $\Longrightarrow$ {\em contingency problem}\nl
must use sensors during execution \nl
solution is a {\em tree} or {\em policy} \nl
often {\em interleave} search, execution
\u{Unknown state space} $\Longrightarrow$ {\em exploration problem} (``online'')
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: vacuum world}
\begin{tabular}{lr}
\hbox{\begin{minipage}[b]{0.6\textwidth}
\u{Single-state}, start in \#5. \q{Solution}
\\
\u{Multiple-state}, start in $\{1,2,3,4,5,6,7,8\}$\\
e.g., $Right$ goes to $\{2,4,6,8\}$. \q{Solution}
\\
\u{Contingency}, start in \#5\\
Murphy's Law: $Suck$ can dirty a clean carpet\\
Local sensing: dirt, location only.\\
\q{Solution}
\end{minipage}}
&
\epsfxsize=0.4\textwidth
\epsffile{\file{figures}{vacuum2-space.ps}}
\end{tabular}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Single-state problem formulation}
A {\em problem} is defined by four items:
\u{{\em initial state}} \quad e.g., ``at Arad''
\u{{\em operators}} (or {\em successor function} $S(x)$) \nl
e.g., Arad $\rightarrow$ Zerind \qquad Arad $\rightarrow$ Sibiu \qquad etc.
\u{{\em goal test}}, can be\nl
{\em explicit}, e.g., $x$ = ``at Bucharest''\nl
{\em implicit}, e.g., $NoDirt(x)$
\u{{\em path cost}} (additive)\nl
e.g., sum of distances, number of operators executed, etc.
A {\em solution} is a sequence of operators\\
leading from the initial state to a goal state
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Selecting a state space}
Real world is absurdly complex \nl
$\Rightarrow$ state space must be {\em abstracted} for problem solving
(Abstract) state = set of real states
(Abstract) operator = complex combination of real actions\nl
e.g., ``Arad $\rightarrow$ Zerind'' represents a complex set\nnl
of possible routes, detours, rest stops, etc. \\
For guaranteed realizability, \u{any} real state ``in Arad''\al
must get to {\em some} real state ``in Zerind''
(Abstract) solution = \nl
set of real paths that are solutions in the real world
Each abstract action should be ``easier'' than the original problem!
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: The 8-puzzle}
\epsfxsize=0.6\textwidth
\fig{\file{figures}{8puzzle.ps}}
\q{states}\\
\q{operators}\\
\q{goal test}\\
\q{path cost}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: The 8-puzzle}
\epsfxsize=0.6\textwidth
\fig{\file{figures}{8puzzle.ps}}
\q{states}: integer locations of tiles (ignore intermediate positions)\\
\q{operators}: move blank left, right, up, down (ignore unjamming etc.)\\
\q{goal test}: = goal state (given)\\
\q{path cost}: 1 per move
[Note: optimal solution of $n$-Puzzle family is NP-hard]
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: vacuum world state space graph}
\epsfxsize=0.8\textwidth
\fig{\file{figures}{vacuum2-paths.ps}}
\q{states}\\
\q{operators}\\
\q{goal test}\\
\q{path cost}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: vacuum world state space graph}
\epsfxsize=0.8\textwidth
\fig{\file{figures}{vacuum2-paths.ps}}
\q{states}: integer dirt and robot locations (ignore dirt {\em amounts})\\
\q{operators}: $Left$, $Right$, $Suck$\\
\q{goal test}: no dirt\\
\q{path cost}: 1 per operator
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Example: robotic assembly}
\epsfxsize=0.5\textwidth
\fig{\file{figures}{stanford-arm+blocks.ps}}
\q{states}: real-valued coordinates of\nl
robot joint angles\nl
parts of the object to be assembled
\q{operators}: continuous motions of robot joints
\q{goal test}: complete assembly {\em with no robot included!}
\q{path cost}: time to execute
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Search algorithms}
Basic idea:\al
offline, simulated exploration of state space\al
by generating successors of already-explored states\nnl
(a.k.a.~{\em expanding} states)
\input{\file{algorithms}{informal-gs-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{General search example}
\epsfxsize=0.7\textwidth
\fig{\sfile{figures}{general-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{General search example}
\epsfxsize=0.7\textwidth
\fig{\sfile{figures}{general-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{General search example}
\epsfxsize=0.7\textwidth
\fig{\sfile{figures}{general-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{General search example}
\epsfxsize=0.7\textwidth
\fig{\sfile{figures}{general-romania4.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Implementation of search algorithms}
\input{\file{algorithms}{general-search-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Implementation contd: states vs.~nodes}
A {\em state} is a (representation of) a physical configuration\\
A {\em node} is a data structure constituting part of a search tree\nl
includes {\em parent}, {\em children}, {\em depth}, {\em path cost} $g(x)$\\
{\em States} do not have parents, children, depth, or path cost!
\epsfxsize=0.65\textwidth
\fig{\file{figures}{state-vs-node.ps}}
The {\sc Expand} function creates new nodes, filling in the various
fields and using the {\sc Operators} (or {\sc SuccessorFn}) of the
problem to create the corresponding states.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Search strategies}
A strategy is defined by picking the {\em order of node expansion}
Strategies are evaluated along the following dimensions:\nl
\u{completeness}---does it always find a solution if one exists?\nl
\u{time complexity}---number of nodes generated/expanded\nl
\u{space complexity}---maximum number of nodes in memory\nl
\u{optimality}---does it always find a least-cost solution?
Time and space complexity are measured in terms of\nl
$b$---maximum branching factor of the search tree\nl
$d$---depth of the least-cost solution\nl
$m$---maximum depth of the state space (may be $\infty$)
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Uninformed search strategies}
{\em Uninformed} strategies use only the information available\\
in the problem definition
Breadth-first search
Uniform-cost search
Depth-first search
Depth-limited search
Iterative deepening search
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Breadth-first search}
Expand shallowest unexpanded node
\u{Implementation}:\nl
{\sc QueueingFn} = put successors at end of queue
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{bfs-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Breadth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{bfs-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Breadth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{bfs-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Breadth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{bfs-romania4.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of breadth-first search}
\q{Complete}
\q{Time}
\q{Space}
\q{Optimal}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of breadth-first search}
\q{Complete} Yes (if $b$ is finite)
\q{Time} $1+b+b^2+b^3+\ldots +b^d = O(b^d)$, i.e., exponential in $d$
\q{Space} $O(b^d)$ (keeps every node in memory)
\q{Optimal} Yes (if cost = 1 per step); not optimal in general
{\em Space} is the big problem; can easily generate nodes at 1MB/sec\nl
so 24hrs = 86GB.
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Romania with step costs in km}
\epsfxsize=1.0\textwidth
\fig{\file{figures}{romania2.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Uniform-cost search}
Expand least-cost unexpanded node
\u{Implementation}:\nl
{\sc QueueingFn} = insert in order of increasing path cost
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{uc-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Uniform-cost search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{uc-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Uniform-cost search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{uc-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Uniform-cost search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{uc-romania4.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of uniform-cost search}
\q{Complete} Yes, if step cost $\geq \epsilon$
\q{Time} \# of nodes with $g \leq {}$ cost of optimal solution
\q{Space} \# of nodes with $g \leq {}$ cost of optimal solution
\q{Optimal} Yes
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Depth-first search}
Expand deepest unexpanded node
\u{Implementation}:\nl
{\sc QueueingFn} = insert successors at front of queue
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{dfs-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Depth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{dfs-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Depth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{dfs-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Depth-first search}
.
.\\
.
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{dfs-romania4.ps}}
\vspace*{-0.6in}
I.e., depth-first search can perform infinite cyclic excursions\\
Need a finite, non-cyclic search space (or repeated-state checking)
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary4.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary5.ps}}
%%%%%%%%%%%% SLide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{DFS on a depth-3 binary tree, contd.}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary6.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary7.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary8.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{DFS on a depth-3 binary tree}
\vspace*{0.3in}
\epsfxsize=1.0\textwidth
\fig{\sfile{figures}{dfs-binary9.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of depth-first search}
\q{Complete}
\q{Time}
\q{Space}
\q{Optimal}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of depth-first search}
\q{Complete} No: fails in infinite-depth spaces, spaces with loops\nl
Modify to avoid repeated states along path\nnl
$\Rightarrow$ complete in finite spaces
\q{Time} $O(b^m)$: terrible if $m$ is much larger than $d$\nl
but if solutions are dense, may be much faster than breadth-first
\q{Space} $O(bm)$, i.e., linear space!
\q{Optimal} No
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Depth-limited search}
= depth-first search with depth limit $l$
\u{Implementation}:\nl
Nodes at depth $l$ have no successors
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative deepening search}
\input{\file{algorithms}{ids-algorithm}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative deepening search $l=0$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania1.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative deepening search $l=1$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Iterative deepening search $l=1$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania2.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Iterative deepening search $l=2$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania1.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Iterative deepening search $l=2$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania2.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Iterative deepening search $l=2$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania3.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Iterative deepening search $l=2$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania4.ps}}
%%%%%%%%%%%% Overlay %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pheading{Iterative deepening search $l=2$}
\vspace*{0.3in}
\epsfxsize=1.1\textwidth
\fig{\sfile{figures}{ids-romania5.ps}}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of iterative deepening search}
\q{Complete}
\q{Time}
\q{Space}
\q{Optimal}
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Properties of iterative deepening search}
\q{Complete} Yes
\q{Time} $(d+1)b^0 + d b^1 + (d-1)b^2 + \ldots + b^d = O(b^d)$
\q{Space} $O(bd)$
\q{Optimal} Yes, if step cost = 1\nl
Can be modified to explore uniform-cost tree
%%%%%%%%%%%% Slide %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\heading{Summary}
Problem formulation usually requires abstracting away real-world details
to define a state space that can feasibly be explored
Variety of uninformed search strategies
Iterative deepening search uses only linear space\\
and not much more time than other uninformed algorithms
\end{huge}
\end{document}