CSE 151 Introduction to Artificial Intelligence
Programming Assignment 2

Markov Decision Processes in the Grid world

Due date is specified in the referencing page.

RULES:
- You will be responsible for any updates to the assignment
that are posted to the discussion board, so please check it
regularly.
- The programs must be written in Matlab
- Programs must be submitted using the turnin procedure by 11:59pm on the due date
- You may work in groups of two or three
- Turn in a writeup and all the source files (see what to turn in below)
- Make sure to comment your code!  This means have comments
describing each function as well as comments throughout the
code. 

In this assignment, you will begin constructing an
infrastructure for reinforcement learning methods, as well
as implement the value iteration and policy iteration algorithms.

Infrastructure:  The Grid World

We will provide you with the function "read_grid", which
will do the boring stuff of reading in a grid world
description. This constructs the basic framework for the grid world.
"read_grid"  takes as parameters the number of rows and
columns and the names of 4 files which describe the world.
(This is clunky, but it is easier than starting from scratch).
It reads the grid specified in the files.

NOTE:  We will NOT be using the same labeling convention as
the book.  We're going to use a row, column representation
so that it matches up with matlab.  The top left corner is
1, 1 and the bottom right corner is rows, columns.

Specifically,
function grid_world = read_grid(rows, columns, obstacles_file, terminals_file, rewards_file, moves_file)

rows: the number of rows in the grid world
columns: the number of columns in the grid world
obstacles file: File containing row, column coordinates for the obstacles in the grid
row column
.
.
.
row column

terminals_file: File containing x, y coordinates for the terminal squares in the grid
row column
.
.
.
row column

rewards_file: The reward for each square (state) of the grid world
reward(1, 1) reward(1, 2) ....reward(1, columns)
.
.
.
reward(rows, 1) reward(rows, 2) ... reward(rows, columns)

moves_file: We'll use the same actions in the book
(i.e. North, South, East, West) with a probabilistic move
formulation.  The moves file specifies the probability of
moving in each of the four directions, given that the agent
has chosen to go in a given direction.  There should be one
line for each of (N, S, E, W) and each line should consist
of the following:
<label>: Either N, S, E or W
<pN>: Probability of moving North
<pS>: probability of moving South
<pE>: probability of moving East
<pW>: probability of moving West

A line is then:
<label> <pN> <pS> <pE> <pW>

Make sure you get this order right.

Given this specification, the following would be specified
for the grid world in the book in Figure 17.1, pg. 614:

rows: 3
columns: 4

obstacles file:
2 2

terminals file:
1 4
2 4

rewards_file:
-.04 -.04 -.04 1
-.04 0 -.04 -1
-.04 -.04 -.04

moves_file:
N 0.8 0.0 0.1 0.1
S 0.0 0.8 0.1 0.1
E 0.1 0.1 0.8 0.0
W 0.1 0.1 0.0 0.8

Your job *******************************
Part 1: Value iteration.

Implement the value-iteration algorithm shown in the book in
Figure 17.4.  Call the function "value_iteration".  The
function should take three parameters, the first should be the
output from the read_grid function, the second is the
epsilon, the third one is the gamma (discount factor).
For example, a call might look like:

value_iteration(read_grid(...), .1, 0.999);

The output from this function should be a matrix that has
the utility of all of the states.

Part 2:  Visualizing the utility function

Figure 7.2 shows a nice visual representation of the choices
that the agent is making.  We're going to do the same thing
(though simpler).  Write a function called
display_agent_choice that takes as input the output of the
value_iteration algorithm, and grid_world information returned
by read_grid(...), and outputs a matrix of N, S, E,
w, T (terminal) and O (obstacle) corresponding to the
direction the agent should take, given the learned utility
function.  For example, the call:

display_agent_choice( value_iteration(read_grid(...), .1, 0.999),
read_grid(...));

would return a matrix that looks like this (if the answer were 17.2a)
E E E T
N O N T
N W W W

Part 3: Investigating your results

Make a plot of your algorithm's progress similar to Figure
17.5(a). Note your curves may be somewhat different, and not
all states are graphed in Figure 17.5. (the function "plot"
may be helpful for this). Also, try to reproduce 17.6.

Do some states converge faster than others?
What happens as we vary the discount factor?
Make sure to explain any interesting behavior you observe in the graphs.

Reproduce the results shown in Figure 17.2(b). Can you find
any other places where the optimal policy changes?

Part 4: Implement the policy iteration algorithm shown in
Figure 17.7. You may use standard linear algebra methods for
the policy evaluation routine, or you may implement the
modified policy iteration using the modified Bellman
update shown on page 625. You may find this approach simpler
given that you have already implemented the standard Bellman
updates for value iteration.

Part 5: Evaluate your algorithm using plots similar to those
from Part 2. I.e., make a plot of your algorithm's progress
similar to Figure 17.5(a). Note your curves may be somewhat
different, and not all states are graphed in Figure
17.5. (the function "plot" may be helpful for this). Also,
try to reproduce 17.6.

Does policy iteration behave similarly to value iteration?
Does it converge faster or slower? What happens as we vary
the discount factor?

Make sure to explain any interesting behavior you observe in
the graphs.

Part 6: Now use "newReward.txt" and "newTerminals.txt", and 
apply value-iteration and policy iteration algorithms again.

Explain/Comment on any interesting things you observed.


What to turn in:
- A tar file with...
- All of your commented matlab code.
- A text writeup of about 4-5 pages (be as concise as
possible) in NIPS format which should include:
  - *** Answers to the questions in Parts 3, 5 and 6.
  - Your figures from parts 3 (replicating 17.5(a),17.6 and
    17.2(b)) and the figures from part 5.
  - A very brief overview of the code
  - Any special features added
  - A separate paragraph by each team member stating:
    what that team member contributed to the project.
    what that team member learned from the project.