Saturated Path-Constrained MDP: Planning Under Uncertainty and Deterministic Model-Checking Constraints
Abstract
In many probabilistic planning scenarios, a system’s behavior needs to not only maximize the expected utility but also obey certain restrictions. This paper presents Saturated Path-Constrained Markov Decision Processes (SPC MDPs), a new MDP type for planning under uncertainty with deterministic model-checking constraints, e.g., "state s must be visited befores s'", "the system must end up in s", or "the system must never enter s". We present a mathematical analysis of SPCMDPs, showing that although SPC MDPs generally have no optimal policies, every instance of this class has an epsilon-optimal randomized policy for any > 0. We propose a dynamic programming-based algorithm for finding such policies, and empirically demonstrate this algorithm to be orders of magnitude faster than its next-best alternative.
Cite
Text
Sprauel et al. "Saturated Path-Constrained MDP: Planning Under Uncertainty and Deterministic Model-Checking Constraints." AAAI Conference on Artificial Intelligence, 2014. doi:10.1609/AAAI.V28I1.9041Markdown
[Sprauel et al. "Saturated Path-Constrained MDP: Planning Under Uncertainty and Deterministic Model-Checking Constraints." AAAI Conference on Artificial Intelligence, 2014.](https://mlanthology.org/aaai/2014/sprauel2014aaai-saturated/) doi:10.1609/AAAI.V28I1.9041BibTeX
@inproceedings{sprauel2014aaai-saturated,
title = {{Saturated Path-Constrained MDP: Planning Under Uncertainty and Deterministic Model-Checking Constraints}},
author = {Sprauel, Jonathan and Kolobov, Andrey and Teichteil-Königsbuch, Florent},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2014},
pages = {2367-2373},
doi = {10.1609/AAAI.V28I1.9041},
url = {https://mlanthology.org/aaai/2014/sprauel2014aaai-saturated/}
}