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.
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:
- 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.
- 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.
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