Surveillance Evasion Through Bayesian Reinforcement Learning

Dongping Qi, David Bindel, Alexander Vladimirsky

Abstract

We consider a task of surveillance-evading path-planning in a continuous setting. An Evader strives to escape from a 2D domain while minimizing the risk of detection (and immediate capture). The probability of detection is path-dependent and determined by the spatially inhomogeneous surveillance intensity, which is fixed but a priori unknown and gradually learned in the multi-episodic setting. We introduce a Bayesian reinforcement learning algorithm that relies on a Gaussian Process regression (to model the surveillance intensity function based on the information from prior episodes), numerical methods for Hamilton-Jacobi PDEs (to plan the best continuous trajectories based on the current model), and Confidence Bounds (to balance the exploration vs exploitation). We use numerical experiments and regret metrics to highlight the significant advantages of our approach compared to traditional graph-based algorithms of reinforcement learning.

Introduction

Navigating through hazardous environments with unknown risk profiles is a critical challenge in robotics and autonomous systems. Whether it is a drone attempting to evade radar detection or an autonomous underwater vehicle navigating patrolled waters, the "surveillance intensity"—the probability of detection at any given point—is often unknown beforehand. Traditional path-planning methods typically assume a complete map of risks, while standard Reinforcement Learning (RL) approaches often struggle with the "curse of continuity" and fail to leverage the spatial correlations inherent in physical environments.

Presented at AISTATS 2023, this research introduces Alg-GP, a model-based Bayesian RL framework designed for continuous 2D spaces. By combining Gaussian Process (GP) regression with classical partial differential equations (PDEs), the authors demonstrate a method for learning optimal evasion paths that is significantly more efficient and safer than traditional graph-based RL techniques.

The Alg-GP Framework

The core innovation of Alg-GP lies in its integration of spatial modeling and optimal control. The framework consists of several key components:

  1. Gaussian Process (GP) Regression: Instead of treating every coordinate as an independent variable, Alg-GP uses GPs to model surveillance intensity as a smooth, spatially correlated field. This allows the agent to generalize from its experiences; for instance, being captured at one point provides information about the risk in the surrounding area.
  2. Eikonal Equations: The physics of evasion is modeled using the Eikonal equation, a type of Hamilton-Jacobi PDE. This mathematical formulation allows the agent to find the "path of least resistance"—the trajectory that minimizes cumulative risk—within a continuous domain.
  3. Lower Confidence Bounds (LCB): To address the exploration-exploitation trade-off, the algorithm employs an "optimism in the face of uncertainty" strategy. By planning paths based on the LCB of the risk estimate, the agent is naturally incentivized to explore regions where the surveillance intensity is uncertain but potentially low.
  4. Fast Marching Method (FMM): To ensure real-time feasibility, the complex PDEs are solved efficiently using the Fast Marching Method, allowing the agent to update its path planning rapidly between episodes.
Visualization of the Alg-GP framework: (i) Ground truth surveillance intensity, (ii) computed value function, (iii) exploration data with capture points (magenta), and (iv) the Gaussian Process posterior mean estimate of the intensity field.

Experimental Evaluation

The researchers evaluated Alg-GP across several complex 2D scenarios, including maps with bimodal intensity peaks, winding detours through safe corridors, and environments with up to eight distinct surveillance centers.

A key finding was the importance of spatial correlation. Traditional graph-based RL algorithms, such as UCT (Upper Confidence Bound applied to Trees), treat every edge in a discretized grid as independent. This leads to "obvious stagnation," where the agent fails to find global optima even after a million episodes. In contrast, Alg-GP leverages the underlying structure of the risk field, leading to much faster convergence and a dramatic reduction in "regret"—the excess capture rate compared to an agent with perfect knowledge.

Key Insights and Results

  • Learning from Safe Trajectories: Unlike many RL methods that only learn from failures (captures), Alg-GP effectively incorporates "censored data." Every successful meter traveled provides evidence of low surveillance intensity, which the GP uses to refine the global risk map.
  • Robustness to Discretization: The method remains effective even when the observation grid is coarse, as the GP interpolation captures the continuous "shape" of the danger field more accurately than piecewise-constant models.
  • Computational Efficiency: Despite the underlying mathematical complexity, the implementation allows for sub-second episode processing, making it suitable for practical applications.

Limitations and Future Directions

While Alg-GP represents a significant step forward, several challenges remain. The reliance on Hamilton-Jacobi PDEs introduces a "curse of dimensionality," making the approach difficult to scale beyond 3D environments. Additionally, the current model assumes a static surveillance field and isotropic movement (where speed is uniform in all directions). Future research could explore adversarial settings with moving surveillance or more complex vehicle dynamics, such as turning radii and environmental factors like wind or terrain.

Summary updated

Abstract

We consider a task of surveillance-evading path-planning in a continuous setting. An Evader strives to escape from a 2D domain while minimizing the risk of detection (and immediate capture). The probability of detection is path-dependent and determined by the spatially inhomogeneous surveillance intensity, which is fixed but a priori unknown and gradually learned in the multi-episodic setting. We introduce a Bayesian reinforcement learning algorithm that relies on a Gaussian Process regression (to model the surveillance intensity function based on the information from prior episodes), numerical methods for Hamilton-Jacobi PDEs (to plan the best continuous trajectories based on the current model), and Confidence Bounds (to balance the exploration vs exploitation). We use numerical experiments and regret metrics to highlight the significant advantages of our approach compared to traditional graph-based algorithms of reinforcement learning.
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