Stochastic Surveillance Strategies for Spatial Quickest Detection

Vaibhav Srivastava, Fabio Pasqualetti, Francesco Bullo

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 anomaly detection algorithms for the control center and vehicle routing policies. For the control center, we propose parallel cumulative sum (CUSUM) algorithms to detect anomalies from noisy observations. For the vehicles, we propose a stochastic routing policy, including stationary and adaptive variants. Our adaptive policy improves upon the stationary counterpart by 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.

Introduction

In scenarios such as environmental monitoring or security patrolling, the number of regions to monitor often exceeds the number of available autonomous vehicles. Traditional vehicle routing typically focuses on minimizing travel distance or time. However, in surveillance, the primary goal is to minimize detection delay—the time elapsed between an anomaly occurring and the system sounding the alarm. This requires balancing the time spent traveling between regions with the time spent collecting noisy sensor data. We address how to coordinate these vehicles and process their data to catch changes in the environment as quickly as possible.

System architecture showing the feedback loop between the environment, anomaly detection, and vehicle routing.

Methodology

The proposed framework consists of a centralized control center and a decentralized routing policy for the vehicles, creating a closed-loop system.

Ensemble CUSUM Algorithm

The control center runs parallel Cumulative Sum (CUSUM) algorithms—one for each region. CUSUM is a statistical tool that integrates evidence over time to detect a change in a data stream's underlying distribution. By running these in parallel, the system can monitor multiple regions simultaneously based on the noisy observations collected by the UAVs.

Stochastic Routing Policies

We explore two types of routing destination selection:

  1. Stationary Policy: Vehicles choose their next destination based on a fixed probability vector. We derive an "efficient" policy ($q^\dagger$) that minimizes an upper bound on the average detection delay, accounting for travel times and the statistical difficulty of detecting an anomaly in specific regions.
  2. Adaptive Policy: Routing probabilities are updated in real-time based on the current CUSUM statistics. If a region starts showing suspicious data, the vehicles are more likely to visit it sooner and more often to gather more evidence.

Multi-Vehicle Partitioning

For teams of robots, we utilize a partitioning strategy where the environment is divided into disjoint sets. Each robot handles its own partition independently using the efficient single-vehicle policy.

The algorithm for partitioning regions among multiple vehicles.

Key Insights and Results

  • Information-Driven Navigation: Routing is driven by the "likelihood" of finding an anomaly rather than just path length. The adaptive policy effectively turns the robots into active seekers of evidence.
  • The Power of Feedback: Closing the loop—letting the detection algorithm inform the robots where to go next—significantly outperforms "open-loop" stationary patrolling, especially when high confidence (low false alarm rate) is required.
  • Theoretical Bounds: We established rigorous lower bounds for detection delay in both single and multi-vehicle scenarios. The proposed "efficient" stationary policy was proven to be within a constant factor of the optimal stationary policy.
  • Real-World Validation: Lab experiments using Erratic mobile robots confirmed that the system is robust against realistic noise, sensor uncertainties, and the physical constraints of robot motion.

Conclusion

This framework for spatial quickest detection demonstrates that combining parallel statistical tests with smart, adaptive routing allows a small team of robots to monitor large environments effectively. Future work will explore moving anomalies and more sophisticated spatial partitioning techniques to further reduce detection delay.

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