Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions

Jeong, Jihwan; Jaggi, Parth; Sanner, Scott

doi:10.24963/ijcai.2021/562

Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions

Jihwan Jeong, Parth Jaggi, Scott Sanner

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4083-4089.

https://doi.org/10.24963/ijcai.2021/562

Keywords

Uncertainty in AI: Markov Decision Processes
Planning and Scheduling: Planning under Uncertainty
Planning and Scheduling: Markov Decisions Processes

Abstract

Recent advances in symbolic dynamic programming (SDP) have significantly broadened the class of MDPs for which exact closed-form value functions can be derived. However, no existing solution methods can solve complex discrete and continuous state MDPs where a linear program determines state transitions --- transitions that are often required in problems with underlying constrained flow dynamics arising in problems ranging from traffic signal control to telecommunications bandwidth planning. In this paper, we present a novel SDP solution method for MDPs with LP transitions and continuous piecewise linear dynamics by introducing a novel, fully symbolic argmax operator. On three diverse domains, we show the first automated exact closed-form SDP solution to these challenging problems and the significant advantages of our SDP approach over discretized approximations.

Jihwan Jeong, Parth Jaggi, and Scott Sanner. 2021. Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4083–4089. https://doi.org/10.24963/ijcai.2021/562

@inproceedings{ijcai2021p562,
  title     = {Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions},
  author    = {Jeong, Jihwan and Jaggi, Parth and Sanner, Scott},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4083--4089},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/562},
  url       = {https://doi.org/10.24963/ijcai.2021/562},
}

TY  - CPAPER
TI  - Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions
AU  - Jeong, Jihwan
AU  - Jaggi, Parth
AU  - Sanner, Scott
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4083
EP  - 4089
DO  - 10.24963/ijcai.2021/562
UR  - https://doi.org/10.24963/ijcai.2021/562
ER  -