05 02 16

Pagina 1

Politecnico di Milano AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS February 5, 2016 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 (7 points). Consider the following situation in which three robots (1, 2, and 3) can move from their starting locations (si) to their goal locations (gi) only along one of their possible paths (Pi,j): g1 g3 s2 g2 s1 s3 P1,1 P2,1 P2,2 P3,1 P3,2 Each robot i must choose one of its paths Pi,j in such a way that the paths chosen by any two robots do not intersect. 1. Formulate the above situation as a Distributed Constraint Satisfaction Problem (DCSP), specifying agents (variables), domains, and constraints. 2. Solve the DCSP formulated above using the asynchronous backtracking algorithm . Assume that the priority order of the agents corresponds to the ir lexicographic order and that, everything else being equal, values are selected according to the lexicographic order. Show the trace of the execution of the algorithm when agents activate sequentially in turns, starting from the highest priority agent. 3. What is the content of the local_views of the agents at the end of the execution of the algorithm? 1. Agents…