Tutorial on Multi-Agent Optimization
at AAMAS 2024, the 23rd International Conference on Autonomous Agents and Multiagent Systems

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 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. The tutorial will conclude with the most recurrent challenges and open questions.

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.

This tutorial is planned to be in person.

The overall programme is as follows:

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

The slides presented during the tutorial are available here

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.