Abstract
Multi-agent planning can solve various sequential decision problems comprising multiple entities. In contrast to classical planning, the agents are interested in maintaining privacy while planning with each other. Therefore they have to reason about what information they can share. Although privacy is one of the crucial aspects of multi-agent planning, formal and algorithmic treatment of privacy is rather sparse in literature. No domain-independent strong privacy preserving multi-agent planner was proposed so far. Moreover, our recent results indicate that an efficient variant of such planner may not exist at all. Such strong privacy preserving planner would not allow to leak any private information during planning neither directly nor indirectly. Especially the indirect leakage is hard to assess as it can be based on any possible deduction principle from the non-private information along the planning process.
Here, we propose a refined version of a multi-agent planning principle, based on our previous work published as the conference version of this paper. The planning principle is designed so that it can get arbitrarily close to the general strong privacy preserving planning for the price of decreased planning efficiency. We have tighten the bounds on the privacy leakage and proved the strong privacy can be achieved by a finite number of additional plans, in contrast to the previous algorithm, where the number had to be infinite in general. We newly illustrate the principle on an additional synthetic planning problem, which shows the general privacy leakage upper bound. As in the previous variant of the algorithm, the strong privacy assurances are under computational tractability assumptions commonly used in secure computation research.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Projected plan-space contains all the solutions of the projected public problem \(\Pi ^{\vartriangleright }\).
References
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 1–10. ACM, New York (1988)
Brafman, R.I.: A privacy preserving algorithm for multi-agent planning and search. In: Yang, Q., Wooldridge, M. (eds.) Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, 25–31 July 2015, pp. 1530–1536. AAAI Press (2015)
Brafman, R.I., Domshlak, C.: From one to many: planning for loosely coupled multi-agent systems. In: Proceedings of the ICAPS 2008, pp. 28–35 (2008)
Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theor. 22(6), 644–654 (1976)
Guanciale, R., Gurov, D., Laud, P.: Private intersection of regular languages. In: Miri, A., Hengartner, U., Huang, N., Jøsang, A., García-Alfaro, J. (eds.) 2014 Twelfth Annual International Conference on Privacy, Security and Trust, Toronto, ON, Canada, 23–24 July 2014, pp. 112–120. IEEE (2014). https://doi.org/10.1109/PST.2014.6890930
Jarecki, S., Liu, X.: Fast secure computation of set intersection. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 418–435. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_26
Maliah, S., Shani, G., Brafman, R.: Online macro generation for privacy preserving planning. In: Proceedings of the 26th International Conference on Automated Planning and Scheduling, ICAPS 2016 (2016)
Maliah, S., Shani, G., Stern, R.: Collaborative privacy preserving multi-agent planning. In: Proceedings of the AAMAS 2016, pp. 1–38 (2016)
Nissim, R., Brafman, R.I.: Multi-agent A* for parallel and distributed systems. In: Proceedings of AAMAS 2012, pp. 1265–1266 (2012)
Nissim, R., Brafman, R.I.: Distributed heuristic forward search for multi-agent planning. JAIR 51, 293–332 (2014)
Pinkas, B., Schneider, T., Segev, G., Zohner, M.: Phasing: Private set intersection using permutation-based hashing. In: 24th USENIX Security Symposium (USENIX Security 15), pp. 515–530. USENIX Association, Washington, D.C. (2015)
Štolba, M., Tožička, J., Komenda, A.: Secure multi-agent planning. In: Proceedings of the International Workshop on PrAISe (2016)
Stolba, M., Tozicka, J., Komenda, A.: Secure multi-agent planning algorithms. ECAI 2016, 1714–1715 (2016)
Stolba, M., Tozicka, J., Komenda, A.: The limits of strong privacy preserving multi-agent planning. In: Proceedings of the 27th International Conference on Automated Planning and Scheduling. ICAPS 2017 (2017). To appear
Torreño, A., Onaindia, E., Sapena, O.: FMAP: distributed cooperative multi-agent planning. AI 41(2), 606–626 (2014)
Tožička, J., Jakubův, J., Komenda, A., Pěchouček, M.: Privacy-concerned multiagent planning. KAIS, pp. 1–38 (2015)
Tozicka, J., Komenda, A., Stolba, M.: \(\epsilon \)-strong privacy preserving multiagent planner by computational tractability. In: van den Herik, H.J., Rocha, A.P., Filipe, J. (eds.) Proceedings of the 9th International Conference on Agents and Artificial Intelligence. ICAART 2017, vol. 1, Porto, Portugal, 24–26 February 2017, pp. 51–57. SciTePress (2017). https://doi.org/10.5220/0006176400510057
Van Der Krogt, R.: Quantifying privacy in multiagent planning. Multiagent Grid Syst. 5(4), 451–469 (2009)
Štolba, M., Komenda, A.: Relaxation heuristics for multiagent planning. In: 24th International Conference on Automated Planning and Scheduling (ICAPS), pp. 298–306 (2014)
Yao, A.C.: Protocols for secure computations. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp. 160–164. SFCS 1982. IEEE Computer Society, Washington, DC (1982)
Yao, A.C.C.: How to generate and exchange secrets. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS 1986, pp. 162–167. IEEE Computer Society, Washington, DC (1986)
Acknowledgments
This research was supported by the Czech Science Foundation (no. 15-20433Y).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Komenda, A., Tožička, J., Štolba, M. (2018). \({\upvarepsilon }\)-Strong Privacy Preserving Multi-agent Planning. In: van den Herik, J., Rocha, A., Filipe, J. (eds) Agents and Artificial Intelligence. ICAART 2017. Lecture Notes in Computer Science(), vol 10839. Springer, Cham. https://doi.org/10.1007/978-3-319-93581-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-93581-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93580-5
Online ISBN: 978-3-319-93581-2
eBook Packages: Computer ScienceComputer Science (R0)