08 02 17

Page 1

AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 8, 2017 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 f ollowing Distributed Constraint Satisfaction Problem (DCSP), in which there are three variables/agents (A, B, and C), whose domains are reported below, and two constraints (A > B and B > C). A B C DA={1,2,3,4} DB={1,2,3} DC={2} > > 1) Consider the priority order A – B – C and solve the problem using the asynchronous backtracking algorithm. Assume that the agents activates in cyclic turns A – B – C – A – … and that, when an agent activates, it receives all the pending messages in the order in which they have been sent . Everything else being equal, agents select their values in increasing order. 2) Consider now the priority order C – B – A and solve the same problem, with the same algorithm and the same assumptions as above. 1) A possible computation is as follows.  A assigns 1 and sends ok?(A,1) to B  B receives ok?(A,1) from A, cannot assign any legal value, sends nogood({A,1}) to A, assigns 1, and sends ok?(B,1) to C  C receives ok?(B,1) from B, cannot assign any legal value, sends nogood({B,1}) to B, and…