[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/2772879.2772932acmotherconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Dynamic Theoretical Analysis of the Distributed Stochastic and Distributed Breakout Algorithms

Published: 04 May 2015 Publication History

Abstract

The distributed constraint satisfaction problem is often used to model real-world situations and find agent-based solutions. A number of methods have been developed to solve these problems, including the well-known DSA and DBA algorithms. In many real scenarios, however, the problems are not static. This forces practitioners to adapt these protocols to solve dynamic distributed constraint satisfaction problems (DynDCSP). Surprisingly, despite long-running study of the problem, practically all analysis of DynDCSP algorithms has been experimental in nature. This work presents a new theoretical assessment of the DSA and DBA algorithms, leveraging a mapping of DynDCSP instances to a physical thermodynamics model to develop a deeper understanding of the algorithms' behavior.
Here, we assess the static versions of DSA and DBA, but focus on examining their rates of convergence, not just their final convergence points, as a means of understanding how they will perform in dynamic settings. We develop various theoretical approaches to show how the algorithms' convergence rates are affected by problem density and tightness, and examine the impact that problem size has on an algorithm's performance. Finally, we show the accuracy of our analytical predictions through comparison with experimental results.

References

[1]
F. Bacchus and P. van Beek. On the conversion between non-binary constraint satisfaction problems. Proceedings of the 15th Nat'l 10th Conf. on Artificial Intelligence Innovative Applications of Artificial Intelligence, pages 311--318, 1998.
[2]
E. Bowring, J. P. Pearce, C. Portway, M. Jain, and M. Tambe. On k-optimal distributed constraint optimization algorithms: New bounds and algorithms. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems - Volume 2, pages 607--614, 2008.
[3]
R. Dechter and A. Dechter. Belief maintenance in dynamic constraint networks. In Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-88), pages 37--42, 1988.
[4]
R. Fitzpatrick. Thermodynamics and Statistical Mechanics: An intermediate level course. Lulu Enterprises, Inc., 2006.
[5]
S. Fitzpatrick and L. Meertens. Distributed Sensor Networks: A Multiagent Perspective, chapter Distributed Coordination Through Anarchic Optimization, pages 257--294. Kluwer Academic Publishers, 2003.
[6]
R. Mailler. Comparing two approaches to dynamic, distributed constraint satisfaction. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 1049--1056, 2005.
[7]
R. Mailler and H. Zheng. A new analysis method for dynamic, distributed constraint satisfaction. In Proceedings of the 2014 International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 901--908, 2014.
[8]
A. Meisels, I. Razgon, E. Kaplansky, and R. Zivan. Comparing performance of distributed constraints processing algorithms. In Proc. AAMAS-2002 Workshop on Distributed Constraint Reasoning DCR, pages 86--93, 2002.
[9]
P. Morris. The breakout method for escaping local minima. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 40--45, 1993.
[10]
I. Wolfram Research. Mathematica version 8.0, 2010.
[11]
M. Yokoo and K. Hirayama. Distributed breakout algorithm for solving distributed constraint satisfaction problems. In Proceedings of the 2nd Int'l Conf. on Multiagent Systems, pages 401--408, 1996.
[12]
W. Zhang, G. Wang, Z. Xing, and L. Wittenburg. Chapter 13: A comparative study of distributed constraint algorithms. Distributed Sensor Networks: A Multiagent Perspective, 2003.

Cited By

View all
  • (2017)Solving DCSP problems in highly degraded communication environmentsProceedings of the International Conference on Web Intelligence10.1145/3106426.3106445(348-355)Online publication date: 23-Aug-2017

Index Terms

  1. Dynamic Theoretical Analysis of the Distributed Stochastic and Distributed Breakout Algorithms

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Other conferences
      AAMAS '15: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
      May 2015
      2072 pages
      ISBN:9781450334136

      Sponsors

      • IFAAMAS

      In-Cooperation

      Publisher

      International Foundation for Autonomous Agents and Multiagent Systems

      Richland, SC

      Publication History

      Published: 04 May 2015

      Check for updates

      Author Tags

      1. constraint satisfaction
      2. dynamics
      3. thermodynamics

      Qualifiers

      • Research-article

      Funding Sources

      • Air Force Research Laboratory
      • National Science Foundation

      Conference

      AAMAS'15
      Sponsor:

      Acceptance Rates

      AAMAS '15 Paper Acceptance Rate 108 of 670 submissions, 16%;
      Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 21 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2017)Solving DCSP problems in highly degraded communication environmentsProceedings of the International Conference on Web Intelligence10.1145/3106426.3106445(348-355)Online publication date: 23-Aug-2017

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media