Tutorial on Multi-Agent Distributed Constrained Optimization
at AAMAS 2022, the 21st International Conference on Autonomous Agents and Multiagent Systems
Zoom link

Table of Contents

1 Short description

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. Such a problem can be formalized and solved in different ways, but in general the multi-agent coordination process is non-trivial and NP-hard to solve.

In this Tutorial on Multi-Agent Distributed Constrained Optimization we will discuss two fundamental approaches that have been proposed in the Multi-Agent Systems (MAS) literature to tackle coordination problems, one based on Distributed Constrained Optimization Problems (DCOPs) and one based on Coalition Formation (CF).

In the first part, we will present an accessible and structured overview of the core concepts and models about DCOPs. We will also expound the available optimal and suboptimal approaches to solve DCOPs.

In the second part, we will discuss a core concept used to model MAS, i.e., Characteristic Function Games (CFGs), and which optimal and approximated approaches are available to form coalitions in both unconstrained and constrained CFGs. We will conclude this part by establishing an interesting link between the first and the second part, showing how Constrained Optimization Problems (COPs) can also be used to solve CF problems.

Finally, we will invite the attendance to model some sample problems coming from real applications, and discuss the relevant solutions methods. Some code and executable examples, from the python library pyDCOP, will be overviewed. The tutorial will conclude with the most recurrent challenges and open questions.

2 Outline

The Tutorial on Multi-Agent Distributed Constrained Optimization is expected to be a half-day tutorial alternates both theoretical and practical concepts on DCOP models, algorithms and applications. Some time is devoted to apply these concepts on sample applications using a python library.

This tutorial is planned to be mostly virtual, but can be hybrid. Being used to teach this tutorial for the past few years (especially during pandemic situations), the presenters are ready to run the event in a full virtual mode.

The overall programme is as follows:

  1. Introduction and Motivations
  2. Theory [2h]
    1. Distributed Constraint Optimization
      • Motivating Examples
      • Preliminaries
      • DCOP Model(s)
      • DCOP Algorithms
    2. Coalition Formation on MAS
      • Characteristic Function Games (CFGs)
      • Coalition Structure Generation (CSG)
  3. Practice [1h]
    1. Real-World Applications
      • Self-configuration of IoT Devices
      • Observation Scheduling in Multi-Owner Constellations
      • Shared Mobility
      • Collective Energy Purchasing
    2. Programming examples with pyDCOP
  4. Conclusion and Wrap-up

The practical session relies on an Open Source library that is available at https://github.com/Orange-OpenSource/ pyDCOP.

3 Contents

The slides presented during the tutorial are available here

Full online documentation for pyDCOP is available here : https://pydcop.readthedocs.io

4 Audience

We expect an heterogeneous audience interested in applying artificial agent and multiagent techniques to practical problems, with a focus on distributed optimization.

The first part can be attended by anyone familiar with constraint-based reasoning and multi-agent systems. Programming (e.g. Python) and problem modeling (constraint based modeling, linear programming, optimization) skills are basic requirements to follow the practical second part.

For many year DCOP topic has been part of summer school and tutorial session of main AI and multi-agent systems conferences (IJCAI, ECAI, AAMAS). Beside, the OPTMAS-DCR workshop series also attract AAMAS attendants since 2010. We add here a more « practical » dimension to the topics by applying such techniques to the practical problems. We are thus confident about the attractiveness of our tutorial for the AAMAS audience.

5 Organizers

Gauthier Picard

Gauthier Picard received a Ph.D. degree in Computer Science from the University of Toulouse in 2004, and the Habilitation degree in Computer Science from the University of Saint-Etienne in 2014. He was full professor in Computer Science at MINES Saint-Etienne and a full researcher at Laboratoire Hubert Curien UMR CNRS 5516. Since 2020, he is Senior Research Fellow at ONERA, The French Aerospace Lab. His research focuses on cooperation and adaptation in multi-agent systems and distributed optimization with applications to aircraft design, ambient intelligence, and satellite constellation operations, and unmanned automated fleet operations.

He has been in charge of the following organization activities: SASO (2016, PC Chair), SASO (2015, WS Chair), JFSMA (2015, Organization Chair), SASO (2014, Doctoral Consortium Chair), SASO (2012, Organization Chair), WI-IAT (2011, Demo Chair), ESAW'09 (2008-2009, Chair). He has also previously been member of the organization committees of the following events: ESAW (2004), JFSMA (2007), Web Intelligence Summer School (2009), EASSS (2010), MALLOW (2010), WI-IAT (2011).

Gauthier Picard teaches Artificial Intelligence, Multi-Agent Systems and DCOPs for Master-level students for more than 15 years, in different institutions and schools (Université de Lyon, Université de Toulouse, Ecole des Mines de Saint-Etienne). He has also coordinated the International Master Track on Cyber-Physical and Social System. Some sample slides and pratical works are available online, on DCSP and DCOP, Programming DCSP with Jason or Self-organization in Multi-Agent Systems. Finally, he presented tutorials on DCOPs at several conferences and summer schools (AAMAS'18, EASSS'18, AAMAS'19, PFIA'19, ECAI'20, PFIA'20).

Filippo Bistaffa

Filippo Bistaffa received the Ph.D. (Doctor Europæus) in Computer Science from the University of Verona in 2016. He is currently a Post-Doctoral Research Fellow (former Marie Skłodowska-Curie Fellow) at the Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain. His research interests comprise combinatorial optimization problems for realistic applications (such as shared mobility and team formation) and GPU computing.

Filippo Bistaffa has been member of the Program Committee of the following: international AI conferences and workshops: AAAI (since 2017), AAMAS (since 2019), IJCAI (SPC, since 2021), ECAI (since 2018), GECCO (since 2019), EuMAS (since 2019), OPTMAS-DCR (now OptLearnMAS, since 2013).

Since 2019, Filippo Bistaffa teaches a tutorial on "Constrained Optimisation for Multi-Agent Systems": Advanced Course on AI (ACAI) Summer School, Crete, Greece (2019) and European Agent Systems Summer School (EASSS), Porto, Portugal (2021).

Author: Gauthier Picard

Email: gauthier.picard@onera.fr

Created: 2022-01-18 Tue 08:56