×

Nogood-based asynchronous forward checking algorithms. (English) Zbl 1327.90113

Summary: We propose two new algorithms for solving Distributed Constraint Satisfaction Problems (DisCSPs). The first algorithm, AFC-ng, is a nogood-based version of Asynchronous Forward Checking (AFC). Besides its use of nogoods as justification of value removals, AFC-ng allows simultaneous backtracks going from different agents to different destinations. The second algorithm, Asynchronous Forward Checking Tree (AFC-tree), is based on the AFC-ng algorithm and is performed on a pseudo-tree ordering of the constraint graph. AFC-tree runs simultaneous search processes in disjoint problem subtrees and exploits the parallelism inherent in the problem. We prove that AFC-ng and AFC-tree only need polynomial space. We compare the performance of these algorithms with other DisCSP algorithms on random DisCSPs and instances from real benchmarks: sensor networks and distributed meeting scheduling. Our experiments show that AFC-ng improves on AFC and that AFC-tree outperforms all compared algorithms, particularly on sparse problems.

MSC:

90C09 Boolean programming

Software:

SensorDCSP; DisChoco
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abu-Amara, H.H. (1988). Fault-tolerant distributed algorithm for election in complete networks. IEEE Transactions on Computers, 37, 449-453. · Zbl 0709.94511 · doi:10.1109/12.2189
[2] Béjar, R., Domshlak, C., Fernández, C., Gomes, C., Krishnamachari, B., Selman, B., Valls, M. (2005). Sensor networks and distributed csp: communication, computation and complexity. Artificial Intelligence, 161, 117-147. · Zbl 1132.68688 · doi:10.1016/j.artint.2004.09.002
[3] Bessiere, C., Maestre, A., Brito, I., Meseguer, P. (2005). Asynchronous backtracking without adding links: a new member in the ABT family. Artificial Intelligence, 161, 7-24. · Zbl 1132.68690 · doi:10.1016/j.artint.2004.10.002
[4] Bessiere, C., & Régin, J.C. (1996). MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems. In Proceedings of CP’96 (pp. 61-75). · Zbl 0513.68066
[5] Brito, I., & Meseguer, P. (2008). Improving ABT performance by adding synchronization points. In Recent advances in constraints, lecture notes in computer science (Vol. 5129, pp. 47-61). · Zbl 1162.68650
[6] Chandy, K.M., & Lamport, L. (1985). Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems, 3(1), 63-75. · doi:10.1145/214451.214456
[7] Chechetka, A., & Sycara, K. (2005). A decentralized variable ordering method for distributed constraint optimization. Tech. Rep. CMU-RI-TR-05-18, Robotics Institute, Carnegie Mellon University.
[8] Chechetka, A., & Sycara, K. (2006). No-commitment branch and bound search for distributed constraint optimization. In Proceedings of AAMAS’06 (pp. 1427-1429). · Zbl 1118.68158
[9] Cheung, T.Y. (1983). Graph traversal techniques and the maximum flow problem in distributed computation. IEEE Transactions on Software Engineering, 9(4), 504-512. · Zbl 0513.68066 · doi:10.1109/TSE.1983.234958
[10] Chong, Y.L., & Hamadi, Y. (2006). Distributed log-based reconciliation. In Proceedings of ECAI’06 (pp. 108-112). · Zbl 1132.68712
[11] Collin, Z., Dechter, R., Katz, S. (1991). On the feasibility of distributed constraint satisfaction. In Proceedings of IJCAI’91 (pp. 318-324). · Zbl 0747.68065
[12] Dechter, R. (1990). Enhancement schemes for constraint processing: backjumping, learning, and cutset decomposition. Artificial Intelligence, 41(3), 273-312. · Zbl 0947.65026 · doi:10.1016/0004-3702(90)90046-3
[13] Dechter, R. (1992). Constraint networks (survey). In Shapiro, S.C. (Ed.) Encyclopedia of artificial intelligence (Vol. 1, pp. 276-285).
[14] Freuder, E.C., & Quinn, M.J. (1985). Taking advantage of stable sets of variables in constraint satisfaction problems. In Proceedings of IJCAI’85 (pp. 1076-1078).
[15] Gaschnig, J. (1978). Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems. In Proceedings of the 2nd Canadian conference on artificial intelligence (pp. 268-277).
[16] Ginsberg, M.L. (1993). Dynamic backtracking. Journal of Artificial Intelligence Research, 1, 25-46. · Zbl 0900.68179
[17] Haralick, R.M., & Elliott, G.L. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14(3), 263-313. · doi:10.1016/0004-3702(80)90051-X
[18] Hirayama, K., & Yokoo, M. (2000). The effect of nogood learning in distributed constraint satisfaction. In Proceedings of ICDCS’00 (pp. 169-177). · Zbl 0513.68066
[19] Jung, H., Tambe, M., Kulkarni, S. (2001). Argumentation as distributed constraint satisfaction: applications and results. In Proceedings of AGENTS’01 (pp. 324-331).
[20] Léauté, T., & Faltings, B. (2011). Coordinating logistics operations with privacy guarantees. In Proceedings of the IJCAI’11 (pp. 2482-2487). · Zbl 0709.94511
[21] Lynch, N.A. (1997). Distributed algorithms. Morgan Kaufmann Series. · Zbl 1132.68688
[22] Maheswaran, R.T., Tambe, M., Bowring, E., Pearce, J.P., Varakantham, P. (2004). Taking DCOP to the real world: Efficient complete solutions for distributed multi-event scheduling. In: Proceedings of AAMAS’04.
[23] Meisels, A., & Lavee, O. (2004). Using additional information in DisCSP search. In Proceedings of DCR’04.
[24] Meisels, A., & Zivan, R. (2003). Asynchronous forward-checking for distributed CSPs. In Frontiers in artificial intelligence and applications. · Zbl 1118.68158
[25] Meisels, A., & Zivan, R. (2007). Asynchronous forward-checking for DisCSPs. Constraints, 12(1), 131-150. · Zbl 1118.68158 · doi:10.1007/s10601-006-9013-5
[26] Modi, P.J., Shen, W.M., Tambe, M., Yokoo, M. (2003). An asynchronous complete method for distributed constraint optimization. In Proceedings of AAMAS’03 (pp. 161-168).
[27] Nguyen, V., Sam-Haroud, D., Faltings, B. (2005). Dynamic distributed backjumping. In Recent advances in constraints (Vol. 3419, pp. 71-85). · Zbl 1078.68757
[28] Petcu, A., & Faltings, B. (2004). A value ordering heuristic for distributed resource allocation. In Proceedings of joint annual workshop of ERCIM/CoLogNet on CSCLP’04 (pp. 86-97). · Zbl 1078.68759
[29] Petcu, A., & Faltings, B. (2005). DPOP: A scalable method for multiagent constraint optimization. In Proceedings of IJCAI’05 (pp. 266-271).
[30] Petcu, A., & Faltings, B. (2006). ODPOP: An algorithm for open/distributed constraint optimization. In Proceedings of AAAI’06 (pp. 703-708).
[31] Prosser, P. (1993). Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence, 9, 268-299. · doi:10.1111/j.1467-8640.1993.tb00310.x
[32] Silaghi, M.C. (2006). Generalized dynamic ordering for asynchronous backtracking on DisCSPs. In Proceedings of DCR’06.
[33] Silaghi, M.C., & Faltings, B. (2005). Asynchronous aggregation and consistency in distributed constraint satisfaction. Artificial Intelligence, 161, 25-53. · Zbl 1132.68712 · doi:10.1016/j.artint.2004.10.003
[34] Wahbi, M., Ezzahir, R., Bessiere, C., Bouyakhf, E.H. (2011). DisChoco 2: A platform for distributed constraint reasoning. In Proceedings of DCR’11 (pp. 112-121). http://www.lirmm.fr/coconut/dischoco/.
[35] Wallace, R.J., & Freuder, E.C. (2002). Constraint-based multi-agent meeting scheduling: Effects of agent heterogeneity on performance and privacy loss. In Proceedings of DCR’02 (pp. 176-182).
[36] Yeoh, W., Felner, A., Koeing, S. (2007). BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm. In Proceedings of workshop on distributed constraint reasoning, (DCR’07). · Zbl 1191.68733
[37] Yokoo, M. (2000). Algorithms for distributed constraint satisfaction problems: a review. Journal of AAMAS, 3(2), 185-207.
[38] Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K. (1992). Distributed constraint satisfaction for formalizing distributed problem solving. In Proceedings of 12th IEEE int’l conf. distributed computing systems (pp. 614-621).
[39] Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K. (1998). The distributed constraint satisfaction problem: Formalization and algorithms. IEEE Transactions on Knowledge and Data Engineering, 10, 673-685. · doi:10.1109/69.729707
[40] Zivan, R., & Meisels, A. (2003). Synchronous vs asynchronous search on DisCSPs. In Proceedings of EUMAS’03. · Zbl 1103.68117
[41] Zivan, R., & Meisels, A. (2006). Dynamic ordering for asynchronous backtracking on DisCSPs. Constraints, 11(2-3), 179-197. · Zbl 1103.68117 · doi:10.1007/s10601-006-8062-0
[42] Zivan, R., & Meisels, A. (2006). Message delay and DisCSP search algorithms. Annals of Mathematics and Artificial Intelligence, 46(4), 415-439. · Zbl 1107.68106 · doi:10.1007/s10472-006-9033-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.