08 02 12 1

Page 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 8th, 2012 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 an environment with two locations, A and B (with rewards as shown): A 10 B 5 and three possible actions: - Action a: move from A to B with probability 0.6 and stay in A with probability 0.4 - Action b: move from B to A with probability 0.9 and stay in B with probability 0.1 - Action c: stay in B with probability 1. 1) Model the above situation as a Markov Decision Process (MDP), specif ying the set of states, the set of possible actions for every state, the transition function, and the reward function. 2) Calculate the best action that the agent should perform when in location B (consider =0.5). 3) Now assume that two agents are independently acting in th e above environment and that their actions are perfor med simultaneously. Model the situation as a new single MDP, specifying the set of states, the set of possible actions for every state, the transition function ( only for the first state of the MDP, according to the alphanumerical order), and the reward fun ction…