29 06 11

Pagina 1

Politecnico di Milano Scuola di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS June 29th, 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). A mobile software agent can migrate between two hosts, A and B, in order to collect information. Due to network instability, the action of moving from host A to host B succeeds with probability 0.8 (with probability 0.2, the agent stays in A). Similarly for the action of moving from host B to host A. The agent can also decide to stay at the current host. At every time step, the agent collects information from its current host. Information collected at host A has value 1, while information collected at host B has value 0.5. 1) Model the above setting as a Markov Decision Process (MDP). 2) Assuming γ=0.8, what is the optimal action for the agent at host A? 3) For what values of γ the optimal action at host A is different from that found in the previous point? Are these values legal? Why? 1) The graphical representation of the MDP model (with the usual notation for actions and immediate rewards) is: 2) Writing the system of Bellman equations: u(A) = 1 + 0.8·max{u(A),…