Constrained Control of Large Graph-Based MDPs Under Measurement Uncertainty

We consider controlling a graph-based Markov decision process (GMDP) with a control capacity constraint given only uncertain measurements of the underlying state. We also consider two special structural properties of GMDPs, called anonymous influence and symmetry. Large-scale spatial processes such as forest wildfires, disease epidemics, opinion dynamics, and robot swarms are well-modeled by GMDPs with these properties. We adopt a certainty-equivalence approach and derive efficient and scalable algorithms for estimating the GMDP state given uncertain measurements, and for computing approximately optimal control policies given a maximum-likelihood state estimate. We also derive suboptimality bounds for our estimation and control algorithms. Unlike prior work, our methods scale to GMDPs with large state-spaces and explicitly enforce a control constraint. We demonstrate the effectiveness of our estimation and control approach in simulations of controlling a forest wildfire using a model with $10^{1192}$ total states.

• Publication year

  2023

• Venue

  IEEE Transactions on Automatic Control

• Publication date

  2023-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TAC.2023.3242344
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning Large Graph-Based MDPs With Historical Data

  2022cited by this paper
• Scalable Filtering of Large Graph-Coupled Hidden Markov Models

  2019cited by this paper
• Semi-Implicit Variational Inference

  2018influential reference
• Controlling Large, Graph-based MDPs with Global Control Capacity Constraints: An Approximate LP Solution

  2018cited by this paper
• A stable particle filter for a class of high-dimensional state-space models

  2017cited by this paper
• A Unifying Variational Inference Framework for Hierarchical Graph-Coupled HMM with an Application to Influenza Infection

  2016cited by this paper
• Variational Inference: A Review for Statisticians

  2016influential reference
• Stochastic Processes And Filtering Theory

  2016cited by this paper
• Filter comparison for estimation on discretized PDEs modeling traffic: Ensemble Kalman Filter and minimax filter

  2016cited by this paper
• Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs

  2015cited by this paper
• Efficient approximate linear programming for factored MDPs

  2015cited by this paper
• Structured Stochastic Variational Inference

  2014cited by this paper
• Point-Based POMDP Solving with Factored Value Function Approximation

  2014cited by this paper
• Approximate Planning for Factored POMDPs

  2014cited by this paper
• Weakly Coupled Dynamic Program: Information and Lagrangian Relaxations

  2014cited by this paper
• Variational Particle Approximations

  2014cited by this paper
• Coupled hidden markov models for user activity in social networks

  2013cited by this paper
• Variational Planning for Graph-based MDPs

  2013cited by this paper
• Graph-Coupled HMMs for Modeling the Spread of Infection

  2012cited by this paper
• Variational Bayesian Inference with Stochastic Search

  2012cited by this paper
• Fast Variational Inference in the Conjugate Exponential Family

  2012cited by this paper
• Stochastic variational inference

  2012cited by this paper
• A Survey of Monte Carlo Tree Search Methods

  2012cited by this paper
• Model Predictive Control for Dynamic Resource Allocation

  2012cited by this paper
• A framework and a mean-field algorithm for the local control of spatial processes

  2012cited by this paper
• Filtering via approximate Bayesian computation

  2010cited by this paper
• Approximate dynamic programming for capacity allocation in the service industry

  2010cited by this paper
• Efficient Planning in Large POMDPs through Policy Graph Based Factorized Approximations

  2010cited by this paper
• Relaxations of Weakly Coupled Stochastic Dynamic Programs

  2008cited by this paper
• Approximate Linear-Programming Algorithms for Graph-Based Markov Decision Processes

  2006influential reference
• Particle Filters for Infinite (or Large) Dimensional State Spaces-Part 2

  2006cited by this paper
• Variational Message Passing

  2005cited by this paper
• VDCBPI: an Approximate Scalable Algorithm for Large POMDPs

  2004cited by this paper
• Efficient Solution Algorithms for Factored MDPs

  2003cited by this paper
• Solving Factored POMDPs with Linear Value Functions

  2001cited by this paper
• Stochastic dynamic programming with factored representations

  2000cited by this paper
• Generalized Belief Propagation

  2000cited by this paper
• On sequential Monte Carlo sampling methods for Bayesian filtering

  2000cited by this paper
• Constrained Markov Decision Processes

  1999cited by this paper
• Computing Factored Value Functions for Policies in Structured MDPs

  1999cited by this paper
• Loopy Belief Propagation for Approximate Inference: An Empirical Study

  1999cited by this paper
• Solving Very Large Weakly Coupled Markov Decision Processes

  1998cited by this paper
• Exploiting Tractable Substructures in Intractable Networks

  1995cited by this paper
• Novel approach to nonlinear/non-Gaussian Bayesian state estimation

  1993cited by this paper
• Tight Performance Bounds on Greedy Policies Based on Imperfect Value Functions

  1993influential reference
• Ieee Transactions on Signal Processing Convolution on the N-sphere with Application to Pdf Modeling

  year unknowncited by this paper

• Optimal Control of Markov Decision Processes for Efficiency with Linear Temporal Logic Tasks

  2024cites this paper
• Learning Large Graph-Based MDPs With Historical Data

  2022cites this paper