01 02 10

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 1st, 2010 LAST NAME AND FIRST NAME ROW COLUMN ID NUMBER (MATRICOLA) • This front page of the three stapled sheets (printed on both sides) 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 Exercise 1 (7 points). Consider the following situation. A robot is in a location A. From there, it can go to locations B and C. From location B, it can go to location C. No other action is allowed. A movement of the robot has success with proba bility α and, with probability 1 – α, leav es t he robot in it s cu rrent location. The immediate reward for being in A is 0, for being in B is x, and for being in C is 10. 1) Model the above situation as a Markov decision problem. 2) One can guess that the larger x, the more convenient for the robot to go from A to B. Consi dering a discount factor γ = 1, find the minimum value of x (as a function of α) for which the best behavior of the robot in A is trying to reach B rather than trying to reach C. 3) One can guess that, if x is small, the larger α, the more conveni ent for the robot to go from A to C and, conversely, if x is large, t he larger α, the more convenient for the robot to go fr om A to B . Considering a discount factor γ = 1, find the minimum value of…