More Web Proxy on the site http://driver.im/

article

Distributed gibbs: a linear-space sampling-based DCOP algorithm

Authors:

Duc Thien Nguyen,

Hoong Chuin Lau,

Roie ZivanAuthors Info & Claims

Journal of Artificial Intelligence Research, Volume 64, Issue 1

Pages 705 - 748

https://doi.org/10.1613/jair.1.11400

Published: 01 January 2019 Publication History

Abstract

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.

References

[1]

Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47 (2-3), 235-256.

Digital Library

[2]

Bacchus, F., Chen, X., van Beek, P., & Walsh, T. (2002). Binary vs. non-binary constraints. Artificial Intelligence, 140 (1-2), 1-37.

Digital Library

[3]

Besag, J. (1986). On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society, Series B, 48 (3), 259-279.

[4]

Burke, D., & Brown, K. (2006). Efficiently handling complex local problems in distributed constraint optimisation. In Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 701-702.

Digital Library

[5]

Dechter, R. (Ed.). (2003). Constraint Processing. Morgan Kaufmann.

Digital Library

[6]

Farinelli, A., Rogers, A., Petcu, A., & Jennings, N. (2008). Decentralised coordination of low-power embedded devices using the Max-Sum algorithm. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 639-646.

Digital Library

[7]

Fernàndez, C., Béjar, R., Krishnamachari, B., & Gomes, C. (2002). Communication and computation in distributed CSP algorithms. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp. 664-679.

Digital Library

[8]

Fioretto, F., Le, T., Yeoh, W., Pontelli, E., & Son, T. C. (2014). Improving DPOP with branch consistency for solving distributed constraint optimization problems. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp. 307-323.

[9]

Fioretto, F., Pontelli, E., & Yeoh, W. (2018). Distributed constraint optimization problems and applications: A survey. Journal of Artificial Intelligence Research, 61, 623-698.

Digital Library

[10]

Fioretto, F., Yeoh, W., & Pontelli, E. (2016). Multi-variable agent decomposition for DCOPs. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 2480-2486.

Digital Library

[11]

Fioretto, F., Yeoh, W., & Pontelli, E. (2017). A multiagent system approach to scheduling devices in smart homes. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 981-989.

Digital Library

[12]

Geman, S., & Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (6), 721-741.

Digital Library

[13]

Gershman, A., Meisels, A., & Zivan, R. (2009). Asynchronous Forward-Bounding for distributed COPs. Journal of Artificial Intelligence Research, 34, 61-88.

[14]

Ghosh, S., Kumar, A., & Varakantham, P. (2015). Probabilistic inference based message-passing for resource constrained DCOPs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 411-417.

Digital Library

[15]

Globerson, A., & Jaakkola, T. (2007). Fixing Max-Product: Convergent message passing algorithms for MAP LP-relaxations. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), pp. 553-560.

Digital Library

[16]

Gutierrez, P., Meseguer, P., & Yeoh, W. (2011). Generalizing ADOPT and BnB-ADOPT. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 554-559.

Digital Library

[17]

Hamadi, Y., Bessière, C., & Quinqueton, J. (1998). Distributed intelligent backtracking. In Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 219-223.

[18]

Hoang, K. D., Fioretto, F., Hou, P., Yokoo, M., Yeoh, W., & Zivan, R. (2016). Proactive dynamic distributed constraint optimization. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 597-605.

Digital Library

[19]

Hoang, K. D., Hou, P., Fioretto, F., Yeoh, W., Zivan, R., & Yokoo, M. (2017). Infinite-horizon proactive dynamic DCOPs. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 212-220.

Digital Library

[20]

Kocsis, L., & Szepesvári, C. (2006). Bandit based Monte-Carlo planning. In Proceedings of the European Conference on Machine Learning (ECML), pp. 282-293.

Digital Library

[21]

Kumar, A., Faltings, B., & Petcu, A. (2009). Distributed constraint optimization with structured resource constraints. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 923-930.

Digital Library

[22]

Kumar, A., Yeoh, W., & Zilberstein, S. (2011). On message-passing, MAP estimation in graphical models and DCOPs. In Proceedings of the Distributed Constraint Reasoning Workshop, pp. 57-70.

[23]

Kumar, A., & Zilberstein, S. (2010). MAP estimation for graphical models by likelihood maximization. In Proceedings of the Conference on Neural Information Processing Systems (NIPS), pp. 1180-1188.

Digital Library

[24]

Lass, R., Kopena, J., Sultanik, E., Nguyen, D., Dugan, C., Modi, P., & Regli, W. (2008). Coordination of first responders under communication and resource constraints (Short Paper). In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1409-1413.

Digital Library

[25]

Léauté, T., & Faltings, B. (2011). Coordinating logistics operations with privacy guarantees. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 2482-2487.

Digital Library

[26]

Léauté, T., Ottens, B., & Szymanek, R. (2009). FRODO 2.0: An open-source framework for distributed constraint optimization. In Proceedings of the Distributed Constraint Reasoning Workshop, pp. 160-164.

[27]

Maheswaran, R., Pearce, J., & Tambe, M. (2004a). Distributed algorithms for DCOP: A graphical game-based approach. In Proceedings of the International Conference on Parallel and Distributed Computing Systems (PDCS), pp. 432-439.

[28]

Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., & Varakantham, P. (2004b). Taking DCOP to the real world: Efficient complete solutions for distributed event scheduling. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 310-317.

Digital Library

[29]

Mailler, R., & Lesser, V. (2004). Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 438-445.

Digital Library

[30]

Modi, P., Shen, W.-M., Tambe, M., & Yokoo, M. (2005). ADOPT: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161 (1-2), 149-180.

[31]

Nguyen, D. T., Yeoh, W., & Lau, H. C. (2012). Stochastic dominance in stochastic DCOPs for risk-sensitive applications. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 257-264.

Digital Library

[32]

Nguyen, D. T., Yeoh, W., & Lau, H. C. (2013). Distributed Gibbs: A memory-bounded sampling-based DCOP algorithm. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 167-174.

Digital Library

[33]

Nguyen, D. T., Yeoh, W., Lau, H. C., Zilberstein, S., & Zhang, C. (2014). Decentralized multi-agent reinforcement learning in average-reward dynamic DCOPs. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 1447-1455.

Digital Library

[34]

Ottens, B., Dimitrakakis, C., & Faltings, B. (2012). DUCT: An upper confidence bound approach to distributed constraint optimization problems. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 528-534.

Digital Library

[35]

Ottens, B., Dimitrakakis, C., & Faltings, B. (2017). DUCT: An upper confidence bound approach to distributed constraint optimization problems. ACM Transactions on Intelligent Systems and Technology, 8 (5), 69:1-69:27.

Digital Library

[36]

Petcu, A., & Faltings, B. (2005a). A scalable method for multiagent constraint optimization. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1413-1420.

Digital Library

[37]

Petcu, A., & Faltings, B. (2005b). Superstabilizing, fault-containing multiagent combinatorial optimization. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pp. 449-454.

Digital Library

[38]

Rajasekaran, S. (2000). On simulated annealing and nested annealing. Journal of Global Optimization, 16 (1), 43-56.

Digital Library

[39]

Rust, P., Picard, G., & Ramparany, F. (2016). Using message-passing DCOP algorithms to solve energy-Efficient smart environment configuration problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 468-474.

Digital Library

[40]

Sontag, D., Globerson, A., & Jaakkola, T. (2010). Introduction to Dual Decomposition for Inference. MIT Press.

[41]

Sontag, D., Meltzer, T., Globerson, A., Jaakkola, T., & Weiss, Y. (2008). Tightening LP relaxations for MAP using message passing. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), pp. 503-510.

Digital Library

[42]

Sultanik, E., Lass, R., & Regli, W. (2007). DCOPolis: a framework for simulating and deploying distributed constraint reasoning algorithms. In Proceedings of the Distributed Constraint Reasoning Workshop.

[43]

Tabakhi, A. M., Tourani, R., Natividad, F., Yeoh, W., & Misra, S. (2017). Pseudotree construction heuristics for DCOPs and evaluations on the ns-2 network simulator. In Proceedings of the International Conference on Tools with Artificial Intelligence (ICTAI).

Digital Library

[44]

Ueda, S., Iwasaki, A., & Yokoo, M. (2010). Coalition structure generation based on distributed constraint optimization. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 197-203.

Digital Library

[45]

Vinyals, M., Rodríguez-Aguilar, J., & Cerquides, J. (2011). Constructing a unifying theory of dynamic programming DCOP algorithms via the generalized distributive law. Autonomous Agents and Multi-Agent Systems, 22 (3), 439-464.

Digital Library

[46]

Wainwright, M., Jaakkola, T., & Willsky, A. (2002). MAP estimation via agreement on (hyper)trees: Message-passing and linear programming approaches. IEEE Transactions on Information Theory, 51, 3697-3717.

Digital Library

[47]

Yanover, C., Meltzer, T., & Weiss, Y. (2006). Linear programming relaxations and belief propagation - an empirical study. Journal of Machine Learning Research, 7, 1887-1907.

Digital Library

[48]

Yeoh, W., Felner, A., & Koenig, S. (2010). BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. Journal of Artificial Intelligence Research, 38, 85-133.

[49]

Yeoh, W., Varakantham, P., & Koenig, S. (2009). Caching schemes for DCOP search algorithms. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 609-616.

Digital Library

[50]

Yeoh, W., Varakantham, P., Sun, X., & Koenig, S. (2015). Incremental DCOP search algorithms for solving dynamic DCOPs. In Proceedings of the International Conference on Intelligent Agent Technology (IAT), pp. 257-264.

Digital Library

[51]

Yeoh, W., & Yokoo, M. (2012). Distributed problem solving. AI Magazine, 33 (3), 53-65.

Digital Library

[52]

Yokoo, M. (Ed.). (2001). Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-agent Systems. Springer.

Digital Library

[53]

Zivan, R., Okamoto, S., & Peled, H. (2014). Explorative anytime local search for distributed constraint optimization. Artificial Intelligence, 212, 1-26.

Digital Library

Cited By

Shi MJia GYokoo M(2025)The improved local cost simulation algorithms based on coalition structure generation for solving distributed constraint optimization problemsThe Journal of Supercomputing10.1007/s11227-024-06644-281:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06644-2
Gao JChen ZChen DZhang WLi Q(2024)Toward fast belief propagation for distributed constraint optimization problems via heuristic searchAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09643-y38:1Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10458-024-09643-y
Damle STriastcyn AFaltings BGujar S(2024)Differentially private multi-agent constraint optimizationAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09636-x38:1Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10458-024-09636-x
Show More Cited By

Recommendations

Distributed Gibbs: a memory-bounded sampling-based DCOP algorithm
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on ...
GD-GIBBS: a GPU-based sampling algorithm for solving distributed constraint optimization problems
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems

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 ...
The distributed breakout algorithms
Special issue: Distributed constraint satisfaction

We present a new series of distributed constraint satisfaction algorithms, the distributed breakout algorithms, which is inspired by local search algorithms for solving the constraint satisfaction problem (CSP). The basic idea of these algorithms is for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Artificial Intelligence Research

Journal of Artificial Intelligence Research Volume 64, Issue 1

January 2019

1007 pages

ISSN:1076-9757

Editor:
Satinder Singh

Issue’s Table of Contents

Publisher

AI Access Foundation

El Segundo, CA, United States

Publication History

Accepted: 01 March 2019

Published: 01 January 2019

Received: 01 February 2018

Published in JAIR Volume 64, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shi MJia GYokoo M(2025)The improved local cost simulation algorithms based on coalition structure generation for solving distributed constraint optimization problemsThe Journal of Supercomputing10.1007/s11227-024-06644-281:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06644-2
Gao JChen ZChen DZhang WLi Q(2024)Toward fast belief propagation for distributed constraint optimization problems via heuristic searchAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09643-y38:1Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10458-024-09643-y
Damle STriastcyn AFaltings BGujar S(2024)Differentially private multi-agent constraint optimizationAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09636-x38:1Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10458-024-09636-x
Zivan RRachmut BPerry OYeoh W(2023)Effect of asynchronous execution and imperfect communication on max-sum belief propagationAutonomous Agents and Multi-Agent Systems10.1007/s10458-023-09621-w37:2Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1007/s10458-023-09621-w
Gao JChen ZChen DZhang WPelachaud CTaylor MFaliszewski PMascardi V(2022)Beyond Uninformed Search: Improving Branch-and-bound Based Acceleration Algorithms for Belief Propagation via Heuristic StrategiesProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536045(1592-1594)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3536045
Chen DChen ZHe ZGao JSu Z(2022)Learning heuristics for weighted CSPs through deep reinforcement learningApplied Intelligence10.1007/s10489-022-03992-553:8(8844-8863)Online publication date: 3-Aug-2022
https://dl.acm.org/doi/10.1007/s10489-022-03992-5
Chen DChen ZDeng YHe ZWang L(2022)Inference-based complete algorithms for asymmetric distributed constraint optimization problemsArtificial Intelligence Review10.1007/s10462-022-10288-056:5(4491-4534)Online publication date: 3-Oct-2022
https://dl.acm.org/doi/10.1007/s10462-022-10288-0
Adrdor RKoutti L(2022)Improvement of Arc Consistency in Asynchronous Forward Bounding AlgorithmAI 2021: Advances in Artificial Intelligence10.1007/978-3-030-97546-3_47(582-591)Online publication date: 2-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-97546-3_47
Tabakhi AXiao YYeoh WZivan RDignum FLomuscio AEndriss UNowé A(2021)Branch-and-Bound Heuristics for Incomplete DCOPsProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464198(1677-1679)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464198
Rachmut BZivan RYeoh WDignum FLomuscio AEndriss UNowé A(2021)Latency-Aware Local Search for Distributed Constraint OptimizationProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464071(1019-1027)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464071
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents