\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  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 anyway in not so efficient way, it arises two questins (i) Can a robot elaborate its behavior by learning through a number of trials? (ii) If the learning is successful, can we expect the robot behavior is not deterministic but adaptive? It would be difficult to be likely, if not at all. So we challange.
}

\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 technique 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. 
According to Rote et al. \cite{rote} 
the textual record of the jeep problem begun with
the 52nd problem in the "{\it Propositiones ad acuendos inventes}" (in Latin) attributed to Alcuin of York (BC 732-804) as a problem of camel carrying grain in a desert, and ends with currently popular form of a mathematical puzzle in which we have its analytical solution. 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; 
Hence there are four actions which move the jeep east, west, south, and north from one cell to one cell; the distance the jeep procceds is measured by {\it Manhattan distance}.\\
%%There are four deterministic primitive actions which move the agent up, down, left and right.


\noindent
Unless the size of the grid is very huge, we do not need a big intelligence to make it.
Even random walk could eventually reaches to the exit.
Then question is,
``Can a navigation robot elaborate its behavior by learning through a number of trials?''
Then if we succeed in attaining this goal, ``Can we call it an intelligent behavior?''
For instance, assume we live in a foreign country and not so familiar with their language.
When we cannot understand a phrase and ask what, one {\it not so intelligent} would repeat 
the same phrase, maybe with a little louder voice while {\it intelligent} one would explain
in yet another way. When we say our robot has an artificial intelligence, we expect it
to behave adaptively, that is, in equivallently but differently than previous trial.
In a sence, what we want is an adaptive behavior not a deterministic one.
That is, what we expect is an everytime different efficient behavior of the agent in the same environment. Like our choice of wine in the same wine shop
This is not easy for any machine learning, if not at all. 



\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
Then questions then are  (i) ``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
We may use a population based search, such as Genetic Algorithm, starting from a population of agents with all randomly created agents, and fitness evaluation being by how close each individual agent approaches to the exit.\\

\noindent
Under our scenario in a desert simulated by a gridworld where a jeep which needs fuels to move and carries containers besides its tank for fuels, inputs to the agent (jeep) are what it sees in each of the cells where jeep locates. So, it might be three-fold: (i) it sees nothing, (ii) it sees the  container previously put, and (iii) it finds the cell it currently locates is the base. The out puts are one of actions it should depending where it locates. So it 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.\\

\noindent
As such agents who could solve the problem, feed-forward or recurrent artificial neural network might be one of the simplest ways.\\

\noindent %% koko
Or, Finite State machine (FSM) would be yet another implimentation of such an agent.
FSM is three-tuples $<State, Input, Action>$. Agent takes one of the pre-specified states in each of which one action is determined by the input given to the agent.
Back in 1992, in their seminal paper, Jefferson et al.~\cite{jeff} reported an elegant experiment of trail-following problem. The world was also the two-dimensional toroidal grid in which a trail called the {\it ``John Muir trail''}  is specified.
The trail is a sequence of discret fixed cells in the grid including 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. An implementaion of Genetic Algorithm as an evolutionary learning resulted in an excellent 16 states FSM which succeeded in following the 92 squares of the trail.\\

However, in our problem of Jeep survival in a desert, an initial population of 4000 
simply desined random individual FSM never proceed even one distance, and as such selection never works in a small scale experiment in which jeep allowed to return the base for refill 2 times
. Totally sort of {\it a-needle-in-a-haystack} problem.

\subsection{But would it be worthy to be called intelligente?}
\noindent
Notice here, the action of the above mentioned successful FSM is totally deterministic, which was a natural result since the solution is only one unique way. However, such a deterministic solution which always behave in exactly an identical way can be  called  intelligent? The same question holds to our lots of successful report of robot navigation by artificial neural networks. We don't think this kind of behavior as intelligent, even if the task may be very sophisticated one.\\

\noindent
In order to alleviate this might-be-clever-but-always-identical solution, we may introduce stochastic variables. FSM, for example, can be modified so that every action in a state with an input is determined following a probability function, like a Hidden Markov Process.
Standard Reinforcement Learning is one of such implementation in a sense.
The agent takes a sequence of primitive actions in a discrete, fixed time scale. 
On each time step, the agent observes the state of its environment and chooses an action
Then one time step later, the agent receives a reward and the environment transitions
to a next state.
The transition to a new state is according to the probability, regardless
of the path taken by the agent before the current state.
Policy, is defined as probability distribution for picking actions in each state. 
The goal of the agent is to find a policy that maximizes the total reward received over time.





\subsection{Neural Networks with adaptive synapse.}
\noindent
In their paper, Stanley et al.~\cite{stan} wrote {\it "... environments can be unpredictable and fixed control policies may fail when conditions suddenly change. Thus, there is a need to evolve neural networks that can adapt, i.e. change their control policy dynamically as conditions change.'}\\

\noindent
Even if fixed control policies may not fail since in our case conditions will not suddenly change
and no need change thier control policy dynamically, we don't think this behaviour is intelligent.
Though an empty desert in our experiment of this paper will not suddenly change, what we want is not a deterministic result of behavior after learning. Therefore their method is worthy to try.\\

\noindent
Stanley et al.~ went on writing further, ``The first method evolves recurrent neural networks
with fixed connection weights, relying on internal
state changes to lead to changes in behavior.

%%we are not interested in solutions which are static after applying a machine-learnign techniqu or computational evolution.


\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.\\

%% one-d vs two d  that's the reason we extended the dimension of the original version into tws. 


\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



\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{rote}
Rote, G. and G. Zhang (1996)  
"Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling."
Spezialforschungsbereich F-003 Technical Report No. 71, T.U. Graz, Austria
url = citeseer.ist.psu.edu/article/rote96optimal.html

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

\bibitem{jeff}
Jefferson, D., R.~Collins, C.~Cooper, M.~Dyer, M.~Flowers, R.~Korf, C.~Taylor, and A.~Wang (1991)
``Evolution as a theme in artificial life: The genesys/tracker system.''
Artificial Life II: Proceedings of the Workshop on Artificial Life, pp. 549--577, 
Addison-Wesley.

\bibitem{stan}
Stanley, K.~O, B.~D. Bryant, and R.~Miikkulainen (2003) "Evolving Adaptive Neural Networks with and without Adaptive Synapses." Proceedings of the IEEE Congress on Evolutionary Computation, Vol. 4,  pp. 2557--2564.

\end{thebibliography}
\end{document}



Optimal-Logistics-for-Expeditions:-the-Jeep-Problem-with-Complete-Refilling

