TY - GEN
T1 - A dynamic programming-based MCMC framework for solving DCOPs with GPUs
AU - Fioretto, Ferdinando
AU - Yeoh, William
AU - Pontelli, Enrico
N1 - 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 -