1 Gridworld [15 pts] Consider the following grid environment. Starting from any unshaded square, you can move up, down, left, or right. Actions are deterministic and always succeed [e.g. going left from state 16 goes to state 15) unless they will cause the agent to run into a wall. The thicker edges indicate walls, and attempting to move in the direction of a wall results in staying in the same square (e.g. going in any direction other than left from state 16 stays in 16). Taking any action from the green target square (no. 12) earns a reward of r9 (so r(12,a) = r9 Va) and ends the episode . Taking any action from the red square of death (no. 5) earns a reward of r, (so r(5,a) = 1",. Va) and ends the episode. Otherwise , from every other square , taking any action is associated with a reward rs E {1,{},+1} (even if the action results in the agent staying in the same square). Assume the discount factor 7:1,r9=+5,and r,=5unless otherwise specied (a) (3pts) Define the value of rs that would cause the optimal policy to return the shortest path to the green target square (no. 12). Using this rs, find the optimal value for each square. (b) (3pts) Lets refer to the value function derived in {a} as V012 and the policy as 11-9. Suppose we are now in a new gridworld where all the rewards (r3, 7'9, and Tr) have +2 added to them . Consider still following 7r of the original gridworld, what will the new values VH1?\" be in this 9 second gridworld