(2009 Semester Project)

Exploration in a gridworld which has a cliff

Akira Imada

Most recently renewed on

October 18, 2010

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

Usually we call “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.

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

The size of the grid is M × 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.

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 left, then agent remains at that point, and if the next action is to up, then it moves to (1, 4), or when the next action is right then agent moves to (2, 3).

Figure 1: A gridworld with a cliff. Also shown an example of trace by an agent.

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 × 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 Manhattan distance to the goal point. (How many such route do you guess?)

Figure 2: 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.

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

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

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.

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.

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

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

Figure 3: In the grid-world of 96×96, starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no 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.

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

Experiment 1 (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.

3.2 Genetic Algorithm

Borrowing the idea from biological evolution, we can be solved certain types of problems by an algorithm which we call Genetic Algorithm. In this case we express the problem we want to solve by a vector which we call chromosome. Chromosome is made up a number of 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 truncate selection.^{1}

Let’s call these two chromosomes parents. Then we create a child from these two parents by crossover operation.

Standard crossover is what we call 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.

Or, yet another crossover is called uniform-crossover where we choose genes one by one either from parents at random. See the following figure.

1We have a couple of different type of selection such as roulette-wheel-selection and tournamentselection.

Then by repeating this procedure (select two parent chromosomes and create one child chromosome), say 100 times, we create the next 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.

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

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.

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.

Figure 4: An example of a chromosome and the path represented by it.

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.

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

Figure 5: Random walk evolved to be minimized by GA.

3.3 Reinforcement Learning

In Reinforcement Learning (RL), an agent takes one state at a time chosen from predefined all possible 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.

It might be helpful to understand this if we imagine that we sometimes in a state of being happy or in a 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.

Agent in RL behaves by following its policy

Thus, RL is defined with a set of states and a set of actions. Then, we have a table called 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.

Table 1: A toy example of policy. Agent action depends on its state.

hug and caress neglect kick
Happy  0.80  0.15 0.05
Normal  0.20  0.70 0.10
Unhappy  0.10  0.50 0.40

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 × N different states. The possible actions is either up, down, right and left.

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

One method of renewing the policy table is called Q-learning. Assume now the state of the agent at time t is s_{t} and the action policy table gives is a_{t}.

Q(s_{t}, a_{t}) = Q(s_{t}, a_{t}) + α{r_{t+1} + γ max_{a} Q(s_{t+1}, a) − Q(s_{t}, a_{t})},

where max_{a} Q(s_{t+1}, a) is the action with the highest value in the state of s_{t+1} in the Qtable, α is called learning ratio which determines how this renewal influence the over all learning, and γ is called 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.

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 up at the state of (4, 3), then the next state will be (4, 4).

This process of selection and update the Q-table is repeated until the goal state is reached. This is called 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.

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

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

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

(1) transition of state according to input;

(2) output an action;

(3) change the state.

are repeated, and produce some behavior of the FSM.

In other words, FSM is defined by a transition table:

Table 2: A toy example of transition table of FSM.

State  input action next state
cat hug Normal
Happy  stone neglect Happy
vodka drink  Happy
cat hug Normal
Normal stone neglect Happy
vodka drink  Happy
cat hug Normal
Unhappy stone neglect Happy
vodka drink  Happy

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.

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.

Diagram representaion of FSM

Figure 6: An exapmle of simplest FSM.

A GA implementation of a FSM

Table 3: An example of how to encode transition table into chromosome.

Old State Input New State Action
00  0  00  01
00  1  01  11
01  0  01  01
01  1  11  11
10  0  10  10
10  1  11  11
11  0  10  10
11  1  10  11

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:

(00010111010111111010111110101011).

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

Figure 7: Yet another example of FSM. How do you think its behavior?

Figure 8: A result of emerging FSM after evolution

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

Ant Colony Algorithm is ...

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

3.6.1 McCulloh-Pits Neurons with Sigmoid

3.6.2 Spiking Neurons

Integrate & Fire Model Amang others, we use an Integrate-and-Fire model of spiking neurons following Florian (2007) in which dynamics of neurons is according to:

u_{i}(t) = u_{r} + {u_{i}(t − δt) − u_{r}} exp(−δt/τ) + ∑_{j} w_{ij}f_{j}(t − δt),

assuming we simulate the dynamics in discrete time with a time step δ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, τ 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 θ it is reset to the reset potential which is equal to the resting potential u_{r} here.^{2}

References

[1] R. S. Sutton and A G. Barto (2005) “Reinforcement Learning: An Introduction.” A Bradford Book. The MIT Press. pp. 185-186

2Florian’s setting is u_{r} = -70 mV, θ = -54 mV, τ = 20 ms and δt = 1 ms.