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

Article

A scalable method for multiagent constraint optimization

Authors:

Boi FaltingsAuthors Info & Claims

IJCAI'05: Proceedings of the 19th international joint conference on Artificial intelligence

Pages 266 - 271

Published: 30 July 2005 Publication History

Abstract

We present in this paper a new, complete method for distributed constraint optimization, based on dynamic programming. It is a utility propagation method, inspired by the sum-product algorithm, which is correct only for tree-shaped constraint networks. In this paper, we show how to extend that algorithm to arbitrary topologies using a pseudotree arrangement of the problem graph. Our algorithm requires a linear number of messages, whose maximal size depends on the induced width along the particular pseudotree chosen.

We compare our algorithm with backtracking algorithms, and present experimental results. For some problem types we report orders of magnitude fewer messages, and the ability to deal with arbitrarily large problems. Our algorithm is formulated for optimization problems, but can be easily applied to satisfaction problems as well.

References

[1]

{Arnborg, 1985} S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey. BIT, 25(1):2-23, 1985.

Digital Library

[2]

{Barbosa, 1996} Valmir Barbosa. An Introduction to Distributed Algorithms. The MIT Press, 1996.

Digital Library

[3]

{Bayardo and Miranker, 1995} Roberto Bayardo and Daniel Miranker. On the space-time trade-off in solving constraint satisfaction problems. In Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI- 95, Montreal, Canada, 1995.

Digital Library

[4]

{Bejar et al., 2005} Ramon Bejar, Cesar Fernandez, Magda Valls, Carmel Domshlak, Carla Gomes, Bart Selman, and Bhaskar Krishnamachari. Sensor networks and distributed CSP: Communication, computation and complexity. Artificial Intelligence, 161(1-2):117-147, 2005.

Digital Library

[5]

{Dechter and Fattah, 2001} Rina Dechter and Yousri El Fattah. Topological parameters for time-space tradeoff. Artificial Intelligence, 125(1-2):93-118, 2001.

Digital Library

[6]

{Dechter, 2003} Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.

Digital Library

[7]

{Freuder and Quinn, 1985} Eugene C. Freuder and Michael J. Quinn. Taking advantage of stable sets of variables in constraint satisfaction problems. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, IJCAI-85, pages 1076-1078, Los Angeles, CA, 1985.

[8]

{Freuder, 1985} Eugene C. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(14):755-761, 1985.

Digital Library

[9]

{Hamadi et al., 1998} Y. Hamadi, C. Bessière, and J. Quinqueton. Backtracking in distributed constraint networks. In ECAI-98, pages 219-223, 1998.

[10]

{Kasif, 1986} Simon Kasif. On the parallel complexity of some constraint satisfaction problems. In Proceedings of the National Conference on Artificial Intelligence, AAAI- 86, pages 349-353, Philadelphia, PA, 1986.

Digital Library

[11]

{Kschischang et al., 2001} Frank R. Kschischang, Brendan Frey, and Hans Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions On Information Theory, 47(2):498-519, FEBRUARY 2001.

Digital Library

[12]

{Maheswaran et al., 2004} Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, and Pradeep Varakantham. Taking DCOP to the realworld: Efficient complete solutions for distributed multi-event scheduling. In AAMAS-04, 2004.

Digital Library

[13]

{Meisels and Zivan, 2003} Amnon Meisels and Roie Zivan. Asynchronous forward-checking on DisCSPs. In Proceedings of the Distributed Constraint Reasoning Workshop, IJCAI 2003, Acapulco, Mexico, 2003.

[14]

{Modi et al., 2003} P. J. Modi, W. M. Shen, and M. Tambe. An asynchronous complete method for distributed constraint optimization. In Proc. AAMAS, 2003.

Digital Library

[15]

{Petcu and Faltings, 2004} Adrian Petcu and Boi Faltings. A distributed, complete method for multi-agent constraint optimization. In CP 2004 - Fifth International Workshop on Distributed Constraint Reasoning (DCR2004) in Toronto, Canada, September 2004.

[16]

{Schiex, 1999} Thomas Schiex. A note on CSP graph parameters. Technical Report 03, INRA, 07 1999.

[17]

{Silaghi et al., 2000} Marius-Calin Silaghi, Djamila Sam-Haroud, and Boi Faltings. Asynchronous search with aggregations. In AAAI/IAAI, pages 917-922, Austin, Texas, 2000.

Digital Library

[18]

{Yokoo et al., 1992} Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In International Conference on Distributed Computing Systems, pages 614-621, 1992.

[19]

{Yokoo et al., 1998} Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. The distributed constraint satisfaction problem - formalization and algorithms. IEEE Transactions on Knowledge and Data Engineering, 10(5):673-685, 1998.

Digital Library

Cited By

Cohen ELev OZivan RWilliams BChen YNeville J(2023)Separate but equalProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25506(3924-3931)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25506
Sarker AChoudhury MKhan MDignum FLomuscio AEndriss UNowé A(2021)A Local Search Based Approach to Solve Continuous DCOPsProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464083(1127-1135)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464083
Matsui T(2021)A Study on Applying Decentralized Constraint Optimization to Mobile Sensor Teams with Range SensorsProceedings of the 5th International Conference on Advances in Artificial Intelligence10.1145/3505711.3505737(183-188)Online publication date: 20-Nov-2021
https://dl.acm.org/doi/10.1145/3505711.3505737
Show More Cited By

A scalable method for multiagent constraint optimization
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 ...
Constraint Handling in Particle Swarm Optimization

In this article, the authors propose a particle swarm optimization PSO for constrained optimization. The proposed PSO adopts a multiobjective approach to constraint handling. Procedures to update the feasible and infeasible personal best are designed to ...
Ant Colony Optimization and Constraint Programming

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI'05: Proceedings of the 19th international joint conference on Artificial intelligence

July 2005

1775 pages

Sponsors

The International Joint Conferences on Artificial Intelligence, Inc.

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 30 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

159
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cohen ELev OZivan RWilliams BChen YNeville J(2023)Separate but equalProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i4.25506(3924-3931)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i4.25506
Sarker AChoudhury MKhan MDignum FLomuscio AEndriss UNowé A(2021)A Local Search Based Approach to Solve Continuous DCOPsProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464083(1127-1135)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464083
Matsui T(2021)A Study on Applying Decentralized Constraint Optimization to Mobile Sensor Teams with Range SensorsProceedings of the 5th International Conference on Advances in Artificial Intelligence10.1145/3505711.3505737(183-188)Online publication date: 20-Nov-2021
https://dl.acm.org/doi/10.1145/3505711.3505737
Barambones JRichoux FImbert RInoue K(2021)Resilient Team Formation with Stabilisability of Agent Networks for Task AllocationACM Transactions on Autonomous and Adaptive Systems10.1145/346336815:3(1-24)Online publication date: 13-Jul-2021
https://dl.acm.org/doi/10.1145/3463368
Sarker AArif AChoudhury MKhan MEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)C-CoCoAProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3399051(1990-1992)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3399051
Mahmud SChoudhury MKhan MTran-Thanh LJennings NEl Fallah Seghrouchni ASukthankar GAn BYorke-Smith N(2020)AED: An Anytime Evolutionary DCOP AlgorithmProceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3398761.3398859(825-833)Online publication date: 5-May-2020
https://dl.acm.org/doi/10.5555/3398761.3398859
Ghose ABudi AAdinugroho S(2020)Collaborative optimization networksProceedings of the 5th International Conference on Sustainable Information Engineering and Technology10.1145/3427423.3427468(1-4)Online publication date: 16-Nov-2020
https://dl.acm.org/doi/10.1145/3427423.3427468
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
Deng YChen ZChen DZhang WJiang X(2019)AsymDPOPProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367065(223-230)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367065
Fransman JSijs JDol HTheunissen EDe Schutter BElkind EVeloso MAgmon NTaylor M(2019)Bayesian-DPOP for Continuous Distributed Constraint Optimization ProblemsProceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3306127.3331977(1961-1963)Online publication date: 8-May-2019
https://dl.acm.org/doi/10.5555/3306127.3331977
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.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents