Deceptive Path Planning via Reinforcement Learning with Graph Neural Networks

Michael Y. Fatemi, Wesley A. Suttle, Brian M. Sadler

Introduction

Deceptive Path Planning (DPP) involves navigating from a starting point to a target destination while intentionally misleading an observer into believing the agent is heading toward a different, "decoy" goal. This capability is critical in domains such as defense, competitive sports, and cybersecurity. Traditional DPP solutions typically rely on complex optimization techniques, such as Linear Programming, which require a global view of the environment and a perfect model of the observer's reasoning. However, these classical methods are computationally intensive, scale poorly to large maps, and are "brittle"—requiring complete recalculation if the environment changes even slightly.

Methodology

To overcome these limitations, we propose a model-free Reinforcement Learning (RL) framework that represents the environment as a graph. Our approach introduces several key innovations:

Local Perception and GNN Policies

Instead of requiring a global map, the agent operates using local perception, seeing only its $k$-hop neighborhood. By employing GraphSAGE, a type of Graph Neural Network (GNN), the policy learns to process local graph structures. Because GNNs are inductive, a policy trained on a small set of graphs can generalize to entirely new and larger graph structures at test time without further training.

Deception Rewards

We translate classical deception metrics into RL-friendly reward functions:

  • Exaggeration: This reward encourages the agent to move aggressively toward a decoy goal before pivoting back to the true destination.
  • Ambiguity: This reward guides the agent to stay in "tightrope" regions where the observer cannot distinguish between the real goal and the decoy.
Comparison between classical ambiguity metrics and the proposed 'tightrope' reward, which encourages the agent to remain in non-committal regions.

Tunable Urgency

By varying the maximum allowed steps ($T_{max}$) during training, the agent learns to utilize extra time for more elaborate deception. This allows users to tune the agent's behavior at test time: increasing $T_{max}$ results in more deceptive paths, while decreasing it produces more direct, efficient routes.

Experimental Setup

The agents were trained on a minimal dataset consisting of only six small gridworld environments (three 8x8 and three 16x16). Evaluation was conducted on significantly more challenging scenarios:

  1. Large-Scale Gridworlds: Maps up to 100x100 to test the scalability of the local perception approach.
  2. Continuous Forest Environments: A novel environment where trees act as obstacles. The agent uses Voronoi clustering to transform this continuous space into a graph on-the-fly, testing zero-shot transfer from discrete grids to continuous motion.

Results and Discussion

Our results demonstrate that the GNN-based policy captures the fundamental essence of deception rather than memorizing specific map layouts.

Zero-Shot Generalization and Efficiency

The policy successfully performed deceptive navigation in continuous environments without any fine-tuning, demonstrating remarkable "small-to-large" generalization. Furthermore, because the policy relies on a fast neural network forward pass, it provides near-instantaneous decision-making, allowing the agent to adapt to dynamic changes—such as moving decoys or new obstacles—in real-time.

Tunability of Deception

We observed a clear trade-off between path efficiency and deception quality. As the agent is granted more time (higher $T_{max}$), the generated paths become significantly more exaggerated toward the decoy.

Deceptive paths with varying time constraints ($T_{max}$), showing increased exaggeration toward the decoy as more time is allowed.

Conclusion

This work presents a scalable and adaptable approach to Deceptive Path Planning using RL and GNNs. By focusing on local perception and inductive learning, we enable agents to perform zero-shot transfer to complex, unseen environments. Future work will explore scenarios with multiple decoys, more sophisticated adversarial observers, and deployment on physical robotic platforms.

Summary updated

BibTeX
@inproceedings{fatemi2024deceptive,
  author = {Michael Y. Fatemi and Wesley A. Suttle and Brian M. Sadler},
  title = {{Deceptive Path Planning via Reinforcement Learning with Graph Neural Networks}},
  booktitle = {AAMAS},
  year = {2024},
}
Figure