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

@inproceedings{haksar_controlling_2018,
address = {Miami Beach, FL},
title = {Controlling {Large}, {Graph}-based {MDPs} with {Global} {Control} {Capacity} {Constraints}: {An} {Approximate} {LP} {Solution}},
isbn = {978-1-5386-1395-5},
shorttitle = {Controlling {Large}, {Graph}-based {MDPs} with {Global} {Control} {Capacity} {Constraints}},
url = {https://ieeexplore.ieee.org/document/8618745/},
abstract = {We consider controlling graph-based MDPs (GMDPs) with two special properties: (i) Anonymous Inﬂuence and (ii) Symmetry. Large-scale spatial processes such as wildﬁres, disease epidemics, opinion dynamics, and robot swarms are well modeled by GMDPs with these properties. We derive two efﬁcient and scalable algorithms for computing approximately optimal control policies for large GMDPs with Anonymous Inﬂuence and Symmetry and derive sub-optimality bounds for these policies. Unlike prior work, our algorithms explicitly enforce a global control capacity constraint. Our methods scale linearly in the number of equivalence classes in the GMDP rather than the total number of MDPs in the graph. We demonstrate our methods in simulations of controlling a wildﬁre with a global ﬁre retardant constraint and controlling an Ebola outbreak with a global medicine constraint. Our Ebola model is derived from data from the 2014 West Africa outbreak.},
language = {en},
urldate = {2020-09-15},
booktitle = {2018 {IEEE} {Conference} on {Decision} and {Control} ({CDC})},
publisher = {IEEE},
author = {Haksar, Ravi N. and Schwager, Mac},
month = dec,
year = {2018},
keywords = {optimal\_control},
pages = {35--42},
month_numeric = {12}
}