Maximizing Markov Trajectory Entropy Under Kemeny Constraints for Robotic Surveillance

We study trajectory-entropy maximization for Markov chains (MCs) under a Kemeny-constant constraint, given a fixed graph topology and stationary distribution, where the trajectory entropy is the weighted average of the entropy of trajectories between every pair of states, with the weights equal to the product of the stationary probabilities of the initial and final states. This problem is motivated by the application of MCs in the stochastic robotic surveillance, where unpredictability is a desirable property that helps prevent intruders from learning the pattern in the surveillance behavior and planning the attack accordingly, while coverage efficiency as quantified via the Kemeny's constant must also be maintained. We first derive a closed-form expression of the trajectory entropy, which turns out to be the product of two well-known quantities related to MCs, the entropy rate, and the Kemeny's constant. We then show that the trajectory entropy can be made arbitrarily large because the Kemeny's constant grows unbounded when the chain approaches reducibility. To encode the efficiency requirement, we impose an explicit upper bound on the Kemeny's constant and obtain a well-posed problem, which can also be interpreted as an efficiency-unpredictability tradeoff. We then establish several properties of the solutions to the constrained optimization problem, including the irreducibility and reversibility. Finally, we present a numerical example to show that the MC with maximum trajectory entropy is effective against a class of waiting intruders in robotic surveillance.