11 02 15

Pagina 1

Politecnico di Milano AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 11th, 2015 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 distributed constraint satisfaction problem (DCSP) represented graphically (all reported constraints are ≠): x1≠ x4 x2 x3≠ The domains of the variables are: D1={B,R}, D 2={G,B,R}, D 3={B,R}, D 4={G}. The priority order is (from highest to lowest priority): x1, x2, x3, x4. 1) Apply the asynchronous backtracking algorithm to solve the above DCSP and report the solution. Assume that the computation proceeds in rounds. At the first round, all agents compute their initial values and send messages. At the second round, all agents receive the messages sent at the previous round, compute, and send messag es. And so on. Everything else being equal, agents select values from their domains in the order reported above. 2) What is the content of the local_view data structure of agent x 3 at the end of the algorithm? 1) Only agents that are performing operations are shown for each round. First round x1: assigns x1=B and sends ok?(x1,B) to x2 and x4 x2: assigns x2=G and sends ok?(x2,G) to x4 x3:…