\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}

\usepackage{graphicx}
\usepackage{color}

\textheight 260mm
\topmargin 5mm
\textwidth 180mm
\oddsidemargin -7mm

\newtheorem{algorithm}{Algorithm}

\pagestyle{myheadings}
\markright{(ACS-2007 -- at Miedzyzdroje, Poland)}
\thispagestyle{empty}

\begin{document}
\begin{huge}

\clearpage  % (title) =========================================
\color{blue}
\hspace*{1in}\\
\bigskip 
\noindent
{\bf Can a learning robot survive in a desert? \\
\hspace*{0.79in} A 2-D expansion of the jeep problem}
\begin{center}
\hspace*{1in}\\
\color{black}
\begin{Large}
Akira Imada  \\
\bigskip
Brest State Technical University \\ 
Belarus
\end{Large}
\end{center}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Looking for ``a-needle-in-a-haystack''}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=10cm]{hay-2.eps}
\end{center}
\end{figure}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A needle hidden in a huge grid world}\\
\bigskip
\color{black}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=4cm,height=4cm]{grid.eps}
\end{center}
\end{figure}
{\LARGE
Can a navigation robot reach it? \\
$\Downarrow$ \\
A 2-D version of a-needle-in-a-haystack.
}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf What is a-needle-in-a-haystack} \\

\color{black}
\bigskip
{\LARGE
%% Assume we have a needle detector $F(x)$\\
%% Assume we have an {\it ORACLE} for  needle $F(x)$\\
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=6cm,height=1.2cm]{oracle.eps}
\end{center}
\end{figure}
\color{red}
``Find $x$ 
\color{black}
(among $N$ items)
\color{red} 
such that $F(x) = 1$'' \\
\color{black}
\bigskip
when \\
only \color{red} unique $x$ \color{black} 
%% from $N$ data 
fulfills $F(x)=1$ while $F(x)=0$ for all others.} \\
\bigskip
{\Large (We might call $F(x)$ a fitness function of this problem.)}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Complexity of the search} \\
\bigskip
\color{black}
$\Downarrow$ \\
\color{red}
Linear \\
\color{black}
or \\
We need \color{red} $O(N)$  \color{black} steps to reach the needle!
\end{center}


\clearpage  % =========================================
\color{blue}
{\bf \hspace*{.35in}How we search the needle \\ \hspace*{2in} as efficiently as possible?}
\begin{center}\color{black}
$\Downarrow$ \\
{\LARGE More efficient than a Random/Exhaustive search?}
\end{center}


%% they shoed us an ELEGANT experiment
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's Needle (1987)}\\
\end{center}

%% approximately one million points
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm,height=1.5cm]{a-needle-0.eps}
\end{center}
\end{figure}

\color{black}
\noindent
{\LARGE
$\bullet$ A-needle $\Rightarrow$ Just one configuration of 20-bit binary strings.
\begin{center}{\Large E.g. \color{red}(00110 10101 11010 10101)} \end{center}
\color{black}
$\bullet$ Haystack $\Rightarrow$ $2^{20}-1$ search points.}


%% they shoed us an ELEGANT experiment
%% We tried a random search with a same condition as Hinton & Nowlan's
%% I have never observed the needle more than 26bits by ANY search
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Their choice of 20-bit was a good one!}\\
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm,height=6cm]{random-search-needle-2.eps}
\end{center}
\end{figure}
\begin{LARGE}
\color{black}
Therefore, their experiment was not a very difficult one.\\
\color{red}
But can we reach a needle longer than 25 bits?
\end{LARGE}
\end{center}


%% if we are not ultralucky
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf How we evolve all-fitness-0 chromosomes?}\\

\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=5cm]{ga-baldwin.eps}
\end{center}
\end{figure}

\color{black}
{\Large $\bullet$ What about the task called ``All-one-problem?''\\
(9 $\times$ 14 $\Rightarrow$ 16 $\Rightarrow$ 17
vs.
0 $\times$ 0 $\Rightarrow$ 0 $\Rightarrow$ 0)}
\end{center}

% their smart trick is an inclusion of flexible genes which is expressed with red 9 here
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Hinton \& Nowlan's brilliant trick}\\
\bigskip
\color{black}
{\LARGE Evolution under Baldwin effect \\
\hspace*{2.5in} --- Lifetime learning of phenotype} \\
%% {\LARGE Lifetime learning of phenotype} \\
\end{center}
{\Large
\color{black}
\hspace*{1in}A genotype:
\begin{center}
(10\color{red}9\color{black}010\color{red}99\color{black}0110010010\color{red}9\color{black}1)\\
\end{center}
\hspace*{.85in} Its phenotype:
\begin{center}
(10\color{red}1\color{black}010\color{red}01\color{black}0110010010\color{red}0\color{black}1)\\
(10\color{red}0\color{black}010\color{red}11\color{black}0110010010\color{red}1\color{black}1)\\
...
\end{center}
}

\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect}\\
$\Downarrow$ \\
A hypothesis for biological evolution\\
\bigskip
\color{black}
{\LARGE Abilities obtained in parent's lifetime will inherit to offspring}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Their assumption}\\
\end{center}\color{black}
%%\bigskip
\hspace*{1in}{\LARGE The closer the {\it genotype} to the needle, \\
\hspace*{2.2in} the faster the learning of {\it phenotype.}}
\begin{center}
{\LARGE
$\Downarrow$ \\
This makes the sharp-fitness-peak a more smooth one.}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=3cm]{make-it-smooth.eps}
\end{center}
\end{figure}
\end{center}

%% We now look at the results
%% random search is the same as before but this time against number of search points instead of 
%% number of bits
%% we may see a tremendous improvement
%% the number of individuals who joined the search
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Baldwin effect looks great!}\\
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=13cm,height=6.5cm]{kauno-linear-2.eps}
\end{center}
\end{figure}

\clearpage  % =========================================
\hspace*{1in}\\
\begin{center} \color{blue}
{\bf I'm not an evangelist!}\\
\end{center}


%% are we REALLY happy ...
\clearpage   % =========================================
\begin{center} \color{blue}
{\bf Are we really happy with this?}\\ %% Baldwin effect?}\\
%%I'm not an evanjelist of this topic but rather opposite
\bigskip
\color{black}
{\LARGE
Why should we continue evolution\\
when lifetime-learning already has found the needle? \\

$\Downarrow$ \\

(Turney 1987)\\
{\it ``Not from an engineering  but a biological interest.''}
}
\end{center}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Still we are not so happy.}\\
\bigskip
\color{black}
{\Large 
{\it The number of \color{red} individuals}, or
{\it the number of total \color{red} points \color{black} visited}?}  

\bigskip
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=13cm,height=6.6cm]{total-points-visited-3.eps}
\end{center}
\end{figure}

\end{center}

\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Effect of like-to-hear-what-we'd-like-to-hear?}\\
\bigskip
\color{black}
$\Downarrow$ \\
{\Large An intelligent strategy is sometimes worse than a random one!}
\end{center}



\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A needle in a grid world}\\
\bigskip
\color{black}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=4cm,height=4cm]{grid.eps}
\end{center}
\end{figure}
{\LARGE
\color{red} No landmarks \color{black} like walls, corridors, or obstacles. \\
$\Downarrow$ \\
How can we know 
\color{red} ``Where we are?'' \color{black}
or 
\color{red} ``Where to go?'' \color{black}


}
\end{center}


\clearpage   % =========================================
\begin{center} \color{blue}
{\bf A random walk to the needle}\\
\end{center}

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=7cm,height=7cm]{walk.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Random walk evolved to be minimized}\\
\end{center}
\bigskip
\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=5cm,height=6cm]{trace-96-start.eps}
   \includegraphics[width=5cm,height=6cm]{trace-96-end-new.eps}
\end{center}
\end{figure}

\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Evolution successful}\\
\end{center}
\bigskip
\begin{figure}[h]
\begin{center}
\includegraphics[width=9cm,height=7cm]{evolution-96-new.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Number of steps grows linearly}
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=14cm,height=8.5cm]{navi-1-new.eps}
\end{center}
\end{figure}


%% it would be less likely for a random walk happened to reach the needle
\clearpage  % =========================================
\begin{center}\color{blue}
{\bf What if the grid is huge?}\\
\color{black} {\Large It seems less likely to reach the needle by chance.}
\end{center}
\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7cm,height=7cm]{random-walk-150.eps}
\end{center}
\end{figure}

\clearpage   % =========================================
\begin{center} \color{blue}
{\LARGE
{\bf Evolution will be harder as grid becomes larger}}\\
\end{center}

\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=8cm]{three-evolutions-5.eps}
\end{center}
\end{figure}

\clearpage  % =========================================
\hspace*{1in}\\
\begin{center}\color{blue}
{\bf A success at a small scale \\is not a royal road to a real success.}
\end{center}


%% Nevertheless we'd rather propose here a more demanding problem as a benchmark
%% using jeep problem. Jeep problem is ..
%% scenario is 
\clearpage  % =========================================
\begin{center}\color{blue}
{\bf The Jeep Problem}\\
\bigskip
\color{black}
{\LARGE
The 52nd problem \\
{\Large in the} \\
{\it ``Propositiones ad acuendos inventes''} (in Latin) \\
{\Large attributed to} \\
Alcuin of York (732--804)\\
$\Downarrow$ \\
\color{red} Camel carrying grain in a desert.}
\end{center}


\clearpage  % =========================================
%%\hfill{\Large (cont'd)}
\begin{center}\color{blue}
{\bf The task in the modern version}\\
\color{black}
\bigskip
{\LARGE Maximize the distance a Jeep can penetrate into 
\color{red} 1-D \color{black} desert.}
\end{center}
{\LARGE
\begin{itemize}
\item Jeep can move a unit distance with a unit fuel.
\item Jeep can unload its fuels anywhere in the desert.
\item Fuels can be filled only at the base.
\item Jeep can go back to the base \color{red} $n$ \color{black} times to re-fill its tank.
\end{itemize}
}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf A Stupid one but anyhow ...}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=6cm]{jeep-1d-stupid.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}\color{blue}
%%{\bf The Solution in a 1-D desert}
{\bf An example of a success for n=3}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=18cm,height=8cm]{jeep-1d.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf An analytical optimal solution} \\
\bigskip
\color{black}{\Large 
by N. J. Fine (1947)
\begin{displaymath}
%% d_0 = 0, \hspace{.2in} d_n = d_{n-1}+\frac{1}{2n-1}
d_0 = 0, \hspace{.2in} d_n = d_{n-1}+1/(2n-1).
\end{displaymath}
}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=4cm]{jeep-1d-solution.eps}
\end{center}
\end{figure}



\clearpage  % =========================================
\begin{center}\color{blue}
{\bf The optimum solution for n=3}
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=18cm,height=8cm]{jeep-1d-optimum.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}\color{blue}
%%{\bf A GA implementation}\\
{\bf A solution by a GA}\\
\color{black}
\bigskip
%%{\LARGE BY Przemyslaw Klesk (2004)}
%%{\LARGE by Przemys\l aw Kl\c{e}sk (2004) at E\l k}
{\LARGE Przemys\l aw Kl\c{e}sk (2004)}

\begin{figure}[h]
\begin{center}
\includegraphics[width=16cm,height=4cm]{jeep-ga.eps}
\end{center}
\end{figure}

{\Large {\it Concluded, ``Solution for $n>3$ was not available!!}}

\end{center}

\clearpage  % =========================================
\hspace*{1in}\\
\begin{center}\color{blue}
{\bf A success at a small scale \\is not a royal road to a real success.}
\end{center}

%% with the task being ...
\clearpage  % =========================================
\begin{center}\color{blue}
{\bf An extension to 2-D Desert}\\
\end{center}
\color{black}
\noindent
{\LARGE
\begin{center}
\color{red}``Maximize the penetration''
\color{black} or 
\color{red}``Find the needle'' \\ 
\color{black}by repeating the procedure:
\end{center}
\begin{itemize}
\item[] (1) Start the base.
\item[] (2) Navigate the desert.
\item[] (3) Put fuels somewhere, or find the fuels to get.
\item[] (4) Return to the base.
\end{itemize}
}


\clearpage  % =========================================
\begin{center}\color{blue}
{\bf Examples of a possible trace}\\ 
\end{center}
\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=8.5cm]{fictitious-2d-jeep.eps}
\end{center}
\end{figure}


\clearpage  % =========================================
\begin{center}
\color{blue}{\bf What we challenge here}\\
\end{center}
\color{black}{\LARGE
\begin{itemize}
\item In a 2-D desert
\begin{itemize}
   \item[$\star$] For $n = 1$
      \begin{itemize}
      \item[-] This is simply a-needle-search
      \end{itemize}
   \item[$\star$] For $n \ge 2$
      \begin{itemize}
      \item[-] Maximize penetration
      \item[-] \color{red}Search for a hidden needle \color{black}
      \end{itemize}
   \end{itemize}
\item In a higher dimensional grid
\end{itemize}
}



\clearpage  % =========================================
\begin{center}
\color{blue}{\bf Still resists to be solved!}\\
\bigskip
\color{black}{\LARGE
Evolutionary Computation \\
...... \\
Reinforcement learning \\
$\Downarrow$ \\
\color{red} An extremely tough benchmark\\
\color{black}
%%$\Downarrow$ \\
A challenge to a navigation robot community.}
\end{center}


\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Grover's quantum search (1997)}\\
\color{black}
\bigskip
A speed up from 
\color{red}
$O(N)$ 
\color{black}
to 
\color{red}
$O(\sqrt{N})$\color{black}.
\end{center}


\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{fictitious-classics.eps}
\includegraphics[width=7.5cm,height=4cm]{fictitious-quantum.eps}
\end{center}
\end{figure}



%% Owing
\clearpage  % =========================================
\begin{center} \color{blue}
{\bf A strange path of quantum computation}\\
\color{black}
\bigskip
\begin{Large}
When a particle goes from A to B, \\ it takes all possible paths at the same time.
\end{Large}
\end{center}

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=7.5cm,height=4cm]{quantum-path.eps}
\end{center}
\end{figure}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Quantum Robot}\\
\bigskip
\color{black}
{\LARGE Paul Benioff (2002) \\
%%``Space Searches with a Quantum Robot.''\\
$\Downarrow$ \\
{\it ``Only faster than classical search in more than 2-D!''}}
\end{center}

\clearpage  % =========================================
\begin{center} \color{blue}
{\bf Summary}
\end{center}
\color{black} {\LARGE
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Two challenges:
   \begin{itemize}
   \item[$\star$] A needle hidden in a huge grid world.
                  %%{\Large (n=1 of the below)}
   \item[$\star$] \color{red}2-D Jeep Problem by a learning navigation robot.\color{black}
         \begin{itemize}
         \item[] {\Large Can a robot learn to solve this? Then how, if any?}
         \end{itemize}
     \end{itemize}
\item We have to be careful because we \\
\hspace*{0.6in}{\it tend-to-hear-what-we-want-to-hear.}
%%\item Success at a small scale is not a success in a real world.
\item Success report sometimes holds true only in a small world.


\end{itemize}
}


\end{huge}
\end{document}


