Robotic Surveillance and Markov Chains With Minimal Weighted Kemeny Constant

Abstract

This article provides analysis and optimization results for the mean first passage time, also known as the Kemeny constant, of a Markov chain. First, we generalize the notion of the Kemeny constant to environments with heterogeneous travel and service times, denote this generalization as the weighted Kemeny constant, and we characterize its properties. Second, for reversible Markov chains, we show that the minimization of the Kemeny constant and its weighted counterpart can be formulated as convex optimization problems and, moreover, as semidefinite programs. Third, we apply these results to the design of stochastic surveillance strategies for quickest detection of anomalies in network environments. We numerically illustrate the proposed design: compared with other well-known Markov chains, the performance of our Kemeny-based strategies are always better and in many cases substantially so.