Distributed Markov Chain Redesign for Multiagent Decision-Making Problems

• 成果类型: Article
• 署名作者: Oliva, Gabriele; Setola, Roberto; Gasparri, Andrea
• 署名单位: University Campus Bio-Medico - Rome Italy; Roma Tre University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3170333
• 发表日期: 2023
• 页码: 1288-1295
• 关键词: Markov processes; Limiting; decision making; monitoring; PROPOSALS; employee welfare; Distributed algorithms; distributed decision-making; distributed optimization; Markov chains

摘要

In this article, we consider the problem of modifying in a distributed way the transition probabilities of a Markov chain over an undirected graph in order to achieve a desired limiting distribution, while minimizing the variation from the current weights. This problem setting could be used to model a (graph-based) distributed decision-making process where static agents, e.g., elements of Internet of Things (IoT) networks, are required to achieve a common objective while adapting to different operational conditions, e.g., monitoring of time-varying and spatial-varying phenomena. This could be effectively used to describe several applications settings, ranging from sensor-network-based border patrolling to IoT-based environmental precision farming. In this context, our contribution is threefold: 1) we show that, under the assumption that a global optimal solution exists, then such a solution can be computed by solving a relaxed problem, where the irreducibility and aperiodicity constraints are lifted; 2) we derive an algebraic optimality condition for the relaxed problem; and 3) we design a distributed algorithm that provably converges towards this optimality condition.