17 09 10

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS September 17th, 2010 LAST NAME AND FIRST NAME ROW COLUMN ID NUMBER (MATRICOLA) x The exam is composed of three stapled sheets printed on both sides. x This front page must be filled with last name, first name, ID number, position (row and column communicated by the instructor), and signature. x Exams without a completely filled front page or with missing sheets will not be considered. x Answers can be written only on these sheets. If you need more space, please write on the last page. x 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. x All the answers must be justified. SIGNATURE Question 1 (7 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 th ese actions, 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, there is a penalty of 1 (namely, a reward of –1) and the agent does not actually mo ve. There are four rewarding cells (apart from the walls), as shown in the figure. The reward of the other cells is 0. Draw the corresponding Markov Decision Problem when considering o nly two actions: ‘right’ from the cell A and ‘left’ from the cell B. Comment on what the states of the MDP represent with respect to the environment. The MDP is: +100 0 0 0 -1 0 0 0.1 0.7 0.1 0.1 0.7 0.1 0.1 0.1 A state in the MDP generally represent a cell in the environment. However, there are two states (shown in the dotted box) for…