Article

Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

Authors:

AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1

Pages 438 - 445

Published: 19 July 2004 Publication History

Get Access

Abstract

Distributed Constraint Optimization Problems (DCOP) have, for a long time, been considered an important research area for multi-agent systems because a vast number of real-world situations can be modeled by them. The goal of many of the researchers interested in DCOP has been to find ways to solve them efficiently using fully distributed algorithms which are often based on existing centralized techniques. In this paper, we present an optimal, distributed algorithm called optimal asynchronous partial overlay (OptAPO) for solving DCOPs that is based on a partial centralization technique called cooperative mediation. The key ideas used by this algorithm are that agents, when acting as a mediator, centralize relevant portions of the DCOP, that these centralized subproblems overlap, and that agents increase the size of their subproblems as the problem solving unfolds. We present empirical evidence that shows that OptAPO performs better than other known, optimal DCOP techniques.

References

[1]

{1} E. C. Freuder and R. J. Wallace. Partial constrain satisfaction. Artificial Intelligence, 58(1-3):21-70, 1992.

Digital Library

Google Scholar

[2]

{2} K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In G. Smolka, editor, Principles and Practice of Constraint Programming (CP-97), volume 1330 of Lecture Notes in Computer Science, pages 222-236. Springer-Verlag, 1997.

Google Scholar

[3]

{3} B. Horling, R. Mailler, and V. Lesser. Farm: A Scalable Environment for Multi-Agent Development and Evaluation. Proceedings of the 2nd International Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS 2003), pages 171-177, May 2003.

Google Scholar

[4]

{4} M. Lemaitre and G. Verfaillie. An incomplete method for slving distributed valued constraint satisfaction problems. In Proceedings of the AAAI Workshop on Constraints and Agents, 1997.

Google Scholar

[5]

{5} R. Mailler and V. Lesser. A Mediation Based Protocol for Distributed Constraint Satisfaction. The Fourth International Workshop on Distributed Constraint Reasoning, pages 49-58, August 2003.

Google Scholar

[6]

{6} P. J. Modi, W.-M. Shen, M. Tambe, and M. Yokoo. An asynchronous complete method for distributed constraint optimization. In Proceedings of the Second International Joint Conference on Autonomous Agent and Multiagent Systems (AAMAS-03), Melbourne, Australia, July 2003.

Digital Library

Google Scholar

[7]

{7} R. Wallace. Enhancements of branch and bound methods for the maximal constraint satisfaction problem. In M. Jampel, E. Freduer, and M. Maher, editors, OCS'95: Workshop on Over-Constrained Systems at CP'95, Cassis, Marseilles, 18, 1995.

Google Scholar

[8]

{8} M. Yokoo and E. H. Durfee. Distributed constraint optimization as a formal model of partially adversarial cooperation. Technical Report CSE-TR-101-91, University of Michigan, Ann Arbor, MI 48109, 1991.

Google Scholar

Cited By

View all

Tassa TGrinshpoun TYanai A(2019)A privacy preserving collusion secure DCOP algorithmProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367707(4774-4780)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367707
Singh AKumar AElkind EVeloso MAgmon NTaylor M(2019)Graph Based Optimization for Multiagent CooperationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331863(1497-1505)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331863
Nguyen DYeoh WLau HZivan R(2019)Distributed gibbsJournal of Artificial Intelligence Research10.1613/jair.1.1140064:1(705-748)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11400
Show More Cited By

Index Terms

Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

Recommendations

Solving dynamic constraint optimization problems using ICHEA
ICONIP'12: Proceedings of the 19th international conference on Neural Information Processing - Volume Part III

Many real-world constrained problems have a set of predefined static constraints that can be solved by evolutionary algorithms (EAs) whereas some problems have dynamic constraints that may change over time or may be received by the problem solver at run ...
Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems
AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1

Distributive Constraint Satisfaction (DCSP) has long been considered an important area of research for multi-agent systems. This is partly due to the fact that many real-world problem can be represented as constraint satisfaction and partly because real-...
A pre-processing algorithm for solving constraint satisfaction optimisation problems
SAICSIT '03: Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology

A constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAMAS '04: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 1

July 2004

494 pages

ISBN:1581138644

Publisher

IEEE Computer Society

United States

Publication History

Published: 19 July 2004

Check for updates

Qualifiers

Article

Conference

AAMAS04

Sponsor:

SIGAI

AAMAS04: The Third International Joint Conference on Autonomous Agents and Multi-Agent Systems 2004

July 19 - 23, 2004

New York, New York

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
24
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tassa TGrinshpoun TYanai A(2019)A privacy preserving collusion secure DCOP algorithmProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367707(4774-4780)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367707
Singh AKumar AElkind EVeloso MAgmon NTaylor M(2019)Graph Based Optimization for Multiagent CooperationProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331863(1497-1505)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331863
Nguyen DYeoh WLau HZivan R(2019)Distributed gibbsJournal of Artificial Intelligence Research10.1613/jair.1.1140064:1(705-748)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1613/jair.1.11400
Liu YLiu JBasar TAndre EKoenig SDastani MSukthankar G(2018)Gossip Gradient DescentProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3238049(1995-1997)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3238049
El Khattabi GHaij OBenelallam IBouyakhf E(2018)Detection of Unethical Intelligent Agents in Ethical Distributed Constraint Satisfaction ProblemsProceedings of the 2nd Mediterranean Conference on Pattern Recognition and Artificial Intelligence10.1145/3177148.3180083(52-57)Online publication date: 27-Mar-2018
https://dl.acm.org/doi/10.1145/3177148.3180083
Yu ZChen ZHe JDeng YLarson KWinikoff MDas SDurfee E(2017)A Partial Decision Scheme for Local Search Algorithms for Distributed Constraint Optimization ProblemsProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091157(187-194)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091157
Chen ZHe ZHe C(2017)An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimizationApplied Intelligence10.1007/s10489-017-0905-447:3(607-623)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s10489-017-0905-4
Le TFioretto FYeoh WSon TPontelli EJonker CMarsella SThangarajah JTuyls K(2016)ER-DCOPsProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2937014(606-614)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2937014
Ghosh SKumar AVarakantham P(2015)Probabilistic inference based message-passing for resource constrained DCOPsProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832306(411-417)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832249.2832306
Agrawal PKumar AVarakantham PWeiss GYolum PBordini RElkind E(2015)Near-Optimal Decentralized Power Supply Restoration in Smart GridsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773315(1275-1283)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773315
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Solving dynamic constraint optimization problems using ICHEA

Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems

A pre-processing algorithm for solving constraint satisfaction optimisation problems