• CMPE 248 Winter 2006
• Homework Assignments

Homework Assignments

• Homework 2, due Feb 21, 2006. Electronic submission (tarball, and post pictures). You have a n x n minefield with n mines (start with n = 10), the mines are distributed at random. You have to go from corner (0,0) to the opposite corner (n-1, n-1); there is an extra state called "sink", aside from these n*n states. You have, at each state, 4 moves: 1, 2, 3, 4 (or right, up, left, down, or whatever - the order does not matter). If you move off the n x n board, you to to the sink. Once in the sink, you stay in the sink. If you are at position x,y and play "right", then with probability q (more on this later) you go to position x+1,y (similarly for the other directions), and with probability 1-q, you "blow up" and go to the sink. The probability q, of not blowing up, is computed as follows. Each mine j, at coordinates x_j, y_j, contributes to a probability of blowing up

  • 1 - q_j = exp (- sigma * (((x+1) - x_j)² + (y - y_j)²))

  where sigma is a "mine width factor" that we will trim for good pyrotechnical effect; I advise you to start with something like sigma = 0.7 or also sigma = 1.0. The overall probability of not blowing up is then given by
  • q = \prod_j q_j
  You must compute a strategy that reaches the goal with maximal probability, creating plots of:
  • The probability of blowing up at every square
  • The optimal move at every square.
  In particular, you should implement both the policy iteration, and the value iteration methods described in class, plotting the convergence of values in value iteration, and plotting the convergence of the deterministic policy. How many steps does the deterministic policy take to converge? What is the path length from (0,0) to (n-1,n-1) using this deterministic policy?

  You can use matlab, octave, scilab, or something else to do this homework; I recommend scilab as it seems to work quite well. See the Notes on Scilab for more information on scilab.

• Homework 1, due January 26, 2006, at the beginning of class. Do the following problems, from this writeup:

  • Problems 1, 2
  • Problem 3
  • Problems 4, 6
  • Problem 7 (parts 1, 2, 3, 4, not 5)
  • Problems 8, 9, 10, 11

  Read the homework policy. If you don't understand some problems, talk to me or to other students. If you still don't understand them, ask questions. Even asking in class is fine, if you know that neither you, nor several of your fellow students, is making progress on a problem. Each of the problems has a simple solution. If you find yourself writing pages and pages as a solution, then there is something wrong - there is a better way.