\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{rsfs}
\usepackage{graphicx}
\usepackage{color}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\newtheorem{algorithm}{Algorithm}
\newtheorem{excersise}{Experiment} 

\pagestyle{myheadings}
\markright{(2009 BSTU Semester Project)}
\thispagestyle{empty}

\begin{document}

\title{{\large (2009 Semester Project)}\\
Exploration in a gridworld which has a cliff}

\author{Akira Imada\\
\hspace*{1in}\\
Most recently renewed on}
\maketitle

\section{Introduction}
In this project, we study machine learning techniques such as Genetic Algorithm (GA), artificial Neural Network (NN), Reinforcement Learning (RL), and so on, by observing an artificial agent who travels a virtual world called a gridworld. The world has the point for the agent to start with, the point for the agent to aim as a goal, and dangerous cliff to which if the agent fall the agent will die.\\

\noindent
Usually we call ``{\it agent}" who are to learn to behave intelligently, and here, agent's aim is to reach the goal. You may, however, replace the term an ``agent'' with a ``dog,'' and the ``goal'' with the ``place where dog can find a sausage.'' That is, a dog learns how he/she reaches the sausage efficiently, or with a shortest path.

\section{The Cliff Walking Problem}
The gridworld those agents are going to explore is like a grid shown in Fig. 1. An example of a trace of agent is also shown in the figure.\\

\noindent
The size of the grid is $M \times N$. Agent starts at the leftmost cell at the bottom. We now denote it as $(1,1)$. The goal is the rightmost cell at the  bottom, that is, $(1,N)$.
The other cells at the bottom, that is, all the cells between $(1,2)$ and $(1,N-1)$ is the cliff. If agent enters the cliff, which means the agent falls into the cliff, then agent will die. So, the aim of the agent is to reach the goal alive.\\

\noindent
Agent can move only one cell at a time to the neighboring cell, that is, to up, down, right and left, unless the agent touches the border. When the agent touches the border, the action that makes the agent cross the border is not performed but it must remain stopped at the point waiting until the next action. For example, if the agent is at $(1,3)$ and the action is to {\it left}, then agent remains at that point,  and if the next action is to {\it up}, then it moves to $(1,4)$, or when the next action is {\it right} then agent moves to $(2,3)$.

\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm,height=5cm]{cliff.eps}
\end{center}
\caption{\it A gridworld with a cliff. Also shown an example of trace by an agent.}
\end{figure}

\subsection*{Or, try to begin your experiment with more simple gridworld.}
Maybe you start with much more simple gridworld -- with no cliff, obstacles like wall, nor border. A huge empty gridworld only with a point to start and the goal. Agent starts at the center of a huge gridworld, say 1000 $\times$ 1000 cells. Agents must spend one unit of energy to move to the next cell. You set the total energy when the agent starts, for example, 500 units. Then agent would never reach the border. Let us now represent one cell with coordinate. Agent starts at $(500,500)$ aiming the goal $(600,600)$ for example. Then agent should look for the shortest {\it Manhattan distance} to the goal point. (How many such route do you guess?)


\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=6.5cm]{empty-gridworld.eps}
\end{center}
\caption{\it An empty  gridworld. Also shown an example of a random walk by an agent. Note that this is just a center part of a huge gridworld.}
\end{figure}

\section{Experiments}
The result of the agent, successful or not, depends on the size of the gridworld. So experiments would be performed by changing the size of the gridworld -- from small one to the large one -- with $M$ and $N$ being increased, say, from 3 to 100.\\

\noindent
You may report the number of successful run in which agent reach the goal as a function of the size of gridworld.\\

\noindent
You start your simulation with agent who walk the gridworld at random (Random Walk). Then you choose at least one of the machine learning technique and study how efficient the technique you chose is.\\

\noindent
If you take only one technique, study it as deep as possible. If you take multiple techniques, you may compare them with each other as for how efficient each of techniques you chose.

\subsection{Random Walk}
Agent move one step upwards, downwards, to the right, or to the left, if the action is possible. If the movement is not possible due to the border of the gridworld, do nothing and decide the next action again at random. This would be repeated until the agent reaches the goal, or die by falling down in to the cliff. The maximum number of steps should be determined depending on the size of the gridworld. For example agent can move 1000 steps unless it dies during its travel.\\

\noindent
We now look at the result of a random walk agent in an empty huge gridworld mentioned above. See the Figure. 2.\\

\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=5cm,height=5cm]{trace-96-start.eps}
\includegraphics[width=5cm,height=5cm]{trace-96-end-new.eps}
\caption{In the grid-world of $96 \times 96$, starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no {\it a-priori} information. Left: A path chosen from 100 trials by random walk. Right: A route of the minimum Manhattan distance to the goal. (Obtained by GA).
Marginal area is omitted in both figures.}
\end{center}
\end{figure}

\noindent
Then try the gridworld with a cliff. Anyway, in both cases you will summarize your results as follows.


\begin{excersise}
(1) Run the algorithm by changing random number seed from run to run.
(2) Count the number of agents who succeeded by repeating the run, say, 200 times.
(3) Show an example of the route the successful agent follows. Or, also the route the agent failed.
\end{excersise}


\subsection{Genetic Algorithm}
Borrowing the idea from biological evolution, we can be solved certain types of problems by an algorithm which we call {\it Genetic Algorithm}. In this case we express the problem we want to solve by a vector which we call {\it chromosome}. Chromosome is made up a number of {\it genes}. At the beginning we create a population of, say 100, chromosomes at random. They are not good solutions at all because they are randomly created. But some are a little better than others. So we pick up two chromosomes such that better chromosomes are more likely to be chosen. Here, let's choose them at random from better half of the population. This is called {\it truncate selection}.\footnote{We have a couple of different type of selection such as {\it roulette-wheel-selection} and {\it tournament-selection}.} \\

\noindent
Let's call these two chromosomes parents. Then we create a child from these two parents by {\it crossover operation}. \\

\noindent
Standard crossover is what we call {\it one-point-crossover}. We cut two parent chromosome at a same location at random. That is, the location to be cut is chosen by creating a random integer from one to $N$ --- the total number of chromosome. Then we take the first part from one parent and second part from the other parent and unite the two parts. See the following Figure.\\

\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=5cm,height=2cm]{one-point-xover.eps}
\end{center}
\end{figure}
\noindent
Or, yet another crossover is called {\it uniform-crossover} where we choose genes one by one either from parents at random. See the following figure.
\begin{figure}[bhtp]
\begin{center}
   \includegraphics[width=5cm,height=2cm]{uniform-xover.eps}
\end{center}
\end{figure}

\noindent
Then by repeating this procedure (select two parent chromosomes and create one child chromosome), say 100 times, we create the next {\it generation}. The population of the next generation includes same number of chromosomes in the previous population. Thus we can evolve the first random population of chromosomes generation by generation. We can expect those chromosomes' performance becomes better and better gradually.\\

\noindent
We also give a {\it mutation} to introduce new genes. This is to avoid for individuals in the population to be trapped into a {\it local minimum}. The probability for mutation to occur is small --- typically {1/number-of-genes}.

\subsubsection*{Agent in GA behaves by following its chromosome}
What we assume here is an evolution in an agent's brain in advance the action. That is a population of  chromosomes in the brain will be evolved. Then after a convergence, the agent acts following the best chromosome.\\

\noindent
Our chromosome in this study of exploring gridworld is made up of 4 different genes move (i) up, (ii) down, (iii) to right
, and (iv) to left. See an example below.

\begin{figure}[h]
\begin{center}
\includegraphics[width=6cm,height=6.5cm]{robot-move.eps}
\caption{An example of a chromosome and the path represented by it.} 
\end{center}
\end{figure}

\subsubsection*{A GA implementation}
Assuming now the total energy when the agent starts is 500 units, as an example, all chromosome has 500 genes whose value is 1, 2, 3, or 4. Then (1) Create 100 such chromosomes at random. This is the initial population; (2) Evaluate fitness -- how good is the chromosome -- by the Manhattan distance when the route approaches to the goal with a closest distance. Note that the smaller the fitness, the better the chromosome; (3) Sort the population according to the fitness. With the best at the top and with the worst at the bottom; (4) Pick up two parent chromosomes randomly from the upper half of the population and create one child chromosome by uniform crossover; (5) Mutate the child chromosome by replacing the gene with 1, 2, 3, or 4 at random. This should be done by selecting the gene to be mutated with a probability of 1/500. Not all the genes; (6) Repeat (4) and (5) 100 times to create the next generation; (7) Record the average fitness and maximum fitness in each generation; (8) Stop the iteration when fitness of any chromosome becomes 0, which means the chromosome is successful, then stop the run. \\

\noindent
The following Figure is the maximum fitness versus iteration of such a run.


\begin{figure}[bhtp]
\begin{center}
\includegraphics[width=12cm,height=6cm]{evolution-96-new.eps}
\caption{Random walk evolved to be minimized by GA.}
\end{center}
\end{figure}


\subsection{Reinforcement Learning}
In Reinforcement Learning (RL), an agent takes one {\it state} at a time chosen from pre-defined all possible {\it states}. In each of those state, also all possible actions are given one by one with a probability of how likely the action will be made.\\

\noindent
It might be helpful to understand this if we imagine that we sometimes in a {\it state of being happy} or in a {\it state of being sad}. Then assume now we see a cat. Also assume the possible actions will be (i) hug the cat; (ii) neglect; (iii) kick the cat. When we are in a happy state, most likely action will be hug the cat, while when we are in a state of sad, we might neglect the cat or might kick the cat. 

\subsubsection*{Agent in RL behaves by following its policy}
\noindent
Thus, RL is defined with a set of {\it states} and a set of {\it actions}. Then, we have a table called {\it policy} in which each of all possible pairs of state and action corresponds to its probability. Starting with a random assignment of this probability at the beginning, the the policy will be renewed according to the agent's experience.

\begin{table}[h]
\begin{center}
\caption{{\it A toy example of policy. Agent action depends on its state.}}
\begin{tabular}{l c c c}
\hspace*{.1in} \\ \hline\hline
\hspace*{.1in}  & hug and caress      & neglect       & kick           \\ \hline
Happy           & 0.80                & 0.15          & 0.05           \\
Normal          & 0.20                & 0.70          & 0.10           \\
Unhappy         & 0.10                & 0.50          & 0.40           \\ \hline\hline
\end{tabular} 
\end{center}
\end{table}

\subsubsection*{Q-learning}
States of our current study of agent's exploration in a gridworld is the cell in which the agent is located. So we have $M \times N$ different states. The possible actions is either up, down, right and left.\\

\noindent
To choose the action in one state, we employ what we call $\epsilon$-greedy strategy. That is, we choose an action at random with probability $\epsilon$ (a pre-fixed small value such as 0.1) and the action with the highest value in the Q-table with probability $1-\epsilon$. \\

\noindent
One method of renewing the policy table is called {\it Q-learning}. Assume now the state of the agent at time $t$ is $s_t$ and the action policy table gives is $a_t$.

\begin{displaymath}
Q(s_t, a_t) = Q(s_t, a_t) + \alpha \{r_{t+1} + \gamma \max_a Q(s_{t+1}, a) - Q(s_t, a_t)\},
\end{displaymath}

\noindent
where $\max_a Q(s_{t+1}, a)$ is the action with the highest value in the state of $s_{t+1}$ in the Q-table, $\alpha$ is called {\it learning ratio} which determines how this renewal influence the over all learning, and $\gamma$ is called {\it discount rate} which determines the importance of the reward received in the future. Anyway both value takes a value between 0 and 1. Try your experiment by changing these two parameters. Reward at time $t$ is expressed by $r_t$. In our case, $r-t$ is -10 when the agent tried to cross border, -500 when the agent falls into the cliff, +500 when agents reaches to the goal, and all other empty cell gives the agent -1.\\

\noindent
Note that $s_{t+1}$ is automatically determined if an action $a_t$ is performed at the state $s_t$. For example, if the action is {\it up} at the state of $(4,3)$, then the next state will be $(4,4)$.\\ 

\noindent
This process of selection and update the Q-table is repeated until the goal state is reached. This is called {\it epoch}. This epoch is repeated from one agent to the next until the Q-table will not be changed any more, that is, until the Q-table becomes stable.


\clearpage
\subsection{Finite State Machine (FSM)}
We human being has a feeling which changes from one moment to the next. And our action is strongly dependent on the feeling, and the feeling will change according to the action. Let's remind of the example of {\it kick-or-hug-a-kitty} in the previous section.
When you are in a feeling of very unhappy, you might kick a cat if you see it and then the action might change your feeling happy more or less.\\  

\noindent
We might call this feeling a state of mind. We now simply call it a {\it STATE}. It changes influenced by environment. That is, it changes according to {\it INPUT} from sensor like eyes, and then we make some {\it ACTION} and change the {\it STATE}. \\

\noindent
Thus, in the same way, 
FSM is defined as a three-tuple ${state, input, action}.$ That is, starting with a specific state, an input changes the  state and output an action. This is one step.  This procedure of 
\begin{itemize}
\setlength{\itemsep}{0pt}
\item[(1)] transition of state according to input; 
\item[(2)] output an action;
\item[(3)] change the state.
\end{itemize}
are repeated, and produce some behavior of the FSM.\\

\noindent
In other words, FSM is defined by a {\it transition table}:

\begin{table}[h]
\begin{center}
\caption{{\it A toy example of transition table of FSM.}}

\begin{tabular}{l c c c}
\hspace*{.1in} \\ \hline\hline
State           & input             & action      & next state      \\ \hline
\hspace*{.1in}  & cat               & hug         & Normal          \\
Happy           & stone             & neglect     & Happy           \\
\hspace*{.1in}  & vodka             & drink       & Happy           \\ \hline
\hspace*{.1in}  & cat               & hug         & Normal          \\
Normal          & stone             & neglect     & Happy           \\
\hspace*{.1in}  & vodka             & drink       & Happy           \\ \hline
\hspace*{.1in}  & cat               & hug         & Normal          \\
Unhappy         & stone             & neglect     & Happy           \\
\hspace*{.1in}  & vodka             & drink       & Happy           \\ \hline
\end{tabular} 
\end{center}
\end{table}

\noindent
Different people have a different table. For example, some people never drink vodka, or some peaple drink vodka when happy and become unhappy remembering a sad past.\\

\noindent
Or, more practical example. Imagine a vending machine. For example, a machine which automatically sell Coke, Fanta, and Sprite upon customer's request. State is Waiting, Having accepted money. Output is giving Coke, Fanta, or Sprite. Assuming customers put exact amount of monye so that no return manye, for the sake of simplicity.\\


\noindent
{\bf Diagram representaion of FSM}\\

\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=3cm]{fsa.eps}
\caption{An exapmle of simplest FSM.}
\end{center}
\end{figure}


\noindent
{\bf A GA implementation of a FSM}\\

\begin{table}[h]
\begin{center}
\caption{An example of how to encode transition table into chromosome.}
\hspace*{1in}\\
\begin{tabular}{c c c c} \hline\hline
Old State & Input & New State & Action \\ \hline\hline
00        & 0     & 00        &01 \\
00        & 1     & 01        &11 \\ \hline
01        & 0     & 01        &01 \\ 
01        & 1     & 11        &11 \\ \hline
10        & 0     & 10        &10 \\
10        & 1     & 11        &11 \\ \hline
11        & 0     & 10        &10 \\
11        & 1     & 10        &11 \\ \hline\hline
\end{tabular} 
\end{center}
\end{table}

\noindent
The first 2 columns are fixed (automatic depending on the number of state and imput). The 3rd and 4th columns are given at random at the beginning. Thus we create 100 stupid FSM's at the beginning
Then express them with a chromosome. The chromosom of the FSM in the above example can be:

\begin{center}
(00010111010111111010111110101011).
\end{center}

\noindent
Then using GA and after lots of generations it converges one clever FSM.
 



\begin{figure}[h]
\begin{center}
\includegraphics[width=12cm,height=3cm]{fsa-2.eps}
\caption{Yet another example of FSM. How do you think its behavior?}
\end{center}
\end{figure}


\begin{figure}[h]
\begin{center}
\includegraphics[width=7cm,height=6cm]{fsa-success.eps}
\caption{A result of emerging FSM after evolution}
\end{center}
\end{figure}



            
 






\clearpage
\subsection{Ant Colony Algorithm}
I have never seen, that artificial ant colony challenge this cliff walking problem. Hence if your simulation with artificial ant colony successfully, you may be the first in the world.\\

\noindent
Ant Colony Algorithm is ... 

\subsection{Neural Network}
In order to challenge agent with Neural Network might be very tough. So, just an observation of the agent moving with neural networks but before learning procedure in the gridworld with out border, obstacle, nor cliff  -- a huge empty gridworld starting from the center of the world.

\subsubsection{McCulloh-Pits Neurons with Sigmoid}

\subsubsection{Spiking Neurons}

{\bf Integrate \& Fire Model}\\
Amang others, we use an {\it Integrate-and-Fire} model of spiking neurons following Florian (2007) in which dynamics of neurons is according to:
\begin{displaymath}
u_i(t) = u_r + \{u_i(t - \delta t) - u_r\} \exp (- \delta t/ \tau) + \sum_j w_{ij}f_j (t - \delta t),
\end{displaymath}
assuming we simulate the dynamics in discrete time with a time step $\delta t$ for the sake of simplicity, where $u_i(t)$ is membrane potential of the $i$-th neuron at time step $t$, $u_r$ is resting potential,  $\tau$ is decay time constant, and $f_j(t)$ is 1 if $j$-th neuron has fired at time step $t$ or 0 otherwise. When membrane potential exceeds firing threshold $\theta$ it is reset to the reset potential which is equal to the resting potential $u_r$ here.\footnote{Florian's setting is $u_r$ = -70 mV, $\theta$ = -54 mV, $\tau$ = 20 ms and $\delta t$ = 1 ms.}\\


\begin{thebibliography}{99}
\bibitem{sutt}
R.~S.~Sutton and A~G.~Barto (2005)
{\it ``Reinforcement Learning: An Introduction.''}
A Bradford Book. The MIT Press. pp. 185-186
\end{thebibliography}

\end{document}

