Integrating domain and constraint privacy reasoning in the distributed stochastic algorithm with breakouts. (English) Zbl 07473193

Vion, Julien; Mandiau, René; Piechowiak, Sylvain; Silaghi, Marius

Ann. Math. Artif. Intell. 90, No. 1, 31-73 (2022).

Summary: Privacy has traditionally been a major motivation of distributed problem solving. One popular approach to enable privacy in distributed environments is to implement complex cryptographic protocols. In this paper, we propose a different, orthogonal approach, which is to control the quality and the quantity of publicized data. We consider the Open Constraint Programming model and focus on algorithms that solve Distributed Constraint Optimization Problems (DCOPs) using a local search approach. Two such popular algorithms exist to find good solutions to DCOP: DSA and GDBA. In this paper, we propose DSAB, a new algorithm that merges ideas from both algorithms to allow extensive handling of constraint privacy. We also study how algorithms behave when solving Utilitarian DCOPs, where utilitarian agents want to reach an agreement while reducing the privacy loss. We experimentally study how the utilitarian approach impacts the quality of the solution and of publicized data.

MSC:

68T42

Agent technology and artificial intelligence

Keywords:

multi-agent system; privacy; distributed constraint problems; local search

Software:

Concrete; GitHub

References:

[1]	Adam, N.R., Worthmann, J.C.: Security-control methods for statistical databases: A comparative study. In: ACM Computing Surveys. issn: 0360-0300. doi:10.1145/76894.76895, vol. 21.4, pp 515-556 (1989)
[2]	Arshad, M., Silaghi, M.C.: Distributed simulated annealing. In: Distributed Constraint Problem Solving and Reasoning in Multi-Agent Systems, p 112 (2004)
[3]	Bonér, J., The Akka Team at Lightbend: Akka: Build powerful reactive, concurrent, and distributed applications more easily. akka.io (2009)
[4]	Brito, I., Meisels, A., Meseguer, P., Zivan, R.: Distributed constraint satisfaction with partially known constraints. In: Constraints, vol. 14.2, pp 199-234 (2009) · Zbl 1186.68434
[5]	Collin, Z., Dechter, R., Katz, S.: On the feasibility of distributed constraint satisfaction. In: Mylopoulos, J., Reiter, R. (eds.) Proceedings of the 12th International Joint Conference on Artificial Intelligence. Sydney, Australia, August 24-30, 1991, pp 318-324. Morgan Kaufmann, Burlington (1991) · Zbl 0747.68065
[6]	Crépin, L., Demazeau, Y., Boissier, O., Jacquenet, F.: Privacy preservation in a decentralized calendar system. In: Proc. 7th Itl Conf on Practical Applications of Agents and Multi-Agent Systems (PAAMS). vol. 55. Advances in Intelligent and Soft Computing, pp 529-537 (2009)
[7]	Doshi, P., Matsui, T., Silaghi, M., Yokoo, M., Zanker, M.: Distributed private constraint optimization. In: Proc. IEEE/WIC/ACM Itl Conf on Intelligent Agent Technology, pp 277-281. IEEE Computer Society, Washington (2008)
[8]	Faltings, B., Léauté, T., Petcu, A.: Privacy guarantees through distributed constraint satisfaction. In: Proc. IEEE/WIC/ACM Itl Conf on Intelligent Agent Technology, vol. 2, pp 350-358. IEEE Computer Society, Washington (2008)
[9]	Faltings, B., Macho-Gonzalez, S.: Open constraint programming. In: Artificial Intelligence 161.1. Distributed Constraint Satisfaction. issn: 0004-3702, pp 181-208 (2005) · Zbl 1132.68699
[10]	Fluckiger, A., Verman, M., Berstein, A.: Improving approximate algorithms for dcops using ranks. In: International Workshop on Optimisation in Multi-Agent Systems, Singapore (2016)
[11]	Freuder, E.C., Minca, M., Wallace, R.J.: Privacy/efficiency tradeoffs in distributed meeting scheduling by constraint-based agents. In: IJCAI Workshop on Distributed Constraint Reasoning, pp. 63-72 (2001)
[12]	Galinier, P., Hao, J. K.: A general approach for constraint solving by local search. In: Journal of Mathematical Modelling and Algorithms 3, vol. 1, pp 73-88 (2004) · Zbl 1076.68071
[13]	Greenstadt, R., Grosz, B., Smith, M.D.: SSDPOP: Improving the privacy of DCOP with secret sharing. In: Proc. of the 6th Itl joint conference on Autonomous agents and multiagent systems. IFAAMAS, p 171 (2007)
[14]	Greenstadt, R., Pearce, J.P., Tambe, M.: Analysis of privacy loss in distributed constraint optimization. In: Proc 21st Nat. Conf. on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conf, pp 647-653. AAAI Press (2006)
[15]	Grinshpoun, T.: When You Say (DCOP) Privacy, What Do Mean? - Categorization of DCOP Privacy and Insights on Internal Constraint Privacy. In: Joaquim, F., Fred, A.L.N. (eds.) Proc. of the 4Th Itl Conference on Agents and Artificial Intelligence (ICAART), pp 380-386. SciTePress, Portugal (2012)
[16]	Grinshpoun, T., Grubshtein, A., Zivan, R., Netzer, A., Meisels, A.: Asymmetric Distributed Constraint Optimization Problems. In: Journal of Artificial Intelligence Research, vol. 47, pp 613-647 (2013) · Zbl 1269.68101
[17]	Grinshpoun, T., Tassa, T.: P-SyncBB: A privacy preserving branch and bound dcop algorithm. In: Journal of Artificial Intelligence Research (JAIR), vol. 57, pp 621-660 (2016) · Zbl 1401.68289
[18]	Grinshpoun, T., Tassa, T., Levit, V., Zivan, R.: Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs. In: Artificial Intelligence, vol. 266, pp 27-50 (2019) · Zbl 1478.68321
[19]	Hamadi, Y., Bessiere, C., Quinqueton, J.: Backtracking in Distributed Constraint Networks. In: Proc. of 13Th European Conf. on Artificial Intelligence (ECAI). Brighton, UK, pp 219-223 (1998)
[20]	Hebrard, E., Marx, D., O’Sullivan, B., Razgon, I.: Soft constraints of difference and equality. In: Journal of Artificial Intelligence Research. issn: 1076-9757, vol. 41.2, pp 97-130 (2011) · Zbl 1218.90173
[21]	Hewitt, C., Bishop, P., Steiger, R.: A universal modular ACTOR formalism for artificial intelligence (1973)
[22]	Hirayama, K., Yokoo, M.: Distributed Partial Constraint Satisfaction Problem, Principles and Practice of Constraint Programming -. In: CP97, Third International Conference, Linz, Austria, October 29 - November 1 1997 Proceedings. Ed. by Gert Smolka. vol. 1330 Lecture Notes in Computer Science, pp 222-236. Springer (1997)
[23]	Hirayama, K., Yokoo, M.: The distributed breakout algorithms. In: Artificial Intelligence, vol. 161.1-2, pp 89-115 (2005) · Zbl 1132.68701
[24]	Léauté, T., Faltings, B.: Protecting privacy through distributed computation in multi-agent decision making. In: Journal Artificial Intelligence Research (JAIR), vol. 47, pp 649-695 (2013) · Zbl 1270.68273
[25]	Maheswaran, R.T., Pearce, J.P., Tambe, M.: Distributed algorithms for DCOP: A graphical-game-based approach. In: Proceedings of ISCA 17th PDCS, pp 432-439 (2004)
[26]	Mairy, J.-B., Deville, Y., Lecoutre, C.: The smart table constraint. In: Michel, L. (ed.) Proc. 12th CPAIOR. isbn: 978-3-319-18008-3, pp 271-287. Springer International Publishing, New York (2015) · Zbl 1464.90081
[27]	Minton, S., Johnston, M. D., Philips, A. B., Laird, P.: Minimizing conicts: A heuristic repair method for constraint-satisfaction and scheduling problems. In: Artificial Intelligence, vol. 58.1-3, pp 161-205 (1992) · Zbl 0782.90054
[28]	Morris, P.: The breakout method for escaping from local minima. In: Proceedings of AAAI’93, pp 40-45 (1993)
[29]	Okamoto, S., Zivan, R., Nahon, A.: Distributed Breakout: Beyond Satisfaction. In: Proc. 25th IJCAI, pp 447-453 (2016)
[30]	Petcu, A, Faltings, B: A scalable method for multiagent constraint optimization. In: Kaelbling, LP, Saffiotti, A (eds.) IJCAI-05, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, Edinburgh, Scotland, UK, July 30 - August 5, 2005, pp 266-271. Professional Book Center (2005)
[31]	Savaux, J., Vion, J., Piechowiak, S., Mandiau, R., Matsui, T., Hirayama, K., Yokoo, M., Elmane, S., Silaghi, M.: Privacy stochastic games in distributed constraint reasoning. In: Annals of Mathematics and Artificial Intelligence, vol. 88.7, pp 691-715 (2020) · Zbl 1460.68121
[32]	Savaux, J., Vion, J., Piechowiak, S., Mandiau, R., Matsui, T., Hirayama, K., Yokoo, M., Elmane, S., Silaghi, M.: Utilitarian approach to privacy in distributed constraint optimization problems. In: Proc. 30th FLAIRS, pp 454-459 (2017) · Zbl 1460.68121
[33]	Silaghi, M., Mitra, D.: Distributed constraint satisfaction and optimization with privacy enforcement. In: Intelligent Agent Technology (IAT), pp 531-535. IEEE (2004)
[34]	Sweeney, L.: K-anonymity: A model for protecting privacy. In: International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. issn: 0218-4885. doi:10.1142/S0218488502001648, vol. 10.5, pp 557-570 (2002) · Zbl 1085.68589
[35]	Tassa, T., Zivan, R., Grinshpoun, T.: Privacy preserving implementation of the max-sum algorithm and its variances. In: JAIR, vol. 59, pp 311-349 (2017) · Zbl 1418.68082
[36]	Vion, J.: Concrete: A CSP Solving API for the JVM. http://github.com/concretecp(2006)
[37]	Vion, J., Mandiau, R., Piechowiak, S., Silaghi, M.C.: Privacy for the distributed stochastic algorithm with breakouts. In: Proc. Itl Symposium on Artificial Intelligence and Mathematics (ISAIM) (2020) · Zbl 1460.68121
[38]	Wallace, R.J., Freuder, E.C.: Anytime Algorithms for Constraint Satisfaction and SAT Problems. In: ACM SIGART Bulletin, vol. 7.2, pp 7-10 (1996)
[39]	Walsh, T.: Stochastic constraint programming. In: Proceedings of the 15th european conference on artificial intelligence, pp 111-115. IOS Press (2002)
[40]	Yokoo, M., Durfee, E.H., Ishida, T., Kuwabara, K.: The distributed constraint satisfaction problem: formalization and algorithms. In: IEEE Transactions on Knowledge and Data Engineering, vol. 10.5, pp 673-685 (1998)
[41]	Yokoo, M., Hirayama, K.: Distributed breakout algorithm for solving distributed constraint satisfaction problems. In: Proc. of the 2nd Itl Conf on Multi-Agent Systems, pp 401-408. AAAI Press (1996)
[42]	Zhang, W., Wang, G., Wittenburg, L.: Distributed stochastic search for constraint satisfaction and optimization: Parallelism, phase transitions and performance. In: Proceedings of AAAI Workshop on Probabilistic Approaches in Search. Alberta, Canada (2002)
[43]	Zhang, W., Wang, G., Xing, Z., Wittenburg, L.: Distributed stochastic search and distributed breakout: Properties, comparison and applications to constraint optimization problems in sensor networks. In: Artificial Intelligence, vol. 161.1-2, pp 55-87 (2005) · Zbl 1132.68718
[44]	Zivan, R., Okamoto, S., Peled, H.: Explorative anytime local search for distributed constraint optimization. In: Artificial Intelligence, vol. 212, pp 1-26 (2014) · Zbl 1405.68334