Utility and Decisions


Due Thursday March 6 in class

This homework should be completed individually.

What to submit: Submit a hard copy of your assignment in class.

Decision Networks

Exercise 16.11 parts (a)-(d) (not (e)) from Russell and Norvig AI book (4 points).

Sequential Decision Problems

Exercise 17.1 from Russell and Norvig AI book (2 points).

Value Iteration

Consider the following 4 x 5 grid world:

-0.04 -0.04 -0.04 -0.04 -0.04
-0.04 -0.04 -0.04 +1.00 -0.04
-0.04 wall -0.04 -1.00 -0.04
-0.04 -0.04 -0.04 -0.04 -0.04

The two terminal states have a reward of +1 and -1, as shown. All other states have a reward of -0.04. An agent can perform four actions: moving Up, Down, Left, or Right from any state. In each case, the intended action of the agent occurs with probability 0.8 but with probability 0.2 the agent moves at a right angle to the intended direction. For example, if the intended action were Up, the agent would move Up with probability 0.8, Right with probability 0.1, and Left with probability 0.1. Colliding with a wall (or edge of the world) results in no movement. (This setup is identical to figure 17.1 in the book, but with an extra row and column).

Implement value iteration as discussed in section 17.2 to compute the utilities of the states in this 4 x 5 world.
(6 points)

For this problem, submit a hard copy (printout) of the utilities and a hard copy of your code. There is no need to submit anything online.