\documentclass[10pt]{article}
\usepackage{graphicx}

\textheight 225mm
%\topmargin 5mm
\textwidth 175mm
\oddsidemargin -7mm

\pagestyle{empty}
\thispagestyle{empty}

\title{How can we design a more intelligent path-planning?}
\author{Akira Imada \\
\hspace*{1in}\\
Brest State Technical University\\
           Moskowskaja 267, Brest 224017 Republic of Belarus\\
           akira@bsty.by}
\date{}

\begin{document}
\maketitle

\begin{quotation}
\begin{small}
\noindent
{\it 
In the "Star Trek" prequel, Spock's father tells him, "You will always be a child of two worlds," urging him not to keep such a tight vise on his emotions. And Spandexy Old Spock, known as Spock Prime, tells his younger self: "Put aside logic. Do what feels right."
-- by Maureen Dowd, from her article in the New York Times on 10th May 2009. 
}
\end{small}
\end{quotation}

\noindent
We try to comtemplate in this paper on how it would be intelligent when we say artificial intelligence. Human intelligence is not always efficient enough worthy to be called optimized but rather spontaneous or unpredictable more or less. Even when we come accross a similar situation as before our behaviour may be different than the one we reacted then. Aiming such a flexibility in an artificial intelligent agent, we propose here a benchmark in which we have infinite nubmer of equally valuable solutions. And then we observe if an agent trained by some of the  machine learning techniques will behave in such an intelligent way as human's.\\

\noindent
By {\it ``path planing problem,''} we usually imply that our goal is to find a {\it shortest path} from a specified point to start to a specified point to finish. But what if our concern is to find the {\it longest path} to reach the goal with a limited amount of energy given? While a shortest-path-problem has a unique solution, this longest-path-problem has multiple solutions. Hence the latter will be a good benchmark to test if an agent can try a different route on each run.\\

\noindent
One option to realize this idea is that we make an agent learn during its action. The approach described here was motivated by the work by Floreano et al.~(2000) in which the authors controlled mobile robots by a neural network so that the robots navigate properly by modifying synaptic weights of the neural network during navigation. The modification was based on a set of four Hebbian-like rules with each of the rules specified by a number of parameters. Each of the connection weights determins which rule with which parameters to modify itself during its navigation. Starting with a random configuration of the weights a poulation search eventually converges an optimized configuration. Later Stanley (2003) united these four rules into one equation with two parameters. More recently Durr (2008) proposed a more general equation of learning.\\

\noindent
The experiments above were made using sigmoid neurons, that is, state takes a continuous value. We now are planning to use a neural network with spiking neurons. A counterpart of Hebbian learning is {\it spike-timing-dependent-plasticity}, or {\it STDP}.\\

\noindent
{\bf A benchmark.}
To test how an agent behaves under some machine learning techniques, we propose here the following problem.

\begin{quotation}
\noindent
{\it In a gridworld, agent moves to the neighboring cell spending one unit of energy. 
The gridworld is sufficiently large so that agent never reaches the border.
Starting from the base located in the center of the gridworld with $N$ units of energy, an agent must travel visiting as many different cells as possible,  and the agent must go back to the base before consuming all the energy.} \\
\end{quotation}

\noindent
Try to imagine a land-rover in a planet like the Mars. The mission of the rover is to explore the
areas which have not yet explored so far with a limited energy charged when it started the base.\\


\noindent
{\bf Random walk as a base of comparison.}
First of all, the rover explors with a random walk. The rover starts from the base, and moves up, down, left or right at random. The rover was  given 100 units of fuel at the start. Since it's less likely to observe the rover will return to the base after a long journy, we observe the rover try to go as far as possible in the first half of the travel and try to return to a point as close as possible to the base. To be more specific, if it reached a point whose Manhattan distance from the start is more than 50, while if final point it reached was the point of Manhattan distance less than 50 from the start.\footnote{We want the value to be more demanding ones, e.g., 40 and 10, respectively, but we found it was too demanding.} What we found then is, none out of 10,000,000 trials never attain this target, and only one out of 100,000,000 trials fullfil this criteria, not a good journey though (maximum reached was 51 and retured to the point of 48).\\


\noindent
{\bf Reinforcement Learning.}
In a standard implementation of reinforcement learning, agent is given a reward only when it reaches to the goal. Hecne, as Driessens et al.~(2004) put it {\it "Using random exploration through the search space, rewards may simply never be encountered."} This might be a reason why usualy those proposed world to be explored includes obstacles, and agent is given a penalty when it touches an obstacle. In a sense, obstacles are not obstacle. Though the agent should avoid obstacles but at the same time those obstacles are good guides to lead the navigation. Our gridworld however has no border nor obstacle and includes only one goal to be reached, which make the search {\it a-needle-in-a-haystack-problem}.\\

\noindent
Our trick is, then (i) agent is given a reward at any cell it passes; (ii) reward is associated with the Manhattan distance from the starting point; (iii) the further away the agent goes, the more reward agent obtains during its first half of the travel and vice versa during the last half of the travel. \\

\noindent
Like the experiment with a random walk mentioned above, rover is given 100 units of fuel at the start. And what we observed was seven rovers after 300 episodes managed to return to the base after a journey. Further check, however, revealed the routes of all these seven rovers were just exploration close to the starting points. The main reason of this failure is 
{\it ``the Q-function only converges after each state has been visited multiple times,''} as Driessens et al.~(2004) pointed out. \\


\noindent
{\bf Genetic Algorithm with a heuristic.}
We have found so far the problem is not so easy. However, we know a heuristic to create such 
a journey starting from the base with the goal being returning again to the base 
at the time when it has spent all the the fuels. That is, the number of up and down should be same, and same goes for the number of right and left. So, chromosome should be four genes each corresponding to up, down, right, and left such that the number of these genes fulfill the condition above. Nevertheless it is not so simple to apply genetic algorithm to this problem, because usual operation of both {\it crossover} and {\it mutation} destruct the condition, or validity of the journey.\\

\noindent
So, we repair those broken chromosomes following Mitchell (2005) -- one of the traditional apploaches to the {\it Travelling Sales-person Problem}. The result was successful. See Figure 1.\\

\begin{figure}[h]
\begin{center}
\includegraphics[width=7.5cm,height=4.5cm]{rover-300.eps}
\caption{A successful journey from the base (0,0) to the base starting with 300 units of fuel. The length of the loop is 300 cells.}
\end{center}
\end{figure}

\noindent
{\bf Are we happy with this?}
Agents moves according to {\it chromosome} in genetic algorithm, and according to {\it policy} in reinforcement learning. As a result the behaviour is deterministic.
Agent behaves any trials afterwords as exactly similar as when it learned.
Can we call it a intelligence, however efficient the behavior might be?
The answer would be ``No,'' if our conceren is on intelligence rather than efficiency.\\

\noindent
{\bf A neural network approach toward an intelligent behavior.}
Then what we are planning is to controll an agent by spiking neurons with modifying its connection weights, from step to the next, during navigation.\\

\noindent
Following the model by Florian (2005), we will exploit here networks of stochastic leaky integrate-and-fire neurons, that evolve in discrete time $\delta t$ according to:
\begin{displaymath}
v_i(t)= v_i(t - \delta t)\exp (-\delta t/\tau_i) + \sum_j w_{ij}(t - \delta t)f_j(t - \delta t)
\end{displaymath}
where $v_i(t)$ is membrane potential of neuron-$i$ at time $t$, $\tau_i$ is a time constant of neuron-$i$, $w_{ij}$ is synaptic weight value from neuron-$j$ to neuron-$i$, and $f_j(t) = 1$ if neuron-$j$ fires at time $t$ otherwise 0.\\

\noindent
The neuron-$i$ fires stochastically with probability $\sigma(v_i (t))$

\begin{eqnarray*}
\sigma_{i}(v_i) = \left\{
\begin{array}{ll}\nonumber
\delta t/\tau_{\sigma} \exp(\beta_{\sigma}(v_i - \theta_i))& \hspace{.2in}\mbox{if the value is less than 1} \\
1                                                          & \hspace{.2in}\mbox{otherwise}      \\
\end{array}
\right.\\
\end{eqnarray*}

\noindent
If the neuron fires, the the membrane potential is reset to a reset potential $V_r$.\\

\noindent
The parameters of neurons are set here as follows: a time constant $\tau_i$ = 20ms, reset potential $V_r$ = 10 mV, threshold potential $\theta_i$ = 16 mV, exponential escape noise with $\tau_{\sigma}$ = 20 ms and $\beta_{\sigma}$ = 0.2 mV.\\

\noindent
We experiment here, among others, with a feedforward architecture with two senser neurons, input layer with 4 neurons, hidden layer with 8 neurons, output layer with 2 neurons. All neurons from one layer to the next layer are fully connected.
The synaptic weights were initialized with random values from -1 to 1 except for those to the output layer in which they are from 0 to 1, at the beginning of a run.\\

\noindent
Since we have no object, the activation of the sensor neurons were set at random from between 0 and 1. The sensor neurons fired Poisson spike trains, with a firing rate proportional to the activation, between 0 and 50 Hz.\\

\noindent
The motor activations $a(t)$ of the output neurons evolve according to the following equation with time constant $\tau_e$ = 2s. 
\begin{displaymath}
a(t) = a(t - \delta t)\exp(- \delta t/\tau_e) +(1-\exp (-1/\nu_e \tau_e))f(t)
\end{displaymath}
The factor of $f(t)$ is to normalize the activation to 1 when the neuron fires regularly with frequency $\nu_e$ = 25 Hz. Agent moves with its $x$ and $y$ coordinat being increment or decrement by these two mortor neurons. (Note that no more descrete gridworld.)\\

\noindent
Thus we can make agent explore the world anyway. The question is, how we modify $w_{ij}(t)$ such that the agent solves the benchmark at any ran with a different route. We hope we will be able to show some positive result in the conference.

\subsubsection*{Acknowledgment}
This paper is based on the talk I made on 20th April 2009 in the Seminar at the System Analysis Department of the Institute of Mathematics and Informatics, Vilnius, Lithuania. I thank for stimulating and creative disucssion at the seminor.


\subsubsection*{Reference}
\begin{description}
\item
Floreano, D., and J.~Urzelai (2000)
``Evolutionary robots with online self-organization and behavioral fitness.''
Neural Networks Vol. 13, pp.~431--434.

\item
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, pp.~2557--2564.

\item
Durr, P., C.~Mattiussi, A.~Soltoggio and  D.~Floreano (2008)
"Evolvability of Neuromodulated Learning for Robots."
Proceedings of ECSIS Symposium on Learning and Adaptive Behaviors for Robotic Systems, pp. 41--46.

\item
Mitchell, G.~G. (2005) 
"Validity Constraints and the TSP - GeneRepair of Genetic Algorithms." 
Proceedings of Artificial Intelligence and Applications pp. 306-311.

\item
Florian, R.~V. (2005)
"A reinforcement learning algorithm for spiking neural networks." 
Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, pp. 299--306. 


\item
Driessens, K.~and S.~Dzeroski (2004)
"Integrating Guidance into Relational Reinforcement Learning" 
Machine Learning, 57, pp.271-304,



\end{description}
\end{document}







