Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph

Ferdinando Fioretto, Hong Xu, Sven Koenig, and T. K. Satish Kumar. Solving multiagent constraint optimization problems on the constraint composite graph. In Proceedings of the 21st International Conference on Principles and Practice of Multi-Agent Systems (PRIMA), 106–122. 2018. doi:10.1007/978-3-030-03098-8_7.
[full text] [BibTeX▼]

@inproceedings{fioretto2018a,
    author = "Fioretto, Ferdinando and Xu, Hong and Koenig, Sven and Kumar, T. K. Satish",
    title = "Solving Multiagent Constraint Optimization Problems on the Constraint Composite Graph",
    year = "2018",
    pages = "106--122",
    doi = "10.1007/978-3-030-03098-8\_7",
    booktitle = "Proceedings of the 21st International Conference on Principles and Practice of Multi-Agent Systems (PRIMA)"
}

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.

Full Text

[download]