23 02 11 1

Pagina 1

Politecnico di Milano Facoltà di Ingegneria dell’Informazione AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 23rd, 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). In an extension of the basic Distributed Constraint Satisfaction Problem (DCSP) framework, each variable x belongs only to an agent, but an agent can have more variables. Variables of an agent can be invo lved either in local constraints (with variables that all belong to the same agent) or in external constraints (with at least a variable of another agent). The Asynchronous Backtracking algorithm can be modified in a natural way to account for multiple variables per agent. In particular, in CHECK-LOCAL-VIEW() procedure, values are selected for all the variables of the agent in such a way they satisfy all the local and external constraints of the agent. Moreover, only values of variables involved in external constraints are communicated. Consider three agents A, B, and C with variables a 1 and a2; b1, b2, and b3; and c1, respectively. Domains are D(a 1)=D(a2)={1,2,3}, D(b 1)=D(b2)=D(b3)={a,b,c,d}, and D(c 1)={ }. The constraints are the following ones: 1. a1 a2 2.…