06 02 13

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 6th, 2013 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 environme nt with 5 locations (a, b, c, d, and e) : An agent has to follow the path a-b-d-c-d-e. In each location (except in location e, where there are no available actions), it can perform two actions: F (move forward toward the next location along the path) and S (stay in the current location). F succeeds wi th probability 0.8 and leaves the agent in the same location with probability 0.2, while S always succeeds. 1) Model the above situation as a Markov Decision Process (MDP), specifying the set of states, the set of possible actions for every state, the transition function, and a possible reward function. 2) Write the Bellman equations for the states representing location d. 3) Given the structure of the MDP defined in 1), how can states be ordered according to their utilities? (Note: you are not required to actually calculate utilities.) 1) Set of states: {a,b,bd,c,cd,e}. Note that the loca tion d is represented by two states in the MDP,…