Nogood based asynchronous distributed optimization (ADOPT ng)

ABSTRACT

This work proposes an asynchronous algorithm for solving Distributed Constraint Optimization problems (DCOPs) using a new kind of nogoods, namely valued nogoods. The proposed technique is an extension of the asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning, leading to important speed-up. Valued nogoods are an extension of classic nogoods that associates each nogood with a threshold 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). Among the mentioned techniques, DPOP performs very well for the chosen metric (requiring a number of such sequential messages linear in the number of agents), but in general has exponential space requirements. DisAO and ADOPT have the advantage of needing only polynomial space. ADOPT has the property of maintaining the initial distribution of the problem. ADOPT needs a preprocessing step consisting of computing a depth first search (DFS) tree on the agent graph. We show that valued nogoods reduce the practical importance/need of this preprocessing since independent subproblems are now dynamically detected and exploited.

REFERENCES

• 1: Syed Ali , Sven Koenig , Milind Tambe, Preprocessing techniques for accelerating the DCOP algorithm ADOPT, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082631]
• 2: Christian Bessière , Arnold Maestre , Ismel Brito , Pedro Meseguer, Asynchronous backtracking without adding links: a new member in the ABT family, Artificial Intelligence, v.161 n.1-2, p.7-24, January 2005 [doi>10.1016/j.artint.2004.10.002]
• 3: Z. Collin, R. Dechter, and S. Katz. Self-stabilizing distributed constraint satisfaction. Chicago Journal of Theoretical Computer Science, 2000.
• 4: J. Davin and P. J. Modi. Impact of problem centralization in distributed cops. In DCR, 2005.
• 5: Rina Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 6: M. L. Ginsberg. Dynamic backtracking. Journal of AI Research, 1, 1993.
• 7: K. Hirayama and M. Yokoo. Distributed partial constraint satisfaction problem. In Proceedings of the Conference on Constraint Processing (CP-97), LNCS 1330, pages 222--236, 1997.
• 8: Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
• 9: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, v.161 n.1-2, p.149-180, January 2005 [doi>10.1016/j.artint.2004.09.003]
• 10: P. J. Modi, M. Tambe, W.-M. Shen, and M. Yokoo. A general-purpose asynchronous algorithm for distributed constraint optimization. In Distributed Constraint Reasoning, Proc. of the AAMAS'02 Workshop, Bologna, July 2002. AAMAS.
• 11: A. Petcu and B. Faltings. Approximations in distributed optimization. In Principles and Practice of Constraint Programming CP 2005, 2005.
• 12: A. Petcu and B. Faltings. A scalable method for multiagent constraint optimization. In IJCAI, 2005.
• 13: M.-C. Silaghi. Asynchronously Solving Distributed Problems with Privacy Requirements. PhD Thesis 2601, (EPFL), June 27, 2002. http://www.cs.fit.edu/~msilaghi/teza.
• 14: Marius-Calin Silaghi, HOWTO: Asynchronous PFC-MRDAC -Optimization in Distributed Constraint Problems±Adopt, Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology, p.490, October 13-17, 2003
• 15: M.-C. Silaghi and B. Faltings. A comparison of DisCSP algorithms with respect to privacy. In AAMAS-DCR, 2002.
• 16: M.-C. Silaghi, J. Landwehr, and J. B. Larrosa. volume 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, 2004.
• 17: Marius C. Silaghi , Debasis Mitra, Distributed Constraint Satisfaction and Optimization with Privacy Enforcement, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference on (IAT'04), p.531-535, September 20-24, 2004 [doi>10.1109/IAT.2004.51]
• 18: Marius-Calin Silaghi , Djamila Sam-Haroud , Boi Faltings, Consistency Maintenance for ABT, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.271-285, November 26-December 01, 2001
• 19: M.-C. Silaghi, D. Sam-Haroud, and B. Faltings. Hybridizing ABT and AWC into a polynomial space, complete protocol with reordering. Technical Report #01/364, EPFL, May 2001.
• 20: R. M. Stallman and G. J. Sussman. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence, 9:135--193, 1977.
• 21: R. Wallace and M.-C. Silaghi. Using privacy loss to guide decisions in distributed CSP search. In FLAIRS'04, 2004.
• 22: M. Yokoo. Constraint relaxation in distributed constraint satisfaction problem. In ICDCS'93, pages 56--63, June 1993.
• 23: M. Yokoo, E. H. Durfee, T. Ishida, and K. Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In ICDCS, pages 614--621, June 1992.
• 24: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707]
• 25: M. Yokoo , K. Hirayama, Distributed Constraint Satisfaction Algorithm for Complex Local Problems, Proceedings of the 3rd International Conference on Multi Agent Systems, p.372, July 03-07, 1998
• 26: Makoto Yokoo , Koutarou Suzuki , Katsutoshi Hirayama, Secure Distributed Constraint Satisfaction: Reaching Agreement without Revealing Private Information, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.387-401, September 09-13, 2002
• 27: Weixiong Zhang , Lars Wittenburg, Distributed breakout revisited, Eighteenth national conference on Artificial intelligence, p.352-357, July 28-August 01, 2002, Edmonton, Alberta, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms

Keywords:
distributed constraint optimization