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. © 1963-2012 IEEE.

Distributed Markov Chain Redesign for Multi-Agent Decision-Making Problems

Gabriele Oliva;Roberto Setola;
2023-01-01

Abstract

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. © 1963-2012 IEEE.
2023
Graphic methods; Internet of things; Markov processes; Multi agent systems; Parallel algorithms; Probability distributions; Sensor networks; Undirected graphs
File in questo prodotto:
File Dimensione Formato  
Distributed_Markov_Chain_Redesign_for_Multi-Agent_Decision-Making_Problems.pdf

solo utenti autorizzati

Licenza: Non specificato
Dimensione 276.71 kB
Formato Adobe PDF
276.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12610/67105
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact