A dynamic programming-based MCMC framework for solving DCOPs with GPUs

Ferdinando Fioretto, William Yeoh, Enrico Pontelli

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

10 Scopus citations

Abstract

The field of Distributed Constraint Optimization (DCOP) has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent coordination. Nevertheless, solving DCOPs is computationally challenging. Thus, in large scale, complex applications, incomplete DCOP algorithms are necessary. Recently, researchers have introduced a promising class of incomplete DCOP algorithms, based on sampling. However, this paradigm requires a multitude of samples to ensure convergence. This paper exploits the property that sampling is amenable to parallelization, and introduces a general framework, called Distributed MCMC (DMCMC), that is based on a dynamic programming procedure and uses Markov Chain Monte Carlo (MCMC) sampling algorithms to solve DCOPs. Additionally, DMCMC harnesses the parallel computing power of Graphical Processing Units (GPUs) to speed-up the sampling process. The experimental results show that DMCMC can find good solutions up to two order of magnitude faster than other incomplete DCOP algorithms.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 22nd International Conference, CP 2016, Proceedings
EditorsMichel Rueher
PublisherSpringer Verlag
Pages813-831
Number of pages19
ISBN (Print)9783319449524
DOIs
StatePublished - Jan 1 2016
Externally publishedYes
Event22nd International Conference on Principles and Practice of Constraint Programming, CP 2016 - Toulouse, France
Duration: Sep 5 2016Sep 9 2016

Publication series

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

Conference

Conference22nd International Conference on Principles and Practice of Constraint Programming, CP 2016
CountryFrance
CityToulouse
Period9/5/169/9/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A dynamic programming-based MCMC framework for solving DCOPs with GPUs'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., Yeoh, W., & Pontelli, E. (2016). A dynamic programming-based MCMC framework for solving DCOPs with GPUs. In M. Rueher (Ed.), Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Proceedings (pp. 813-831). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9892 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-44953-1_51