Privacy Preserving Multi-Agent Planning with Provable Guarantees
This work addresses the lack of practical algorithms with meaningful privacy guarantees for multi-agent planning, which is crucial for applications requiring secure cooperation among agents.
The paper tackles the problem of slow privacy-preserving algorithms in multi-agent planning by formulating a precise notion of secure computation for search-based algorithms and proving that Secure MAFS has this property across all domains.
In privacy-preserving multi-agent planning, a group of agents attempt to cooperatively solve a multi-agent planning problem while maintaining private their data and actions. Although much work was carried out in this area in past years, its theoretical foundations have not been fully worked out. Specifically, although algorithms with precise privacy guarantees exist, even their most efficient implementations are not fast enough on realistic instances, whereas for practical algorithms no meaningful privacy guarantees exist. Secure-MAFS, a variant of the multi-agent forward search algorithm (MAFS) is the only practical algorithm to attempt to offer more precise guarantees, but only in very limited settings and with proof sketches only. In this paper we formulate a precise notion of secure computation for search-based algorithms and prove that Secure MAFS has this property in all domains.