期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 64, 期 4, 页码 1566-1580出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2018.2844120
关键词
Convex optimization; entropy rate; Markov chain; stochastic surveillance
资金
- Air Force Office of Scientific Research Award [FA9550-15-1-0138]
This paper provides a comprehensive analysis of the following optimization problem: Maximize the entropy rate generated by a Markov chain over a connected graph of order it and subject to a prescribed stationary distribution. First, we show that this problem is strictly convex with global optimum lying in the interior of the feasible space. Second, using Lagrange multipliers, we provide a closed-form expression for the maxentropic Markov chain as a function of an n-dimensional vector, referred to as the maxentropic vector; we provide a provably converging iteration to compute this vector. Third, we show that the maxentropic Markov chain is reversible, compute its entropy rate and describe special cases, among other results. Fourth, through analysis and simulations, we show that our proposed procedure is more computationally efficient than semidefinite programming methods. Finally, we apply these results to robotic surveillance problems. We show realizations of the maxentropic Markov chains over prototypical robotic roadmaps and find that maxentropic Markov chains outperform minimum mean hitting time Markov chains for the so-called intelligent intruders with short attack durations. A comprehensive analysis of the following optimization problem: maximize the entropy rate generated by a Markov chain over a connected graph of order n and subject to a prescribed stationary distribution.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据