Abstract
Privacy preservation has become one of the crucial research topics in multi-agent planning. A number of techniques to preserve private information throughout the planning process have emerged. One major difficulty of such research is the comparison of properties related to privacy among such techniques. A metric allowing for comparison of such privacy preservation was introduced only recently, having a number of drawbacks such as prohibitive computational complexity. In this work we strengthen the theoretical foundations and simplify the metric in order to be practically usable. Moreover, we test the usability of the metric in an analysis of various techniques in multi-agent heuristic computation and search, determining which are the most beneficial in terms of privacy preservation. We also evaluate the techniques in terms of the classical IPC score to assess their impact on the overall planning performance. The results are somewhat surprising and show that extracting any privacy-related information even from the simplest variant of heuristic search is a very complicated task. Existing techniques such as distributed heuristic and sending only relevant states is shown to reduce the privacy leakage even more.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Availability of data and material
Notes
http://github.com/stolba/privacy-analysis
Abbreviations
- \({\mathcal {A}}\) :
-
Set of agents
- \(\alpha _i \in {\mathcal {A}}\) :
-
Agent i
- \({\mathcal {M}}=\{\Pi _{i}\}_{i=1}^{|{\mathcal {A}}|}\) :
-
Set of agents’ problems
- \({\mathcal {V}}^{\mathsf {pub}}\) :
-
Public variables
- \({\mathcal {V}}^{\mathsf {priv}_{i}}\) :
-
Private variables of agent i
- \(\mathsf {dom}(V)\) :
-
Domain (values) of the variable V
- \({\mathcal {O}}_{i}={\mathcal {O}}^{\mathsf {pub}_{i}}\cup {\mathcal {O}}^{\mathsf {priv}_{i}}\) :
-
Actions of agent i, public, private
- \({\mathcal {V}}_{i}={\mathcal {V}}^{\mathsf {pub}}\cup {\mathcal {V}}^{\mathsf {priv}_{i}}\) :
-
All variables of agent i
- \(\Pi _{i}=\left\langle {\mathcal {V}}_{i},{\mathcal {O}}_{i},s_{I}^{i},s_{\star }\right\rangle\) :
-
Problem of agent i
- \({\mathcal {O}}^{\vartriangleright }_{i}=\{a^{\triangleright }|a\in {\mathcal {O}}^{\mathsf {pub}_{i}}\}\) :
-
Projected actions of agent i
- \(\Pi _{i}^{\triangleright }=\left\langle {\mathcal {V}}^{\mathsf {pub}},{\mathcal {O}}^{\vartriangleright }_{i},s_{I}^{\triangleright },s_{\star }\right\rangle\) :
-
Projected problem of agent i
- \(a=\left\langle {\mathsf {pre}}(a),{\mathsf {eff}}(a)\right\rangle\) :
-
Action, precondition, effect
- \(a^{\triangleright }=\left\langle {\mathsf {pre}}(a)^{\triangleright },{\mathsf {eff}}(a)^{\triangleright }\right\rangle\) :
-
Projected action
- \({\mathcal {O}}_{a}^{\vartriangleright }\subseteq {\mathcal {O}}^{\mathsf {pub}}_{i}\) :
-
Set of all actions represented by a projection
- s[V]:
-
Value of variable V in (partial) state s
- \(s{[}{\mathcal {V}}'{]}\) :
-
State s restricted to \({\mathcal {V}}'\subseteq {\mathcal {V}}_{i}\)
- \(s^\vartriangleright = s{[}{\mathcal {V}}^{\mathsf {pub}}{]}\) :
-
Public projection of a (partial) state
- \(s'=a\circ s\) :
-
Apply action a in state s resulting in \(s'\)
- \(S^{i}\) :
-
State space of agent i
- \(\delta _{i}:S^{i}\rightarrow {\mathbb {N}}\) :
-
Agent-specific identifier for each state (private part)
- \(m=\left\langle s^{\vartriangleright },\delta _{1}(s),\ldots ,\delta _{n}(s)\right\rangle\) :
-
Message exchanged throughout search
- \(T_{V}\) :
-
Variable transition system of V
- \(T_{a,V}\) :
-
Action transition system of a w.r.t. V
- \(T_{a,V}^{\vartriangleright }\) :
-
Projected transition system of \(a^\vartriangleright\)
- \(T_{V}^n\) :
-
Set of all transition systems of V
- \(X_{V}\subseteq T_{V}^n\) :
-
Transition system property w.r.t. V
- \((v,v')\in T_{V}\) :
-
Edge in transition system, \(v,v'\in \mathsf {dom}(V)\)
- \({\mathsf {ia}}_{V},{\mathsf {nia}}_{V}\) :
-
(not-)init-applicable transition system property w.r.t V
- \(\mathsf {pd}_{V},\mathsf {pi}_{V}\) :
-
Privately-(in)dependent t.s. property w.r.t V
- \(\mathsf {de}_{V},\mathsf {no}_{V}\) :
-
Privately-(non)deterministic t.s. property w.r.t V
- \({\mathsf {ia}},{\mathsf {nia}},\mathsf {pd},\mathsf {pi},\mathsf {de},\mathsf {no}\) :
-
Respective action properties
- \(s^{\vartriangleright }=s'^{\vartriangleright }\) :
-
Publicly equivalent (PE) states
- \(s\,\ntrianglerighteq \,s'\) :
-
Privately different (PD) states
- \(S_{\mathsf {rec}},S_{\mathsf {sen}}\) :
-
Set of received (sent) states
- \(S_{I}\) :
-
Set of states reachable from \(s_{I}\) by agent \(\alpha _i\)
- \(i\mathsf {\text{- }par}:S_{\mathsf {rec}}\rightarrow S_{\mathsf {sen}}\cup \{s_{I}^{\vartriangleright },\bot \}\) :
-
Assigns to each received state \(s^{\vartriangleright }\) its i-parent
- \(\mathsf {ap-res}:{\mathcal {O}}^{\vartriangleright }_{i}\rightarrow 2^{S_{\textsf {rec}}}\) :
-
States possibly resulting from the application of \(a^{\vartriangleright }\)
- \(h,h^{\vartriangleright },g\) :
-
Heuristic, projected heuristic, cost function
- \(\mathsf {prop}:2^{{\mathcal {O}}^{\vartriangleright }_{i}}\rightarrow 2^{\{{\mathsf {ia}},{\mathsf {nia}},\ldots \}}\) :
-
Action to set of properties
- \({\mathcal {O}}^{\vartriangleright }_{p,k}\) :
-
k-th set of proj. actions with a property p
- \(x_{a^\vartriangleright }\in \{0,1\}\) :
-
ILP variable resp. to action \(a^\vartriangleright\)
References
Brafman, R. I. (2015). A privacy preserving algorithm for multi-agent planning and search. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, (IJCAI’15), pp. 1530–1536
Brafman, R. I., Domshlak, C. (2008). From one to many: Planning for loosely coupled multi-agent systems. In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS’08), pp. 28–35.
Edmund, H. D. (1999). Distributed problem solving and planning. In G. Weiß (Ed.), A modern approach to distributed artificial intelligence, chapter 3. The MIT Press.
Fišer, D., Štolba, M., Komenda, A. (2015). MAPlan. In Proceedings of the Competition of Distributed and Multi-Agent Planners (CoDMAP’15), pp. 8–10.
Gerevini, A. E, Lipovetzky, N., Peli, N., Percassi, F., Saetti, A., Serina, I. (2019). Novelty messages filtering for multi agent privacy-preserving plannin. In Twelfth Annual Symposium on Combinatorial Search.
Helmert, M. (2006). The fast downward planning system. Journal of Artificial Intelligence Research, 26, 191–246.
Komenda, A., Stolba, M., & Kovacs, D. L. (2016). The international competition of distributed and multiagent planners (CoDMAP). AI Magazine, 37(3), 109–115.
Maliah, S., Brafman, R. I., Shani, G. (2016). Increased privacy with reduced communication and computation in multi-agent planning. In Proceedings of the 4th Workshop on Distributed and Multi-Agent Planning, DMAP–ICAPS’16, pp. 106–112.
Maliah, S., Shani, G., Brafman, R. I.(2016). Online macro generation for privacy preserving planning. In Proceedings of the 26th International Conference on Automated Planning and Scheduling
Maliah, S., Shani, G., Stern, R. (2016). Stronger privacy preserving projections for multi-agent planning. In Proceedings of the 26th International Conference on Automated Planning and Scheduling, pp. 216–220.
Maliah, S., Shani, G., & Stern, R. (2018). Action dependencies in privacy-preserving multi-agent planning. Autonomous Agents and Multi-Agent Systems, 32(6), 779–821.
Nissim, R., Brafman, R. I. (2012). Multi-agent A* for parallel and distributed systems. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’12), pp. 1265–1266.
Nissim, R., & Brafman, R. I. (2014). Distributed heuristic forward search for multi-agent planning. Journal of Artificial Intelligence Research, 51, 293–332.
Pommerening, F., Helmert, M., Röger, G., Seipp, J. (2015). From non-negative to general operator cost partitioning. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 3335–3341.
Smith, G. (2009). On the foundations of quantitative information flow. In Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures, pp. 288–302.
Štolba, M. (2017). Reveal or hide: Information sharing in multi-agent planning.
Štolba, M., Fišer, D., Komenda, A. (2016). Potential heuristics for multi-agent planning. In Proceedings of the 26th International Conference on Automated Planning and Scheduling, ICAPS’16, pp. 308–316.
Štolba, M., Fišer, D., & Komenda, A. (2019). Privacy leakage of search-based multi-agent planning algorithms. In Proceedings of the International Conference on Automated Planning and Scheduling, 29, 482–490.
Štolba, M., Komenda, A. (2014). Relaxation heuristics for multiagent planning. In Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS’14), pp. 298–306.
Štolba, M., Komenda, A., Kovacs, D. (2016). Competition of distributed and multiagent planners (CoDMAP). In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 4343–4345.
Štolba, M., Tožička, J., Komenda, A. (2017). Quantifying privacy leakage in multi-agent planning. Transactions on Internet Technology (TOIT).
Torreño, A., Onaindia, E., Komenda, A., & Štolba, M. (2017). Cooperative multi-agent planning: A survey. ACM Computing Surveys (CSUR), 50(6), 84.
Tožička, J., Štolba, M., Komenda, A. (2017). The limits of strong privacy preserving multi-agent planning. In Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS’17)
Acknowledgements
This research was supported by the Czech Science Foundation (Grant No. 18-24965Y). The authors acknowledge the support of the OP VVV MEYS funded project
CZ.02.1.01/0.0/0.0/16_019/0000765 “Research Center for Informatics”.
Funding
This research was supported by the Czech Science Foundation (Grant No. 18-24965Y).
Author information
Authors and Affiliations
Contributions
Not applicable
Corresponding author
Ethics declarations
Conflict of interest
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Štolba, M., Urbanovská, M. & Komenda, A. Privacy leakage of search-based multi-agent planning algorithms. Auton Agent Multi-Agent Syst 36, 40 (2022). https://doi.org/10.1007/s10458-022-09568-4
Accepted:
Published:
DOI: https://doi.org/10.1007/s10458-022-09568-4