Quickest Detection Over Robotic Roadmaps

Abstract

We study the problem of quickest detection of anomalies in an environment under extreme uncertainties in sensor measurements. The robotic roadmap corresponding to the environment can be represented as a graph with an arbitrary topology. We analyze the Ensemble CUSUM Algorithm for this surveillance problem. We quantify the delay in detection of anomalies using the Ensemble CUSUM Algorithm and also frame an optimization problem to minimize this detection delay. We then provide an upper bound on the optimal detection delay and frame a convex optimization problem to minimize this upper bound. We also propose an efficient policy that achieves this upper bound and can be computed by solving a semidefinite program. We illustrate the efficacy of the Ensemble CUSUM Algorithm using numerical simulations. We observe that the efficient policy outperforms policies based on other well-known Markov chains.