05 07 10

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS July 5th, 2010 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 the following 10x10 grid environment. A robot operates in this environment. When in a cell, it can choose one of four actions: up, down, left, or right. When the robot selects one of these action s, it has a 0.7 chance of going one step in the desired direction and 0.1 chance of going in any of the other three directions. If it bumps into the outside wall, the agent does not actually move. There are four rewa rding cells, as shown in the figure. The reward of the other cells is 0. Suppose that the discount factor is γ=0.9 and that ut=0(s)=0 for all states s. Using the value iteration algorithm calculate the values of the 9 cells around th e cell with +10 reward after the first and the second iteration of the algorithm (t=1 and t=2). According to t he values at t=2, what is th e optimal policy for the robot in the cell immediately on the left of the cell with +10 reward? The value iteration algorithm updates the values of cells (states) s according to:…