04 03 15

Page 1

Politecnico di Milano AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS March 4th, 2015 LAST NAME AND FIRST NAME ROW COLUMN ID NUMBER (MATRICOLA)  The exam is composed of three stapled sheets printed on both sides.  This front page must be filled with last name, first name, ID number, position (row and column communicated by the instructor), and signature.  Exams without a completely filled front page or with missing sheets will not be considered.  Answers can be written only on these sheets. If you need more space, please write on the last page.  Exam is closed books (i.e., no books, notebooks, notes, … are allowed). Cell phones, bags, cases, and wallets are not allowed on the desk during the exam.  All the answers must be justified. SIGNATURE Question 1 (8 points). Consider a Markov Decision Process (MDP), where states are the free cells of an environment represented as a grid, the actions in each state can be moving North, West, South, and East, and the transition function executes the correct movement with p robability 0.8 and the two perpendicular movements with probability 0.1 each, for example moving North from a generic state: 0.8 0.10.1 All actions can be performed in all states, except in terminal states. If there is an obstacle in the direction the agent would have been taken, the agent stays in its current state (and the transition probabilities change accordingly). In the following, each state reports the current value of the utility as calculated after 4 iterations of the value iteration algorithm with =0.9 and with initial utilities set to 0. States a4 and b4 are terminal (no action can be performed). 0.37 0 0 0.66 0 0.83 0.31 0.51 +1 0 -1 a b c 1 432 (1) What are the rewards the states a4 and b4, r(a4) and r(b4), respectively? Why? (2) What can be said…