Stochastic Surveillance Strategies for Spatial Quickest Detection

Vaibhav Srivastava, Fabio Pasqualetti, Francesco Bullo

TL;DR

This paper develops persistent surveillance strategies for a team of autonomous vehicles to detect anomalies across multiple regions as quickly as possible. By combining parallel cumulative sum (CUSUM) detection algorithms with novel stochastic routing policies—both stationary and adaptive—the authors provide a framework that minimizes detection delay while maintaining a low false alarm rate, even in the presence of significant sensor noise and travel time constraints.

What Problem Does This Paper Address?

Imagine a scenario like an oil spill, a wildfire, or monitoring a large industrial facility. You have a limited number of autonomous robots but many regions to monitor. Each sensor reading is noisy, meaning a single "bad" reading doesn't necessarily mean there's an anomaly; you need to accumulate evidence over time. Furthermore, robots take time to travel between regions.

The core challenge is the spatial quickest detection problem: how should robots move between regions, and how should a central controller process their noisy data to detect changes in the environment (anomalies) in the minimum amount of time? The goal is to balance the "detection delay" (time from anomaly start to detection) against the "false alarm rate."

Methods

The authors propose a two-part system architecture, as illustrated in the overall setup:

Persistent Surveillance Setup Architecture
  1. Ensemble CUSUM Algorithm: The control center runs $n$ parallel CUSUM algorithms, one for each region. CUSUM is a classic sequential statistical test that accumulates the log-likelihood ratio of observations. When the accumulated evidence for a region exceeds a threshold $\eta$, an anomaly is declared.
  2. Stochastic Routing Policies: Instead of deterministic paths (which can be predictable and sub-optimal), the robots choose their next destination based on a probability vector.
  3. Stationary Policy: The probability of visiting a region is constant. The authors show that the function for average detection delay is generally non-convex (see Figure 2), making it hard to find the absolute global optimum. They propose an "efficient" stationary policy ($q^\dagger$) based on minimizing an upper bound of the delay.
  4. Adaptive Policy: The routing probability is updated in real-time based on the current CUSUM statistics. If the evidence for an anomaly in Region A is growing, the robots are more likely to visit Region A next to gather more data and confirm the detection faster.
  5. Multi-Vehicle Partitioning: For teams of $m$ robots, the authors propose a partitioning strategy (Algorithm 2) where the $n$ regions are divided among the robots, and each robot then follows the single-vehicle stochastic policy within its assigned territory.

Datasets

The paper does not use standard public datasets. Instead, it evaluates the algorithms through:

  • Numerical Simulations: Using synthetic data where observations are sampled from normal distributions with different means and variances to represent nominal vs. anomalous states.
  • Persistent Surveillance Experiment: A real-world test using three "Erratic" mobile robots in a laboratory environment. The "observations" were campus images, some of which were manually altered to include anomalies (like black smoke). The robots used standard ROS-based drivers (Player/Stage) for localization and navigation.

Key Insights and Ideas

  • The Non-Convexity Challenge: A major theoretical insight is that the average detection delay function for stationary policies is non-convex. This means standard gradient descent might get stuck in local minima. Non-convex level sets of the objective function However, the authors provide probabilistic guarantees that their optimization approach typically finds a unique global minimum for most practical parameter distributions.

  • Closing the Loop with Adaptation: The most powerful idea is using the internal state of the detection algorithm (the CUSUM statistic) to drive the physical movement of the robots. This feedback loop allows the system to focus resources where they are most needed in real-time.

  • Analytical Bounds: The authors don't just provide heuristics; they derive rigorous lower and upper bounds for detection delay that account for travel times, processing times, and the statistical "difficulty" of detecting an anomaly (measured by Kullback-Leibler divergence).
Non-convex level sets of the objective function

Key Results

  • Efficiency of the $q^\dagger$ Policy: Simulations showed that the proposed "efficient" stationary policy performs nearly as well as the numerically computed optimal stationary policy, while being much easier to calculate.
  • Adaptive Superiority: The adaptive routing policy significantly outperformed stationary policies, especially at higher detection thresholds (which correspond to lower false alarm rates). In some simulations, the adaptive policy reduced detection delay by nearly 50% compared to a uniform stationary policy.
  • Hardware Robustness: The lab experiment confirmed that the ensemble CUSUM and adaptive routing are robust to real-world issues like localization errors, varying travel times, and complex image-based observation noise. The robots successfully detected anomalies in the assigned regions with very few observations.

Limitations and Future Work

  • Static Anomalies: The current framework assumes anomalies stay in the region where they started. The authors suggest that extending this to "moving anomalies" that can migrate between regions is a key next step.
  • Simple Partitioning: The multi-robot partitioning strategy used in the paper is relatively basic. The authors note that "smarter" partitioning policies that better account for the spatial layout and travel times between all regions could further improve performance.
  • Known Distributions: The basic CUSUM assumes the probability distributions for both normal and anomalous states are known. While the authors demonstrate a Generalized Likelihood Ratio (GLR) extension for unknown anomalous parameters, further work on fully robust, distribution-free detection would be valuable.

Summary updated

Abstract

We design persistent surveillance strategies for the quickest detection of anomalies taking place in an environment of interest. From a set of predefined regions in the environment, a team of autonomous vehicles collects noisy observations, which a control center processes. The overall objective is to minimize detection delay while maintaining the false alarm rate below a desired threshold. We present joint (i) anomaly detection algorithms for the control center and (ii) vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms (one for each region) to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, in which the regions to be visited are chosen according to a probability vector. We study stationary routing policy (the probability vector is constant) as well as adaptive routing policies (the probability vector varies in time as a function of the likelihood of regional anomalies). In the context of stationary policies, we design a performance metric and minimize it to design an efficient stationary routing policy. Our adaptive policy improves upon the stationary counterpart by adaptively increasing the selection probability of regions with high likelihood of anomaly. Finally, we show the effectiveness of the proposed algorithms through numerical simulations and a persistent surveillance experiment.
BibTeX
@article{srivastava2013stochastic,
  author = {Vaibhav Srivastava and Fabio Pasqualetti and Francesco Bullo},
  title = {{Stochastic Surveillance Strategies for Spatial Quickest Detection}},
  journal = {Int. J. Robotics res},
  year = {2013},
  doi = {10.1177/0278364913490322},
}
Figure