Article

Quality guarantees on k-optimal solutions for distributed constraint optimization problems

Authors:

Jonathan P. Pearce,

Milind TambeAuthors Info & Claims

IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence

Pages 1446 - 1451

Published: 06 January 2007 Publication History

Abstract

A distributed constraint optimization problem (DCOP) is a formalism that captures the rewards and costs of local interactions within a team of agents. Because complete algorithms to solve DCOPs are unsuitable for some dynamic or anytime domains, researchers have explored incomplete DCOP algorithms that result in locally optimal solutions. One type of categorization of such algorithms, and the solutions they produce, is k- optimality; a k-optimal solution is one that cannot be improved by any deviation by k or fewer agents. This paper presents the first known guarantees on solution quality for k-optimal solutions. The guarantees are independent of the costs and rewards in the DCOP, and once computed can be used for any DCOP of a given constraint graph structure.

References

[1]

{Boyd and Vandenberghe, 2004} S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge U. Press, 2004.

Digital Library

Google Scholar

[2]

{Fitzpatrick and Meertens, 2003} S. Fitzpatrick and L. Meertens. Distributed coordination through anarchic optimization. In V. Lesser, C. L. Ortiz, and M. Tambe, editors, Distributed Sensor Networks: A Multiagent Perspective, pages 257-295. Kluwer, 2003.

Crossref

Google Scholar

[3]

{Gutin and Yeo, 2005} G. Gutin and A. Yeo. Domination analysis of combinatorial optimization algorithms and problems. In M. Golumbic and I. Hartman, editors, Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications. Kluwer, 2005.

Google Scholar

[4]

{Maheswaran et al., 2004} R. T. Maheswaran, J. P. Pearce, and M. Tambe. Distributed algorithms for DCOP: A graphical-game-based approach. In PDCS, 2004.

Google Scholar

[5]

{Mailler and Lesser, 2004} R. Mailler and V. Lesser. Solving distributed constraint optimization problems using cooperative mediation. In AAMAS, 2004.

Digital Library

Google Scholar

[6]

{Modi et al., 2005} P. J. Modi, W. Shen, M. Tambe, and M. Yokoo. Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence , 161(1-2):149-180, 2005.

Digital Library

Google Scholar

[7]

{Nair et al., 2005} R. Nair, P. Varakantham, M. Tambe, and M. Yokoo. Networked distributed POMDPs: A synthesis of distributed constraint optimization and POMDPs. In AAAI, 2005.

Digital Library

Google Scholar

[8]

{Pearce et al., 2006} J. P. Pearce, R. T. Maheswaran, and M. Tambe. Solution sets for DCOPs and graphical games. In AAMAS, 2006.

Digital Library

Google Scholar

[9]

{Petcu and Faltings, 2005} A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In IJCAI , 2005.

Digital Library

Google Scholar

[10]

{Vlassis et al., 2004} N. Vlassis, R. Elhorst, and J. R. Kok. Anytime algorithms for multiagent decision making using coordination graphs. In Proc. Intl. Conf. on Systems, Man and Cybernetics, 2004.

Crossref

Google Scholar

[11]

{Yokoo and Hirayama, 1996} M. Yokoo and K. Hirayama. Distributed breakout algorithm for solving distributed constraint satisfaction and optimization problems. In ICMAS, 1996.

Google Scholar

[12]

{Zhang et al., 2005a} W. Zhang, G. Wang, Z. Xing, and L. Wittenberg. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Artificial Intelligence, 161(1-2):55-87, 2005.

Digital Library

Google Scholar

[13]

{Zhang et al., 2005b} Y. Zhang, J. G. Bellingham, R. E. Davis, and Y. Chao. Optimizing autonomous underwater vehicles' survey for reconstruction of an ocean field that varies in space and time. In American Geophysical Union, Fall meeting, 2005.

Google Scholar

Cited By

View all

Chen ZDeng YWu THe Z(2018)A class of iterative refined Max-sum algorithms via non-consecutive value propagation strategiesAutonomous Agents and Multi-Agent Systems10.5555/3288249.328826232:6(822-860)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288249.3288262
Fioretto FYeoh W(2018)AI buzzwords explainedAI Matters10.1145/3175502.31755063:4(8-13)Online publication date: 16-Feb-2018
https://dl.acm.org/doi/10.1145/3175502.3175506
van Leeuwen CPawełczak PSingh SMarkovitch S(2017)CoCoAProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298141(3944-3950)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298141
Show More Cited By

Quality guarantees on k-optimal solutions for distributed constraint optimization problems
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

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 ...
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 ...
Robust solutions in changing constraint satisfaction problems
IEA/AIE'10: Proceedings of the 23rd international conference on Industrial engineering and other applications of applied intelligent systems - Volume Part I

Constraint programming is a successful technology for solving combinatorial problems modeled as constraint satisfaction problems (CSPs). An important extension of constraint technology involves problems that undergo changes that may invalidate the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IJCAI'07: Proceedings of the 20th international joint conference on Artifical intelligence

January 2007

2953 pages

Editors:
Rajeev Sangal
International Institute of Information Technology, Hyderabad
,
Harish Mehta
Onward Technologies Limited
,
R. K. Bagga
International Institute of Information Technology, Hyderabad

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 06 January 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen ZDeng YWu THe Z(2018)A class of iterative refined Max-sum algorithms via non-consecutive value propagation strategiesAutonomous Agents and Multi-Agent Systems10.5555/3288249.328826232:6(822-860)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288249.3288262
Fioretto FYeoh W(2018)AI buzzwords explainedAI Matters10.1145/3175502.31755063:4(8-13)Online publication date: 16-Feb-2018
https://dl.acm.org/doi/10.1145/3175502.3175506
van Leeuwen CPawełczak PSingh SMarkovitch S(2017)CoCoAProceedings of the Thirty-First AAAI Conference on Artificial Intelligence10.5555/3298023.3298141(3944-3950)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3298023.3298141
Chen ZDeng YWu TLarson KWinikoff MDas SDurfee E(2017)An Iterative Refined Max-sum_AD Algorithm via Single-side Value Propagation and Local SearchProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091158(195-202)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091158
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
Zivan RParash TCohen LPeled HOkamoto S(2017)Balancing exploration and exploitation in incomplete Min/Max-sum inference for distributed constraint optimizationAutonomous Agents and Multi-Agent Systems10.1007/s10458-017-9360-131:5(1165-1207)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s10458-017-9360-1
Tassa TZivan RGrinshpoun T(2016)Preserving privacy in region optimal DCOP algorithmsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060691(496-502)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060691
Fioretto FWeiss GYolum PBordini RElkind E(2015)Exploiting the Structure of Distributed Constraint Optimization ProblemsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773549(2007-2008)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773549
Fioretto FCampeotto FDovier APontelli EYeoh WWeiss GYolum PBordini RElkind E(2015)Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization ProblemsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773461(1835-1836)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773461
Zivan RYedidsion HOkamoto SGlinton RSycara K(2015)Distributed constraint optimization for teams of mobile sensing agentsAutonomous Agents and Multi-Agent Systems10.1007/s10458-014-9255-329:3(495-536)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s10458-014-9255-3
Show More Cited By

View Options

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

Recommendations

Solving dynamic constraint optimization problems using ICHEA

A pre-processing algorithm for solving constraint satisfaction optimisation problems

Robust solutions in changing constraint satisfaction problems