GD-Gibbs: A GPU-based sampling algorithm for solving distributed constraint optimization problems

Ferdinando Fioretto, Federico Campeotto, Luca Da Rin Fioretto, William Yeoh, Enrico Pontelli

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

10 Scopus citations

Abstract

Researchers have recently introduced a promising new class of Distributed Constraint Optimization Problem (DCOP) algorithms that is based on sampling. This paradigm is very amenable to parallelization since sampling algorithms require a lot of samples to ensure convergence, and the sampling process can be designed to be executed in parallel. This paper presents GPU-based D-Gibbs (GD-Gibbs), which extends the Distributed Gibbs (D-Gibbs) sampling algorithm and harnesses the power of parallel computation of GPUs to solve DCOPs. Experimental results show that GD-Gibbs is faster than several other benchmark algorithms on a distributed meeting scheduling problem.

Original languageEnglish (US)
Title of host publication13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1339-1340
Number of pages2
ISBN (Electronic)9781634391313
StatePublished - Jan 1 2014
Externally publishedYes
Event13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 - Paris, France
Duration: May 5 2014May 9 2014

Publication series

Name13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Volume2

Conference

Conference13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
CountryFrance
CityParis
Period5/5/145/9/14

Keywords

  • DCOP
  • Gibbs
  • GPU
  • Sampling

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'GD-Gibbs: A GPU-based sampling algorithm for solving distributed constraint optimization problems'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., Campeotto, F., Da Rin Fioretto, L., Yeoh, W., & Pontelli, E. (2014). GD-Gibbs: A GPU-based sampling algorithm for solving distributed constraint optimization problems. In 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 (pp. 1339-1340). (13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014; Vol. 2). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).