Solving multiagent constraint optimization problems on the constraint composite graph

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We introduce the Constraint Composite Graph (CCG) for Distributed Constraint Optimization Problems (DCOPs), a popular paradigm used for the description and resolution of cooperative multi-agent problems. The CCG is a novel graphical representation of DCOPs 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, and demonstrate its efficiency and effectiveness on DCOP benchmarks based on several network topologies.

Original languageEnglish (US)
Title of host publicationPRIMA 2018
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings
EditorsNir Oren, Yuko Sakurai, Itsuki Noda, Tran Cao Son, Tim Miller, Bastin Tony Savarimuthu
PublisherSpringer Verlag
Pages106-122
Number of pages17
ISBN (Print)9783030030971
DOIs
StatePublished - Jan 1 2018
Externally publishedYes
Event21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018 - Tokyo, Japan
Duration: Oct 29 2018Nov 2 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11224 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018
CountryJapan
CityTokyo
Period10/29/1811/2/18

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Solving multiagent constraint optimization problems on the constraint composite graph'. Together they form a unique fingerprint.

Cite this