[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

ADOPT-ing: unifying asynchronous distributed optimization with asynchronous backtracking

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ali, S., Koenig, S., & Tambe, M. (2005). Preprocessing techniques for accelerating the DCOP algorithm ADOPT. In AAMAS.

  2. Armstrong, A., & Durfee, E. F. (1997). Dynamic prioritization of complex agents in distributed constraint satisfaction problems. In Proceedings of 15th IJCAI.

  3. Atlas, J., & Decker, K. (2007). A complete distributed constraint optimization method for non-traditional pseudotree arrangements. In AAMAS.

  4. Benisch, M., & Sadeh, N. (2006). Examining dcsp coordination tradeoffs. In AAMAS.

  5. Bessiere C., Brito I., Maestre A., Meseguer P. (2005) Asynchronous backtracking without adding links: A new member in the abt family. Artificial Intelligence 161: 7–24

    Article  MATH  MathSciNet  Google Scholar 

  6. Bistarelli, S., Fargier, H., Montanari, U., Rossi, F., Schiex, T., & Verfaillie, G. (1996). Semiring-based CSPs and valued CSPs: Basic properties and comparison. In Over-Constrained Systems (pp. 111—150). London, UK: Springer-Verlag.

  7. Bistarelli, S., Montanari, U., & Rossi, F. (1995). Constraint solving over semirings. In Proceedings IJCAI (pp. 624–630). Montreal.

  8. Bistarelli S., Montanari U., Rossi F., Schiex T., Verfaillie G., Fargier H. (1999) Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison. Constraints 4(3): 199–240

    Article  MATH  MathSciNet  Google Scholar 

  9. Chechetka, A., & Sycara, K. (2005). A decentralized variable ordering method for distributed constraint optimization. In AAMAS.

  10. Chechetka, A., & Sycara, K. (2006). No-commitment branch and bound search for distributed constraint optimization. In AAMAS.

  11. Collin, Z., Dechter, R., & Katz, S. (2000). Self-stabilizing distributed constraint satisfaction. Chicago Journal of Theoretical Computer Science.

  12. Dago, P. (1997). Backtrack dynamique valué. In JFPLC (pp. 133–148).

  13. Dago, P., & Verfaillie, G. (1996). Nogood recording for valued constraint satisfaction problems. In ICTAI.

  14. Dechter, R. (1990). Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition. AI’90.

  15. Dechter R. (2003) Constraint processing. Morgan Kaufman, San Francisco

    Google Scholar 

  16. Faltings, B. (2006). Handbook of constraint programming (Foundations of artificial intelligence), chap. Distributed constraint programming. New York, NY, USA: Elsevier.

  17. Franzin, M., Rossi, F., E.C., F., & Wallace, R. (2004). Multi-agent meeting scheduling with preferences: Efficiency, privacy loss, and solution quality. Computational Intelligence, 20(2).

  18. Gershman, A., Meisels, A., & Zivan, R. (2006). Asynchronous forward-bounding for distributed constraints optimization. In ECAI.

  19. Gershman, A., Meisels, A., & Zivan, R. (2007). Asynchronous forward-bounding with backjumping. In IJCAI DCR Workshop.

  20. Ginsberg M.L. (1993) Dynamic backtracking. Journal of AI Research 1: 25–46

    MATH  Google Scholar 

  21. Greenstadt, R., Pearce, J., Bowring, E., & Tambe, M. (2006). Experimental analysis of privacy loss in dcop algorithms. In AAMAS (pp. 1024–1027).

  22. Hamadi, Y., & Bessière, C. (1998). Backtracking in distributed constraint networks. In ECAI’98 (pp. 219–223).

  23. Hirayama, K., & Yokoo, M. (1997). Distributed partial constraint satisfaction problem. In Proceedings of the Conference on Constraint Processing (CP-97), LNCS 1330 (pp. 222–236).

  24. Jagota, A., & Dechter, R. (1997). Simple distributed algorithms for the cycle cutset problem. In SAC’97: Proceedings of the 1997 ACM symposium on Applied computing (pp. 366–373). New York, NY, USA: ACM Press.

  25. Larrosa, J. (2002). Node and arc consistency in weighted csp. In AAAI-2002, Edmonton.

  26. Liu, J., & Sycara, K. P. (1995). Exploiting problem structure for distributed constraint optimization. In ICMAS.

  27. Maheswaran, R., Tambe, M., Bowring, E., Pearce, J., & Varakantham, P. (2004). Taking DCOP to the real world: Efficient complete solutions for distributed event scheduling. In AAMAS.

  28. Marcellino, F. M., Omar, N., & Moura, A. V. (2007). The planning of the oil derivatives transportation by pipelines as a distributed constraint optimization problem. In IJCAI-DCR Workshop, India.

  29. Modi, P., & Veloso, M. (2005). Bumping strategies for the multiagent agreement problem. In AAMAS.

  30. Modi, P. J., Shen, W.-M., Tambe, M., & Yokoo, M. (2005). ADOPT: Asynchronous distributed constraint optimization with quality guarantees. AIJ, 161.

  31. Modi, P. J., Tambe, M., Shen, W.-M., & Yokoo, M. (2002). A general-purpose asynchronous algorithm for distributed constraint optimization. In Distributed Constraint Reasoning, Proc. of the AAMAS’02 Workshop, Bologna: AAMAS.

  32. Neystadt, J., & Har’El, N. (1997). Israeli internet guide (iguide). http://www.iguide.co.il/isp-sum.htm.

  33. Petcu, A., & Faltings, B. (2005). Approximations in distributed optimization. In Principles and Practice of Constraint Programming CP 2005.

  34. Petcu, A., & Faltings, B. (2005). A scalable method for multiagent constraint optimization. In IJCAI.

  35. Petcu, A., & Faltings, B. (2006). Distributed generator maintenance scheduling. In Proceedings of the First International ICSC Symposium on Artificial Intelligence in Energy Systems and Power: AIESP’06. Madeira, Portugal.

  36. Petcu, A., & Faltings, B. (2006). ODPOP: an algorithm for open/distributed constraint optimization. In AAAI.

  37. Ringwelski, G., & Hamadi, Y. (2005). Multi-directional distributed search with aggregation. In IJCAI-DCR.

  38. Schiex, T., Fargier, H., & Verfaillie, G. (1995). Valued constraint satisfaction problems: Hard and easy problems. In Procs. IJCAI’95 (pp. 631–637).

  39. Silaghi, M.-C. (2002) Asynchronously solving distributed problems with privacy requirements. PhD Thesis 2601, (EPFL). http://www.cs.fit.edu/~msilaghi/teza.

  40. Silaghi, M.-C. (2003). Asynchronous PFC-MRDAC  ± ADOPT_ consistency-maintenance in ADOPT_. In IJCAI-DCR.

  41. Silaghi, M.-C. (2003). Howto: Asynchronous PFC-MRDAC—optimization in distributed constraint problems +/-ADOPT_. In IAT. Halifax.

  42. Silaghi, M.-C. (2006). Framework for modeling reordering heuristics for asynchronous backtracking. In IAT.

  43. Silaghi M.-C., Faltings B. (2004) Asynchronous aggregation and consistency in distributed constraint satisfaction. Artificial Intelligence 161(1–2): 25–53

    MathSciNet  Google Scholar 

  44. Silaghi, M.-C., Landwehr, J., & Larrosa, J. B. (2004). Vol. 112 of Frontiers in Artificial Intelligence and Applications, chapter Asynchronous Branch & Bound and A* for DisWCSPs with heuristic function based on consistency-maintenance. IOS Press.

  45. Silaghi, M.-C., Sam-Haroud, D., & Faltings, B. (2000). Asynchronous search with aggregations. In Proceedings of AAAI2000 (pp. 917–922). Austin.

  46. Silaghi, M.-C., Sam-Haroud, D., & Faltings, B. (2001). ABT with asynchronous reordering. In IAT.

  47. Silaghi, M.-C., Sam-Haroud, D., & Faltings, B. (2001). Hybridizing ABT and AWC into a polynomial space, complete protocol with reordering. Tech. rep. #01/364, EPFL.

  48. Silaghi, M.-C., Sam-Haroud, D., & Faltings, B. (2000). Maintaining hierarchical distributed consistency. In Workshop on Distributed CSPs, 6th International Conference on CP 2000, Singapore.

  49. Silaghi, M.-C., & Yokoo, M. (2006). Nogood-based asynchronous distributed optimization. In AAMAS.

  50. Stallman R.M., Sussman G.J. (1977) Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence 9: 135–193

    Article  MATH  Google Scholar 

  51. Sultanik, E., Modi, P. J., & Regli, W. (2006). Constraint propagation for domain bounding in distributed task scheduling. In CP.

  52. Walsh, T. (2007). Traffic light scheduling: a challenging distributed constraint optimization problem. In DCR, India.

  53. Yeoh, W., Koenig, S., & Felner, A. (2007). Idb-adopt : A depth first search dcop algorithm. In IJCAI DCR Workshop.

  54. Yokoo, M. (1993). Constraint relaxation in distributed constraint satisfaction problem. In ICDCS’93 (pp. 56–63).

  55. Yokoo, M., Durfee, E. H., Ishida, T., & Kuwabara, K. (1992) Distributed constraint satisfaction for formalizing distributed problem solving. In ICDCS (pp. 614–621).

  56. Yokoo M., Durfee E.H., Ishida T., Kuwabara K. (1998) The distributed constraint satisfaction problem: Formalization and algorithms. IEEE TKDE 10(5): 673–685

    Google Scholar 

  57. Yokoo, M., & Hirayama, K. (1998). Distributed constraint satisfaction algorithm for complex local problems. In Proceedings of 3rd ICMAS’98 (pp. 372–379).

  58. Zivan, R., & Meisels, A. (2005). Dynamic ordering for asynchronous backtracking on discsps. In CP (pp. 161–172).

Download references

Author information

Authors and Affiliations

  1. Florida Institute of Technology, Melbourne, FL, USA

    Marius C. Silaghi

  2. Kyushu University, Fukuoka City, Fukuoka, Japan

    Makoto Yokoo

Authors
  1. Marius C. Silaghi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Makoto Yokoo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Marius C. Silaghi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Silaghi, M.C., Yokoo, M. ADOPT-ing: unifying asynchronous distributed optimization with asynchronous backtracking. Auton Agent Multi-Agent Syst 19, 89–123 (2009). https://doi.org/10.1007/s10458-008-9069-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10458-008-9069-2

Keywords

Search

Navigation