Privacy leakage of search-based multi-agent planning algorithms

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.