A Privacy Preserving Algorithm for Multi-Agent Planning and Search

Ronen I. BrafmanIJCAI 2015

Introduction

In multi-agent planning (MAP), diverse entities—such as independent logistics companies or international disaster response teams—must coordinate their actions to achieve a shared global objective. While cooperation is essential, these agents often possess proprietary or sensitive information, such as internal resource levels, specific vehicle locations, or private operational constraints, which they wish to keep confidential.

Traditional approaches to this problem have largely relied on "weak privacy" models. These models ensure that agents do not explicitly share private state variables and utilize encryption for communication. However, as this research demonstrates, weak privacy is insufficient. Even when data is encrypted, the underlying structure of the distributed search process—specifically the pattern of communication and the topology of the search tree—can leak significant information. For instance, an agent observing the number of successor states generated by a partner might deduce the complexity of that partner's private internal processes. This paper introduces SECURE-MAFS, the first multi-agent planning algorithm designed to provide formal "strong privacy" guarantees, ensuring that no private information can be mathematically deduced from the search process.

The SECURE-MAFS Framework

SECURE-MAFS builds upon the established Multi-Agent Forward Search (MAFS) framework and the MA-STRIPS model. The core challenge in achieving strong privacy lies in masking the "search tree leak"—the information revealed by the number and timing of state transmissions between agents.

To address this, the authors introduce two primary mechanisms:

1. Virtual-Send Mechanism

In standard MAFS, when an agent reaches a state where another agent is eligible to act, it transmits that state to the relevant party. SECURE-MAFS modifies this by checking if a state with the same "public footprint" (the set of values for all public variables) has already been sent. If it has, the algorithm performs a "virtual send." Instead of transmitting the state again, the system allows the receiving agent to utilize its existing knowledge of that public state, effectively collapsing multiple private paths into a single public representative. This prevents an observer from counting how many internal paths lead to a specific public milestone.

2. State Caching

To support the virtual-send mechanism, agents maintain a specialized "closed list" consisting of three-tuples: the public key, private components, and public children. This caching system allows agents to recognize when different private action sequences lead to identical public outcomes. By managing these transitions internally and only communicating unique public transitions, the algorithm hides the branching logic of an agent's private sub-problems.

Theoretical Insights and Strong Privacy

The most significant contribution of this work is the formalization of "strong privacy." The authors define a standard where an agent cannot deduce any information about another agent’s private variables or actions beyond what is inherently revealed by the public interface and the final agreed-upon plan.

The paper establishes that the topology of a distributed search is a primary vector for information leakage. By ensuring that the "projected" search trees (the tree as viewed through public variables only) remain identical across different possible private configurations, SECURE-MAFS makes these configurations indistinguishable to other agents.

Key Results

The research provides several rigorous proofs regarding the algorithm's performance and security:

  • Soundness and Completeness: The authors prove that SECURE-MAFS is both sound (it only returns valid plans) and complete (it will find a plan if one exists), maintaining the fundamental requirements of a planning algorithm.
  • Privacy Guarantees: Under the conditions of unit action costs and heuristics that are insensitive to private variables, the paper proves that SECURE-MAFS achieves strong privacy.
  • Domain Application: The algorithm was validated using classic planning domains. In the Logistics domain, for example, the authors demonstrated that vehicle locations and internal movements remain strongly private throughout the planning process.
  • Efficiency Gains: Interestingly, the mechanisms introduced for privacy—specifically the reduction of redundant state transmissions—often result in lower communication overhead compared to the original, non-secure MAFS algorithm.

Limitations and Future Directions

While SECURE-MAFS represents a major leap forward, the authors identify specific constraints that provide avenues for future research:

  • Heuristic Leakage: If a heuristic function is highly sensitive to private data, the order in which states are expanded could still leak information. The current proof of strong privacy assumes heuristics do not rely on private variables. The authors suggest that introducing $\epsilon$-exploration (randomized state expansion) could mitigate this risk.
  • The Honest-but-Curious Model: The current framework assumes agents are "honest-but-curious"—they follow the protocol but attempt to learn as much as possible. Future work is needed to address "malicious" agents who might intentionally deviate from the protocol to extract secrets.
  • Non-Unit Costs: Extending strong privacy to scenarios with varying action costs remains a challenge, as cost differences can reveal information about which private actions were taken.

Conclusion

SECURE-MAFS shifts the paradigm of multi-agent planning from heuristic-based privacy to mathematically proven security. By addressing the subtle information leaks inherent in distributed search topologies, it provides a robust foundation for collaborative planning in environments where data sensitivity is paramount.

Summary updated

BibTeX
@inproceedings{brafman2015privacy,
  author = {Ronen I. Brafman},
  title = {{A Privacy Preserving Algorithm for Multi-Agent Planning and Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure