\documentstyle[twocolumn,eclepsf,IEEEtran]{article}

%%\textheight 250mm
\topmargin -2mm
%%\textwidth 180mm
%%\oddsidemargin -7mm

\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
\def\bs{-0.5ex}

\begin{document}
\title{What we can do for Jeep in a Desert: \\
Which is cleverer --- human or learning-machine?
}

\author{{\bf Akira Imada} \\
            \normalsize Brest State Technical University \\ [\bs]
            \normalsize Moskowskaja 267 Brest 224017 Belarus \\ [\bs]
            \normalsize akira@bstu.by \\ [\bs]}

\pagestyle{empty}
\maketitle

{\it \noindent
Abstract -- This article is not a report of success but a proposal of a benchmark that we believe not solvable by any of so-far-proposed machine learning techniques or computational evolutions. The  benchmark is for robot navigation in two dimensional grid-world. A robot starting from somewhere in the grid should look for the exit of which the robot has no information about where.
Furthermore, the robot needs to consume fuels to move, and the exit is far away from the starting point such that the robot must refill fuels to reach the exit. Assuming the robot can make it somehow in not so efficient way, the question is, ``Can a robot elaborate its behavior by learning through a number of trials?'' It might sound easy, but what we want is adaptive behavior not a deterministic action. This is extremely difficult, if not impossible.
}

\bigskip
{\it \noindent
Keywords -- Robot navigation in a grid-world, A needle in a haystack, Jeep problem, Computational evolution, Machine-learning techniques.
}

\bigskip
\section{Introduction}
\begin{quotation}
\begin{small}
\noindent
{\it 
So, I lived all alone, without anyone I could really talk to, until I had to make a crash landing in the Sahara Desert six years ago. Something in my plane's engine has broken, and since I had neither a mechanic nor passengers in the plane with me. I was preparing to undertake the difficult repair job by myself. For me it was a matter of life or death: I had only enough drinking water for eight days.
-- ``The Little Prince'' by Antoine de Saint Exupery (translated by R. Howard.)
}
\end{small}
\end{quotation}

\bigskip \noindent
The research field of computational evolution or machine-learning techniques is now quite mature, and as such, we have had tremendously lots of success reports on how they solve a difficult problem, claiming like, {\it ``The result solves a problem of indisputable difficulty in its field.''} 
Or, {\it ``Techniques of genetic and evolutionary computation are being increasingly applied to difficult real-world problems -- often yielding results that are not merely interesting, but competitive with the work of creative and inventive humans.''}\footnote{These two expressions are appeared in ``Call for entries for \$10,000 in awards -- The 2007 'Humies' -- for human competitive results.'' This competition was held in the {\it Genetic and Evolutionary Computation Conference} in London in 2007.}\\

\noindent
Those claims might be true. However, the opposit also holds. Some problems would be extremely easy to be solved by a human, but remain unsolvable by any so-called artificial-intelligent technique. In this report, we propose one such problem as a benchmark, expecting it challenges our  neural network, machine-learning, evolutionary-computation community, whatsoever.\\


\noindent
The task is as follows. 
A robot navigates in a desert with a jeep which can carry a limited amount of fuel,
starting from its base where the jeep can return later to refill the fuel.
The jeep has containers to put some of its fuels somewhere in the desert to use it in future.
The task is to find the exit of the desert far away from the base, by repeating the procedure:
%%The goal is to maximize the penetration of the jeep into the desert by repeating the following four actions: 
(i) start the base; (ii) navigate the desert; (iii) put fuels somewhere or find the 
fuels to get; and  (iv) return to the base. Robot is allowed to return to the base pre-specified limited times.\\

\noindent
This task is an extension of a mathematical puzzle called a {\it jeep-problem} in which a jeep explores one-dimensional desert under a constraint. A robot here navigates a two-dimensional grid-world instead of one-dimensional desert.

\noindent
The problem is studied here in a simulation, that is, a navigation robot explores a fictitious $N \times N$ grid-world. Hence, the motion of the jeep is from one cell to one cell to the north, south, east, or west; the distance of penetration is by {\it Manhattan distance}.\\



\noindent
The question is,
``Can a navigation robot elaborate its behavior by learning through a number of trials?''
This should be done not in a deterministic way, but in an adaptive way.


\bigskip
\section{A Preliminary Experiment}
\begin{quotation}
\begin{small}
\noindent
{\it 
From a mountain as high as this one, he said to himself, I'll get a view of the whole planet and all the people on it... But he saw nothing but rocky peaks as sharp as needles.
-- ``The Little Prince'' by Antoine de Saint Exupery (translated by R. Howard.)
}
\end{small}
\end{quotation}

\bigskip \noindent
As a preliminary experiment, let's try a kind of two-dimensional version of {\it a-needle-in-a-haystack problem.} The task is to look for a needle, or equivalently, uniquely pre-determined location in the grid-world. The robot has no information of where the needle is. The navigation is by random walk. The robot is expected to eventually find the location, unless $N$ is very large. Question is whether the robot can minimize the path length by a learning algorithm later? \\

\noindent
The expectation of number of steps of a robot to reach the exit is $O(N^2)$. The result of our experiment to confirm this is shown in Fig.~1 by the average number of steps in 100 runs plotted as a function of $N^2$. This might be called {\it a two-dimensional version of a-needle-in-a-hay-stack} problem.\footnote{The problem in general from a computational context was firstly described in 1987 by Hinton \& Nowlan \cite{hint} as {\it a needle being a unique configuration of 20-bit binary string while all other configurations being a haystack.}}\\

\noindent
We tried this experiment by increasing the grid size. As size grows the task becomes difficult. The experiment is still on going, but according to our so-far observation of 1000 different runs, when grid size is 17,000 $\times$ 17,000, the minimum steps required was 25,987,691, and the robot reached the needle only in 119 out of 1,000 runs. The number of steps is starting to explode. \\

\noindent
The question then will be,  ``A learning can enhance the efficiency?'' In other words,
``If a robot try it multiple times under a learning scheme, then the number of steps of the robot
to reach the exit becomes shorter than the previous trials, or hopefully minimized?''\\


\begin{figure}
\centering
%%\includegraphics[width=7cm,height=3cm]{navi-1-new.eps}
\epsfile{file=navi-1-new.eps,width=7cm,height=5cm}
\caption{Average number of steps during 100 runs until a robot who explores the $N \times N$ 
grid starting from $(1,1)$ by a random walk eventually reaches $(N,N)$ as a function 
of number of cells in the grid $N^2$.}
\end{figure}

\noindent
In Fig.~2 we show the experiment when the grid size is $96 \times 96$. First, by a random walk. Starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no {\it a-priori} information.\footnote{The reason for the start and goal are far inside the grid is, otherwise robot found a more clever warp utilizing our toroidal character of the grid. Namely, robot could reach from (1,1) to $(N,N)$ just with 1 step at the minimum.} We observed a 100 such runs and in the left of the Fig.~2 we show the minimum path out of those 100 different walks.\\

\noindent
Then we tried a evolutionary learning, just as an example among many others, 
in which a possible trace of robot is expressed by a chromosomes whose gene is either 0, 1, 2, or 3, meaning to move one cell to the north, south, east or west, respectively. The length of one chromosome is $N^2$. Following this chromosome from one gene to the next, the robot moves from one cell to the next. After each movement it is checked if the current location is the goal or not. If it is the goal the walk is completed, otherwise to the next cell. The longest possible path length would be thus $N^2$ but most likely much less than that. The fitness is the number of steps to the goal. If the robot did not reach the goal after following  all the $N^2$ genes, the walk failed. The selection is by {\it fitness proportionate}, reproduction is by {\it one-point crossover} and mutation is by replacement with other gene chosen at random with the probability of $1/N$. A result of trace after the evolution is shown in the right of the Fig.~2, and the fitness evolution is shown in Fig.~3.

\begin{figure}[bhtp]
\begin{center}
%%   \includegraphics[width=5cm,height=6cm]{trace-96-start.eps}
%%   \includegraphics[width=5cm,height=6cm]{trace-96-end-new.eps}
\epsfile{file=trace-96-start.eps,width=4.4cm,height=4.6cm}
\epsfile{file=trace-96-end-new.eps,width=4.4cm,height=4.6cm}
\caption{In the grid-world of $96\time96$ starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no {\it a-priori} information. Left: The path of minimum length among 100 trials by random walk. Right: Minimal path the robot found after an evolutionary learning as shown in Fig.~3. (Marginal area is omitted.)}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
%% \includegraphics[width=9cm,height=7cm]{evolution-96-new.eps}
\epsfile{file=evolution-96-new.eps,width=8cm,height=6cm}
\caption{An evolution of the number of steps to the goal starting with a population of 
random walks. We can see the convergence to the global minimum of 48 Manhattan distance.}
\end{center}
\end{figure}




\section{Challenge}

\begin{quotation}
\begin{small}
\noindent
{\it 
He answered, "Oh come on! Your know!" as if we were talking about something quite obvious. And I was forced to make a great mental effort to understand  this problem all by myself.
-- ``The Little Prince'' by Antoine de Saint Exupery (translated by R. Howard.)
}
\end{small}
\end{quotation}

\bigskip \noindent
Can a learning robot survive in a desert with a jeep?\\

\noindent
We now assume  that the jeep are in the base located at the center of a desert.
Again our world is a two-dimensional grid. This time, for some reasons which later become clear,
size is $77 \times 77$, the coordinate of the bottom-left corner is $(-38, -38)$, and
the top-right corner is $(38,38)$ which is the only exit of the desert.
The base is located at the origin $(0,0)$. The grid is toroidal, that is, if the coordinate
becomes $(N+1)$ and $-(N+1)$ then it is replaced with $-N$ and $N$, respectively.\\

\noindent
A robot leaves the base with a jeep. The jeep moves the desert of grid 
%% horizontally or vertically,
from one cell to the next, each time by consuming  one unit of fuel. The jeep has
a tank for fuel whose capacity is 30 units. The jeep also has a container with which
the robot can store some amount of fuel in the tank to put at any location in the desert
for the next time usage. 
Since the exit is 76 {\it Manhattan-distance} apart from the base,
the tank full of 30 units are not enough to reach the exit.
The robot is allowed to go back to the base twice to refill the tank.\\


\noindent
This is an extension of so-called a {\it jeep problem} where
a jeep should maximize its penetration to one-dimensional desert under a constraint.
See, for example, the WWW page of 
{\it Wolfram MathWorld}.\footnote{http://mathworld.wolfram.com/JeepProblem.html.}
It reads:
\begin{quotation}
\noindent
{\it ``Maximize the distance a Jeep can penetrate into the (one-dimensional)
desert using a given quantity of fuel. 
The Jeep is allowed to go forward, unload some fuel, and then return to its base 
using the fuel remaining in its tank. At its base, it may refuel and set out again. 
When it reaches fuel it has previously stored, it may then use it to partially fill its tank. 
This problem is also called the exploration problem (Ball and Coxeter 1987).''}
\end{quotation}

\noindent
As far as we know, this has never extended to a two-dimensional world. We now summarize the problem.

\bigskip \noindent
{\bf Challenge (Jeep's survival in a desert)}\\
{\it Assume $77 \times 77$ toroidal lattice each of whose cells is expressed by (i,j) where
$i,j=-$38, $-$37 $\cdots$, 0, 1, 2, $\cdots$, 37, 38. We call this grid a desert.
The desert has only one exit at (38,38).
Starting from (0,0) a robot navigates a jeep from one cell to the next. 
In order for the jeep to move one cell, it needs to spend one unit of fuel, and 
the jeep has the tank whose capacity is 30 units. The jeep also has a container with which
the robot put some amount of fuel to any location of the desert for the next time usage.
Allowing to go back to the base twice, can the robot learn how to reach the exit through
a multiple times of experiences of failure?}\\

\noindent
Or, we might be modified it like the original one, 
as follows. {\it The size is more generally $N \times N$ 
for a large enough $N$. Starting from also the base at (0,0) and being allowed to go back 
to the base R times to refill the fuels, the  robot should penetrate
the maximum distance from the base instead of aiming the exit of the desert.} 

\bigskip
\section{Possible Approaches}
\begin{quotation}
\begin{small}
\noindent
{\it 
A geographer is too important to go wandering about. He never leaves his study. But he receives the explorers there. He questions them, and he writes down what they remember.
-- ``The Little Prince'' by Antoine de Saint Exupery (translated by R. Howard.)
}
\end{small}
\end{quotation}

\bigskip \noindent
As such agents who could solve our problem, let's try here two candidates, among others.
One is Neural Network and the other is Finite State machine (FSM). And as learning, we experiment with a Computational Evolution and Reinforcement Learning.

\subsection{Neural Network under Evolutionary Computation}
\noindent
With architecture being Feed Forward or Recurrent, whichever it might be, input is what the jeep sees in each of the cells which jeep locates. So, it might be three-fold: (i) see nothing, (ii) see container previously put, and (iii) find the cell is base. 
Out put might be six-fold: (i) put a unit of fuel, (ii) get a unit of fuel, (iii) move north, (iv) move south, (v) move east or (vi) move west. We may use a population-learning, such as Genetic Algorithm, starting from a population of agents with all random weight connections, and fitness evaluation being by how close each individual agent approaches to the exit.

\subsection{Finite State Machine under Reinforcement learning}
\noindent
FSM could also explore the desert. With two inputs -- nothing to see or container there, and six actions --- the same as those in the neural network above. The number of states should be arbitrary large. The behavior of the FSM is determined by the transition table which determine the next action and the next state according to the current state and input. Though these FSMs could learn the behavior also by a Computational Evolution as in Neural Network above, but here for a change, we might use Reinforcement Learning.\\

\noindent
I will describe these two implementations more in detail in case our kindly reviewer generously accept this submission.

\bigskip
\section{We know a solution, but...}
\begin{quotation}
\begin{small}
\noindent
{\it 
I made an exasperated gesture. It is absurd looking for a well, at random, in the vastness of the desert. But even so, we started walking.
-- ``The Little Prince'' by Antoine de Saint Exupery (translated by R. Howard.)
}
\end{small}
\end{quotation}

\bigskip \noindent
As already mentioned, the task is an extension of the Jeep problem. This is quite an old problem, and we now have to confess that we know the analytical solution. Let's see the already known solution of the original version in the one-dimensional desert here.

\begin{itemize}
{\it
\setlength{\itemsep}{0pt}
\item[1)] Start with 30 units of fuel.                                           %% (00 30)
\item[2)] Go forward 10 distances, put 10 units, and then go back to the base 
          with the remaining 10 units of fuels, and refill 30 units again.       %% (00 00)
\item[3)] Go forward 10 with 30 units refilled, spending 10 units,
           and get 10 units there.                                               %% (10 30)
\item[4)] Go forward 6 further, spending 6 units and put there 8 units.          %% (16 16)
\item[5)] Go back to the base spending remaining 16 units                        %% (00 00)
\item[6)] With 30 units again, go forward 16 , spending 16 units,
           and get 8.                                                            %% (16 22)
\item[7)] Go forward further until spending all the remaining fuel, and
          eventually reach the point which is 38 apart from the base.
}
\end{itemize}

\noindent
This is how the jeep can penetrate to the desert with the maximum distance
when allowed to go back to the base twice. 
You now notice the reason why those parameters in our two-dimensional version described here
 are highly artificially devised. It is to fit the problem.\\

\noindent
As you now know, the solution can be simply applied to the two-dimensional grid-world. However, we must notice, we have infinite number of such optimal paths to the exit while only unique in the case of one-dimensional desert.


\section{Concluding Remarks}
\noindent
To put it frankly we have had no good results for this problem as of today.\\

\noindent
Back in 1992, in their seminal paper, Jefferson et al.~reported a similar experiment of trail-following problem. The world is also the two-dimensional toroidal grid in which a trail called the {\it John Muir trail} is specified. The trail is not continuous but includes empty gap(s) whose length is from one to three. The task of the agent is to move from square to square, traversing as much of the trail as possible. As a candidate of the agent, a FSM under Genetic Algorithm was proposed, while commenting, ``Neural network will perform better than FSM.'' But we are wondering, how many input nodes are necessary in its minimal case. If we think it of one input, what, on earth, might be its struchture?\\

\noindent
Anyway, their results looked excellent using FSM which succeeded in following the 92 squares
of the trail after the FSM's evolutionary learning.\\

\noindent
Notice, however, the action of the successful FSM is totally deterministic. The result is natural since the solution is only one unique way.\\

\noindent
Then what about in our problem?
As we already mentioned, we have plenty of paths of the minimum length in the case of two-dimensional grid. What if the jeep which learned successfully follows always the same path as it found for the first time, totally neglecting the other possibilities? How can we call this behavior an {\it intelligent} one? All we want is an adaptive behavior of the successfully learned agents, like an intelligent human.
As far as we know, we have never had such artificial intelligent behaviors after learning in any of those successful reports.
Is it possible or just a fantasy?


\bigskip
\begin{thebibliography}{99.}
\bibitem{hint}
Hinton, G.~E., and S.~J.~Nowlan (1987)
``How Learning can guide evolution?''
Complex Systems, Vol. 1, pp. 495--502.

\bibitem{rema}
Remazeilles, A., and F.~Chaumette (2007)
``Image-based robot navigation from an image memory.''
Robotics and Autonomous Systems archive, Vol. 55(4), pp. 345-356.

\end{thebibliography}
\end{document}

\bibitem{srin}
Srinivasan, B.~(2006)
``Analysis of memory-based learning schemes for robot
navigation in discrete gridworlds with partial observability.''
Available at author's WWW page but the author says this is just ``Other paper.''\\
\verb\(http://www.stanford.edu/~bharsrin/docs/papers/)\

\bibitem{sutt}
Sutton, R.~S.~(1996)
``Generalization in reinforcement learning: Successful examples using sparse coarse coding.''
Advances in Neural Information Processing Systems 8, MIT Press. pp. 1038-1044.

\bibitem{watk}
Watkins, C.~J.~C.~H.~(1989)
``Learning from delayed rewards.'' PhD thesis, University of Cambridge.

\bibitem{grov}
Grover, L.~(1997)
``Quantum mechanics helps in searching for a needle in a haystack.'' 
Physical Review Letter, Vol. 79, pp. 325--328.

\bibitem{shen}
Shenvi, N., J.~Kempe, and B.~Whaley (2003)
``A Quantum random walk search algorithm.'' 
Physical Review A, Vol. 67, pp. 052307--052318.

\bibitem{beni}
Benioff, P.~(2002)
"Space searches with a quantum robot"
Contemporary Mathematics, Vol. 305, pp. 1--12.

\bibitem{knad}
Knaden, M., and R.~Wehner (2006)
``Ant navigation: resetting the path integrator.''
Journal of Experimental Biology Vol. 209, pp. 26--31.


