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.

In this tutorial we will provide an overview of DCOPs, focusing on its algorithms and its applications. We will present an accessible and structure overview of the available optimal and suboptimal approaches to solve DCOPs. We will discuss recent extensions to the DCOP framework to capture agents acting in a dynamic environment and/or using continuous domains and objective functions. Finally, we will discuss what are the suitable applications that can be modeled and solved as a DCOP, and 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
  1. DCOP Extensions
    • Continuous DCOPs
    • Dynamic DCOPs
  2. Applications for Cooperative Multiagent Systems
    • Meetings Scheduling
    • Smart Device Scheduling in Smart Homes
  3. Challenges and Open Questions

Time and Venue

TBA

Extra Material

Contacts

  • Ferdinando Fioretto

    Syracuse University

    ffiorett@syr.edu
    Ferdinando Fioretto is an assistant professor at the Syracuse University. His research focuses on multiagent systems, data privacy, and discrete optimization. His dissertation was awarded “the best AI dissertation” from the Italian Association of Artificial Intelligence in 2017.
  • William Yeoh

    Washington University St. Luis

    wyeoh@wustl.edu
    William Yeoh is an assistant professor in the Computer Science and Engineering Department at Washington University in St. Louis. His research interests include multi-agent systems, distributed constraint reasoning, and planning with uncertainty. He is an NSF CAREER awardee and was named in IEEE’s 2015 AI’s 10-to-Watch list.