Teams of agents often have to coordinate their decisions in a distributed manner to achieve both individual and shared goals. Examples include service-oriented computing, sensor network problems, and smart devices coordination homes problems. The resulting Distributed Constraint Optimization Problem (DCOP) is NP-hard to solve, and the multi-agent coordination process non-trivial.

This tutorial is composed of two parts and will provide an overview of DCOPs, focusing on its algorithms and its applications to the Internet-of-Things (IoT).
In the first part, we will present an accessible and structured overview of the available optimal and suboptimal approaches to solving DCOPs. We will discuss recent extensions to the DCOP framework to capture agents acting in a dynamic environment and/or using asymmetric costs/rewards.
In the second part, we will review the application of DCOP methods that are suitable for the IoT context, illustrate a case study on how to model a real smart home, and, finally, show how to program and deploy DCOP algorithms on a real IoT environment composed of Raspberry PIs.
The tutorial will conclude with the most recurrent challenges and open questions.

Syllabus

  1. Preliminaries
    • CSP and WCSP
    • Multiagent Systems
    • DCOP
    • Overview of Agents Interaction Graphs
  2. DCOP Algorithms
    • Overview and Categorization
    • Introduction to Search-based Algorithms
      • SyncBB
      • DSA and MGM
    • Introduction to Inference-based Algorithms
      • DPOP
    • Critical Overview of DCOP Algorithms
  3. DCOP Extensions
    • Asymmetric DCOP
    • Dynamic DCOP
  4. Applications for Cooperative Multiagent Systems
    • Meetings Scheduling
    • Traffic Flow Control
    • Smart Device Scheduling in Smart Homes
  1. Hands on PyDCOP I
    • Install VirtualBox
    • Import the pyDCOP Virtual Machine
    • Modeling a graph coloring problem
    • Solving a DCOP
    • Analysing results
    • Web UI see here
  2. Hands on PyDCOP II
    • Implementing DSA
    • Use DSA to solve a DCOP
  3. Hands on PyDCOP III
    • Modeling a smart home scenario : SECP
    • Running SECP on several machines
    • Distributing SECP
  4. Hands on PyDCOP IV
    • Repairing distributions

Time and Venue

Monday, May 13    9:00 AM - 12:30 PM
Room: MB 3.430

Extra Material

Contacts