TY - GEN
T1 - A dynamic programming-based MCMC framework for solving DCOPs with GPUs
AU - Fioretto, Ferdinando
AU - Yeoh, William
AU - Pontelli, Enrico
N1 - Funding Information:
This research is partially supported by the National Science Foundation under grants 1345232 and 1550662. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies, or the U.S. government.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84986223647&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84986223647&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-44953-1_51
DO - 10.1007/978-3-319-44953-1_51
M3 - Conference contribution
AN - SCOPUS:84986223647
SN - 9783319449524
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 813
EP - 831
BT - Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Proceedings
A2 - Rueher, Michel
PB - Springer Verlag
T2 - 22nd International Conference on Principles and Practice of Constraint Programming, CP 2016
Y2 - 5 September 2016 through 9 September 2016
ER -