期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 65, 期 1, 页码 72-86出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2019.2906473
关键词
Entropy; Markov processes; Surveillance; Robots; Random variables; Topology; Markov chains; return time entropy; stochastic surveillance
资金
- Air Force Office of Scientific Research Award [FA9550-15-1-0138]
Motivated by robotic surveillance applications, this paper studies the novel problem of maximizing the return time entropy of a Markov chain, subject to a graph topology with travel times and stationary distribution. The return time entropy is the weighted average, over all graph nodes, of the entropy of the first return times of the Markov chain; this objective function is a function series that does not admit, in general, a closed form. This paper features theoretical and computational contributions. First, we obtain a discrete-time delayed linear system for the return time probability distribution and establish its convergence properties. We show that the objective function is continuous over a compact set and therefore admits a global maximum. We then establish upper and lower bounds between the return time entropy and the well-known entropy rate of the Markov chain. To compute the optimal Markov chain numerically, we establish the asymptotic equality between entropy, conditional entropy, and truncated entropy, and propose an iteration to compute the gradient of the truncated entropy. Finally, we apply these results to the robotic surveillance problem. Our numerical results show that for a model of rational intruder over prototypical graph topologies and test cases, the maximum return time entropy Markov chain outperforms several pre-existing Markov chains.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据