Surveillance Evasion Through Bayesian Reinforcement Learning

Dongping Qi, David Bindel, Alexander Vladimirsky

Introduction

In many high-stakes scenarios, such as UAV navigation in contested airspace or illegal logging detection, an "Evader" must traverse a region monitored by hidden surveillance. The primary challenge lies in the fact that the surveillance intensity—the probability of being captured at any given point—is initially unknown. To succeed, the agent must learn the "risk map" of the environment through repeated episodes, balancing the need to explore new areas with the desire to exploit known safe paths.

This paper introduces Alg-GP, a Bayesian Reinforcement Learning (BRL) framework designed for path planning in continuous environments with spatially varying, unknown surveillance. By integrating Gaussian Process (GP) regression with Hamilton-Jacobi partial differential equations (PDEs), the proposed method offers a significant leap in learning efficiency and evasion success compared to traditional discrete reinforcement learning approaches.

The Evasion Challenge: Multi-Episodic Path Planning

Standard path planning typically assumes a perfectly known map. However, in surveillance evasion, the environment is "dark." The Evader only gains information when it successfully traverses a region or is captured. This is a problem of multi-episodic path planning with unknown random termination.

The objective is to minimize "regret"—the difference between the capture rate of the learning agent and that of an omniscient agent with perfect knowledge of the surveillance field. Traditional Reinforcement Learning (RL) methods, like Upper Confidence Bound for Trees (UCT), often struggle in these settings because they treat the environment as a discrete graph and ignore the inherent spatial correlations of physical risk.

The Alg-GP Framework

The researchers propose a model-based approach that leverages three core mathematical components:

  1. Gaussian Process (GP) Regression: Instead of treating every point in the domain as independent, Alg-GP uses GPs to model surveillance intensity. This allows the agent to exploit spatial correlations; information gained at one point helps predict risk in adjacent areas. The model specifically handles "right-censored" data: if an agent survives a path, we know the integrated risk was low; if it is caught, we know the risk at the point of capture was high.
  2. Hamilton-Jacobi PDEs (The Eikonal Equation): To determine the optimal continuous trajectory, the algorithm solves the Eikonal equation. Using the Fast Marching Method (FMM), it calculates a "value function" representing the minimum cumulative risk across the entire domain. This avoids the "discretization gap" inherent in grid-based movement.
  3. Optimism in the Face of Uncertainty: To manage the exploration-exploitation trade-off, the algorithm employs a Lower Confidence Bound (LCB) on the learned risk map. By optimistically underestimating risk in unvisited regions, the agent is encouraged to explore potentially safer alternative routes.
Overview of surveillance environments and learned trajectories: (i) Bimodal intensity, (ii) Multi-peak landscape, (iii) Learning process with sample points, and (iv) Smooth risk field.

Experimental Evaluation

The performance of Alg-GP was evaluated across several complex synthetic 2D environments, including bimodal and multi-peak landscapes. These tests assessed the algorithm's ability to navigate around multiple "peaks" of high surveillance and its robustness when the risk map has non-smooth characteristics like sharp boundaries.

The algorithm was compared against UCT (a model-free RL algorithm) and Alg-D (a model-based graph RL), demonstrating superior performance in both learning speed and final path optimality.

Key Insights

Spatial Correlation as a Force Multiplier

Traditional RL treats each path as an isolated data point. In contrast, the Bayesian approach recognizes that surviving the first half of a journey provides valuable evidence about that specific sub-region. This allows for much faster convergence, as the agent doesn't need to visit every single "node" to understand the safety of a neighborhood.

Learning from Failure and Success

The algorithm's ability to incorporate both successful traversals and capture events is crucial. As shown in the learning process visualizations, the agent uses a cloud of "censored" data points (successful and failed attempts) to refine its internal model of the risk field.

Detailed view of the learning process, showing the evader's path (black) amidst successful and failed exploration points (magenta dots).

Overcoming the Discretization Gap

Graph-based methods are limited to a fixed set of movement directions (e.g., 8-way connectivity). Even with extremely fine grids, these methods cannot reach the true continuous optimum. By solving the Eikonal equation, Alg-GP finds the mathematically optimal path in continuous space, resulting in lower overall regret.

Results and Conclusion

In all experimental scenarios, Alg-GP demonstrated superior convergence speed and lower cumulative regret than its graph-based counterparts. Despite the mathematical complexity of GPs and PDEs, the implementation is highly efficient, with each planning episode taking less than 0.1 seconds on standard hardware.

While the current model assumes isotropic dynamics, it provides a robust foundation for future work involving vehicle constraints and dynamic adversaries. The integration of Bayesian learning with continuous optimization represents a powerful new paradigm for autonomous navigation in hazardous, unknown environments.

Summary updated

BibTeX
@inproceedings{qi2023surveillance,
  author = {Dongping Qi and David Bindel and Alexander Vladimirsky},
  title = {{Surveillance Evasion Through Bayesian Reinforcement Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=sQLwdPSnpy},
}
Figure