Markov Chains with Maximum Return Time Entropy for Robotic Surveillance

Abstract

This paper studies the problem of maximizing the return time entropy generated by a Markov chain subject to a given graph structure and a prescribed stationary distribution. The return time entropy is defined to be the weighted sum of the entropy of the first return time for the states in the Markov chains. The objective function in our optimization problem is a function series and does not have a closed form in general. First, we show that this problem is well-posed, i.e., the objective function is continuous over a compact set and there exists at least one optimal solution. Then, we analyze two special cases when the objective functions have closed-form expressions. Third, we obtain an upper bound for the return time entropy and solve analytically for the case when the given graph is a complete graph. Fourth, we approximate the problem by truncating the objective function and propose a gradient projection based method to solve it. We also illustrate the results through numerical simulations. The results derived in this paper are relevant to the design of stochastic surveillance strategies in robotic surveillance problems.