Cluster Tree Elimination for Distributed Constraint Optimization with Quality Guarantees

• Autorzy: Brito I. , Meseguer P.
• Języki publikacji: EN

Abstrakty

EN

Some distributed constraint optimization algorithms use a linear number of messages in the number of agents, but of exponential size. This is often the main limitation for their practical applicability. Here we present some distributed algorithms for these problems when they are arranged in a tree of agents. The exact algorithm, DCTE, computes the optimal solution but requires messages of size exp(s), where s is a structural parameter. Its approximate version, DMCTE(r), requires smaller messages of size exp(r), r < s, at the cost of computing approximate solutions. It provides a cost interval that bounds the error of the approximation. Using the technique of cost function filtering, we obtain DMCTEf(r). Combining cost function filtering with bound reasoning, we propose DIMCTEf, an algorithm based on repeated executions of DMCTEf(r) with increasing r. DIMCTEf uses messages of previous iterations to decrease the size of messages in the current iteration, which allows to alleviate their high size. We provide evidences of the benefits of our approach on two benchmarks.

Słowa kluczowe

EN

distributed constraint optimization; distributed cluster-tree elimination; function filtering

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 102, nr 3/4
• Strony: 263--286
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Brito I.

autor

Meseguer P.

• IIIA, CSIC, Campus UAB 08193 Bellaterra, Spain,

Bibliografia

• [1] Bejar R., Fernandez C., Valls M., Domshlak C., Gomes C., Selman S., Krishnamachari B. Sensor networks and distributed CSP: Communication, computation and complexity. Artificial Intelligence, 161:117-147, 2005.
• [2] Bodlaender H. Treewidth: algorithmic techniques and results Proc. MFCS-97, 19-36, 1997.
• [3] Chechetka A., Sycara K. No-commitment branch and bound search for distributed constraint optmization Proc. of AAMAS-06 1427-1429, 2006.
• [4] Dechter R. Bucket elimination:A unifying framework for reasoning. Artificial Intelligence, 113:41-85, 1999.
• [5] Dechter R. Constraint Processing. Morgan Kaufmann, 2003.
• [6] Dechter R., Kask K., Larrosa J. A general scheme for multiple lower bound computation in constraint optimization. Proc. CP-01, 346-360, 2001.
• [7] Gershman A., Meisels A., Zivan R. Asynchronous forward-bounding for distributed constraint optimization Proc. of ECAI-06 103-107, 2006.
• [8] Hirayama K., Yokoo M. Distributed partial constraint satisfaction problem Proc. of CP-97, 222-236, 1997.
• [9] Larrosa J. Node and arc consistency in weighted CSP Proc. of AAAI-02, 48-53, 2002.
• [10] Kask K., Dechter R. Larrosa J., Dechter A. Unifying cluster-tree decompositions for reasoning in graphical models. Artificial Intelligence, 166:165-193, 2005.
• [11] Maheswaran R., Tambe M., Bowring E., Pearce J., Varakantham P. Taking DCOP to the RealWorld: Efficient Complete Solutions for Distributed Multi-Event Scheduling Proc. of AAMAS-04, 310-317, 2004.
• [12] Mailler R., Lesser V. Solving distributed constraint optimization problems using cooperative mediation Proc. of AAMAS-04, 438-445, 2004.
• [13] Meseguer P., Rossi F., Schiex T. Soft constraints Handbook of Constraint Programming Ed van Beek, Rossi, Walsh, 281-328, 2006.
• [14] Modi P. J., Shen W.M., Tambe M., Yokoo M. Adopt: asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161:149-180, 2005.
• [15] Paskin M., Guestrin C., McFadden J. A robust architecture for distributed inference in sensor networks. Proc. of IPSN, 55-62, 2005.
• [16] Perlman R. An algorithm for distributed computation of a spanning tree in an extended LAN. ACM SIGCOMM Computer Communication Review, 44-53, 1985.
• [17] Petcu A. FRODO: A FRamework for Open and Distributed constraint Optimization. Technical Report 2006/001. Swiss Federal Institute of Technology (EPFL) Laussane, Switzerland, 2006.
• [18] Petcu A., Faltings B. A scalable method for multiagent constraint optimization Proc. of IJCAI-05, 266-271, 2005.
• [19] Sanchez M., Larrosa J., Meseguer P. Improving Tree Decomposition Methods with Function Filtering. Proc. of IJCAI-05, 1537-1538, 2005.
• [20] Silaghi M. Yokoo M. Nogood-based Asynchronous Distributed Optimization (ADOPT-ng). Proc. of AAMAS-06, 1389-1396, 2006.
• [21] Verfaillie G., Lemaıtre M., Schiex T. Russian doll search. Proc. of AAAI-96, 181-187, 1996.
• [22] Vinyals M., Rodriguez-Aguilar J.A., Cerquides J. Generalizing DPOP: Action-GDL, a new complete algorithm for DPOPs. Proc. of AAMAS-09, 1239-1240, 2009.
• [23] Wallace R., Freuder E. The Distributed Constraint-based reasoning and privacy/efficiency tradeoffs in multiagent problem solving. Artificial Intelligence, 161:209-227, 2005.
• [24] Yeoh W., Felner A. Koenig S. BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm Proc. of AAMAS-08, 591-598, 2008.
• [25] Yokoo M., Durfee E., Ishida T., Kuwabara K. The Distributed Constraint Satisfaction Problem: Formalization and Algorithms. IEEE Trans. Know. and Data Engin., 10:673-685, 1998.