---
title: "Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions"
authors:
  - "Jihwan Jeong"
  - "Parth Jaggi"
  - "Scott Sanner"
doi: "10.24963/ijcai.2021/562"
url: "https://ijcai.org/proceedings/2021/562"
pdf: "https://ijcai.org/proceedings/2021/0562.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4083-4089"
track: "Main Track"
keywords:
  - "Uncertainty in AI: Markov Decision Processes"
  - "Planning and Scheduling: Planning under Uncertainty"
  - "Planning and Scheduling: Markov Decisions Processes"
---

# Symbolic Dynamic Programming for Continuous State MDPs with Linear Program Transitions

Jihwan Jeong, Parth Jaggi, Scott Sanner

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4083-4089. DOI: [10.24963/ijcai.2021/562](https://doi.org/10.24963/ijcai.2021/562)

## 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.