Constraint composite graph-based lifted message passing for distributed constraint optimization problems

Ferdinando Fioretto, Hong Xu, Sven Koenig, T. K. Satish Kumar

Research output: Contribution to conferencePaper

Abstract

The Distributed Constraint Optimization Problem (DCOP) offers a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinates their actions to optimize a global objective function, taking into account their local preferences. In the majority of DCOP algorithms, agents operate on three main graphical representations of the problem: (a) the constraint graph, (b) the pseudo-tree, or (c) the factor graph. In this paper, we introduce the Constraint Composite Graph (CCG) for DCOPs, an alternative graphical representation on which agents can coordinate their assignments to solve the distributed problem suboptimally. By leveraging this representation, agents are able to reduce the size of the problem. We propose a novel variant of Max-Sum–a popular DCOP incomplete algorithm–called CCG-Max-Sum, which is applied to CCGs. We also demonstrate the efficiency and effectiveness of CCG-Max-Sum on DCOP benchmarks based on several network topologies.

Original languageEnglish (US)
StatePublished - Jan 1 2018
Externally publishedYes
Event2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018 - Fort Lauderdale, United States
Duration: Jan 3 2018Jan 5 2018

Conference

Conference2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018
CountryUnited States
CityFort Lauderdale
Period1/3/181/5/18

ASJC Scopus subject areas

  • Applied Mathematics
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Constraint composite graph-based lifted message passing for distributed constraint optimization problems'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., Xu, H., Koenig, S., & Satish Kumar, T. K. (2018). Constraint composite graph-based lifted message passing for distributed constraint optimization problems. Paper presented at 2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018, Fort Lauderdale, United States.