Solving multiagent constraint optimization problems on the constraint composite graph

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

doi:10.1007/978-3-030-03098-8_7

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/Entry/Poem › Conference contribution

3 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 language	English (US)
Title of host publication	PRIMA 2018
Subtitle of host publication	Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings
Editors	Nir Oren, Yuko Sakurai, Itsuki Noda, Tran Cao Son, Tim Miller, Bastin Tony Savarimuthu
Publisher	Springer Verlag
Pages	106-122
Number of pages	17
ISBN (Print)	9783030030971
DOIs	https://doi.org/10.1007/978-3-030-03098-8_7
State	Published - 2018
Externally published	Yes
Event	21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018 - Tokyo, Japan Duration: Oct 29 2018 → Nov 2 2018

Publication series

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

Conference

Conference	21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018
Country/Territory	Japan
City	Tokyo
Period	10/29/18 → 11/2/18

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-03098-8_7

Cite this

Fioretto, F., Xu, H., Koenig, S., & Kumar, T. K. S. (2018). Solving multiagent constraint optimization problems on the constraint composite graph. In N. Oren, Y. Sakurai, I. Noda, T. Cao Son, T. Miller, & B. T. Savarimuthu (Eds.), PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings (pp. 106-122). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11224 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-030-03098-8_7

Solving multiagent constraint optimization problems on the constraint composite graph. / Fioretto, Ferdinando; Xu, Hong; Koenig, Sven et al.
PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings. ed. / Nir Oren; Yuko Sakurai; Itsuki Noda; Tran Cao Son; Tim Miller; Bastin Tony Savarimuthu. Springer Verlag, 2018. p. 106-122 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11224 LNAI).

Research output: Chapter in Book/Entry/Poem › Conference contribution

Fioretto, F, Xu, H, Koenig, S & Kumar, TKS 2018, Solving multiagent constraint optimization problems on the constraint composite graph. in N Oren, Y Sakurai, I Noda, T Cao Son, T Miller & BT Savarimuthu (eds), PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11224 LNAI, Springer Verlag, pp. 106-122, 21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018, Tokyo, Japan, 10/29/18. https://doi.org/10.1007/978-3-030-03098-8_7

Fioretto F, Xu H, Koenig S, Kumar TKS. Solving multiagent constraint optimization problems on the constraint composite graph. In Oren N, Sakurai Y, Noda I, Cao Son T, Miller T, Savarimuthu BT, editors, PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings. Springer Verlag. 2018. p. 106-122. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-03098-8_7

Fioretto, Ferdinando ; Xu, Hong ; Koenig, Sven et al. / Solving multiagent constraint optimization problems on the constraint composite graph. PRIMA 2018: Principles and Practice of Multi-Agent Systems - 21st International Conference, 2018, Proceedings. editor / Nir Oren ; Yuko Sakurai ; Itsuki Noda ; Tran Cao Son ; Tim Miller ; Bastin Tony Savarimuthu. Springer Verlag, 2018. pp. 106-122 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{517a28e9555d4f168c9af3c2b8702259,

title = "Solving multiagent constraint optimization problems on the constraint composite graph",

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.",

author = "Ferdinando Fioretto and Hong Xu and Sven Koenig and Kumar, {T. K.Satish}",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018 ; Conference date: 29-10-2018 Through 02-11-2018",

year = "2018",

doi = "10.1007/978-3-030-03098-8_7",

language = "English (US)",

isbn = "9783030030971",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "106--122",

editor = "Nir Oren and Yuko Sakurai and Itsuki Noda and {Cao Son}, Tran and Tim Miller and Savarimuthu, {Bastin Tony}",

booktitle = "PRIMA 2018",

}

TY - GEN

T1 - Solving multiagent constraint optimization problems on the constraint composite graph

AU - Fioretto, Ferdinando

AU - Xu, Hong

AU - Koenig, Sven

AU - Kumar, T. K.Satish

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2018.

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85056475722&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056475722&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-03098-8_7

DO - 10.1007/978-3-030-03098-8_7

M3 - Conference contribution

AN - SCOPUS:85056475722

SN - 9783030030971

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 106

EP - 122

BT - PRIMA 2018

A2 - Oren, Nir

A2 - Sakurai, Yuko

A2 - Noda, Itsuki

A2 - Cao Son, Tran

A2 - Miller, Tim

A2 - Savarimuthu, Bastin Tony

PB - Springer Verlag

T2 - 21st International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2018

Y2 - 29 October 2018 through 2 November 2018

ER -

Solving multiagent constraint optimization problems on the constraint composite graph

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this