Privacy Preserving Plans in Partially Observable Environments

Sarah Keren, Avigdor Gal, Erez KarpasIJCAI 2016 · OpenReview

Abstract: Big brother is watching but his eyesight is not all that great, since he only has partial observability of the environment. In such a setting agents may be able to preserve their privacy by hiding their true goal, following paths that may lead to multiple goals. In this work we present a framework that supports the offline analysis of goal recognition settings with non-deterministic system sensor models, in which the observer has partial (and possibly noisy) observability of the agent's actions, while the agent is assumed to have full observability of his environment. In particular, we propose a new variation of worst case distinctiveness (wcd), a measure that assesses the ability to perform goal recognition within a model. We describe a new efficient way to compute this measure via a novel compilation to classical planning. In addition, we discuss the tools agents have to preserve privacy, by keeping their goal ambiguous as long as possible. Our empirical evaluation shows the feasibility of the proposed solution.

Introduction

In an era of smart cities and ubiquitous surveillance, goal recognition systems are increasingly prevalent. These systems observe an agent's actions and attempt to predict their ultimate destination or objective. While much research focuses on improving the accuracy of these observers, this paper addresses the inverse: how can an agent plan their route to maintain privacy for as long as possible?

The challenge lies in the fact that real-world sensors are rarely perfect; they often suffer from partial observability and noise. This research formalizes a framework for agents to exploit these limitations, maintaining ambiguity by following paths that are consistent with multiple potential goals.

Quantifying Privacy: Worst Case Distinctiveness

The core of this framework is the grd-at (Goal Recognition Design with Action Tokens) model. In this model, an observer does not see actions directly but instead receives "tokens." This introduces two forms of ambiguity: aliasing (multiple actions producing the same token) and non-determinism (one action producing one of several possible tokens).

To measure privacy, the authors introduce Worst Case Distinctiveness (wcd). This metric represents the maximum number of steps an agent can take toward a goal before the sequence of observed tokens reveals their true destination. Privacy, in this context, is achieved through ambiguity—staying on a path that serves as a prefix for plans toward multiple different goals.

Visualization of an agent's path in the GRID domain under varying sensor granularities. The blue regions represent areas where actions are indistinguishable to the observer.

The Common-Declare Compilation

Calculating wcd is computationally intensive if approached via exhaustive search. To solve this efficiently, the authors propose the Common-Declare Compilation. This method transforms the privacy query into a classical planning problem involving two virtual agents. These agents aim for different goals but are constrained to "declare" identical observation tokens.

A standard classical planner (such as Fast Downward) is then used to find the longest possible sequence where these agents can remain synchronized in their observations. The moment they are forced to emit different tokens, their goals become distinguishable, marking the limit of the wcd.

Empirical Evaluation

The framework was evaluated across three classic AI planning domains: LOGISTICS (LOG), BLOCKSWORLD (BLOCK), and GRID NAVIGATION (GRID). For each domain, five sensor models were tested, ranging from FULL (perfect observability) to POND (Partially Observable Non-Deterministic), where sensors are both noisy and limited.

Experimental results across three domains (LOG, BLOCK, GRID) comparing wcd and computation time for different sensor models.

Key Results

  • Quantifiable Privacy: The experiments confirmed that as sensor quality decreases, the wcd value increases. In the GRID domain, reducing sensor granularity increased the "privacy window" by approximately 10%.
  • Efficiency: The compilation method proved robust. While non-deterministic environments (POND) increased search times due to a larger state space, the system successfully solved most problems within a 30-minute window.
  • Cloaking: The research mathematically demonstrates that reducing sensor accuracy is a guaranteed method to increase wcd, providing agents with a reliable way to assess environmental privacy.

Conclusion

This work provides a formal foundation for privacy-preserving planning in imperfectly monitored environments. By leveraging the Common-Declare compilation, agents can efficiently determine paths that maximize their anonymity. Future work may expand this to probabilistic goal recognition, moving beyond worst-case scenarios to account for the likelihood of specific observations in dynamic, real-world environments.

Summary updated

Abstract

Big brother is watching but his eyesight is not all that great, since he only has partial observability of the environment. In such a setting agents may be able to preserve their privacy by hiding their true goal, following paths that may lead to multiple goals. In this work we present a framework that supports the offline analysis of goal recognition settings with non-deterministic system sensor models, in which the observer has partial (and possibly noisy) observability of the agent's actions, while the agent is assumed to have full observability of his environment. In particular, we propose a new variation of worst case distinctiveness (wcd), a measure that assesses the ability to perform goal recognition within a model. We describe a new efficient way to compute this measure via a novel compilation to classical planning. In addition, we discuss the tools agents have to preserve privacy, by keeping their goal ambiguous as long as possible. Our empirical evaluation shows the feasibility of the proposed solution.
BibTeX
@inproceedings{keren2016privacy,
  author = {Sarah Keren and Avigdor Gal and Erez Karpas},
  title = {{Privacy Preserving Plans in Partially Observable Environments}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=ryWQO7fuWS},
}
Figure