02 02 11 1

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell‟Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 2nd, 2011 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 MDP, with =0.8. (Rewards are shown in the nodes representing the corresponding states, probabilities are shown on the corresponding arcs.) A 0 C 10 B 5 α 1-αα 1-α α 1-α a b Consider the value iteration algorithm to find the utilities of the states. 1) Starting with initial values u(A)=u(B)=u(C)=0, report the first two iteration s of the algorithm (assuming a generic ). 2) What are the values u(A), u(B), and u(C) to which the algorithm wi ll eventually converge when =0? And when =1? 3) For =1, which action (a or b) will the agent choose in state A? Will the chosen action bring the agent to the state with the largest reward? Why is the chosen action convenient for the agent? 1) Initial values: u(A)=u(B)=u(C)=0. First iteration: u(A) = 0 + 0.8·max{ ·0+(1- )·0, ·0+(1- )·0} = 0 u(B) = 5 + 0.8·{ ·0+(1- )·0} = 5 u(C) = 10 Second iteration: u(A) = 0 + 0.8·max{ ·5+(1- )·0, ·10+(1- )·0} = 8 u(B) = 5 + 0.8·{ ·0+(1- )·5} = 5 + 4(1- ) = 9-4 u(C) = 10 2) The value…