CSE 151 Introduction to Artificial Intelligence
Programming Assignment 2

Reinforcement learning in the Grid world

Due date to be specified.

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

Part 1:  The Grid World

For the first part of the assignment, you will be constructing the basic framework for the grid world.  Write a function called "read_grid" that takes the name of 4 files and the number of rows and columns and reads the grid specified in the files (you may find the read_bn_file.m from last assignment useful for writing this function). 

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 talked about at the bottom of 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


Part 2: Learning in the Grid world

Implement the value-iteration algorithm shown in the book in Figure 17.4.  Call the function "value_iteration".  The function should take two parameters, the first should be the output from the read_grid function and the second is the epsilon.  For example, a call might look like:

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

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

Part 3:  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) with our answer from part 2.  Write a function called display_agent_choice that takes as input the output of the value_iteration algorithm 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));

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 4: Investigating your results

Make a plot of your algorithm's progress similar to Figure 17.5. 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)

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.

Do problem 17.7 in the book.  For each of the reward thresholds that you find (including the ones already shown in the book), show the output of the display_agent_choice algorithm on one example.



What to turn in:
- A tar file with...
- All of your commented matlab code.
- A text writeup less than 4 pages long (be as concise as possible) which should include:
  - *** Answers to the questions in Part 4.
  - 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.