Path-Constrained Markov Decision Processes: bridging the gap between probabilistic model-checking and decision-theoretic planning.

Abstract : Markov Decision Processes (MDPs) are a popular model for planning under probabilistic uncertainties. The solution of an MDP is a policy represented as a controlled Markov chain, whose complex properties on execution paths can be automatically validated using stochastic model-checking techniques. In this paper, we propose a new theoretical model, named Path-Constrained Markov Decision Processes: it allows system designers to directly optimize safe policies in a single design pass, whose possible executions are guaranteed to satisfy some probabilistic constraints on their paths, expressed in Probabilistic Real Time Computation Tree Logic. We mathematically analyze properties of PC-MDPs and provide an iterative linear programming algorithm for solving them.We also present experiments that illustrate PC-MDPs and highlight their benefits.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-onera.archives-ouvertes.fr/hal-01060349
Contributor : Alain Broc <>
Submitted on : Wednesday, September 3, 2014 - 2:37:38 PM
Last modification on : Tuesday, March 26, 2019 - 2:28:03 PM
Long-term archiving on : Thursday, December 4, 2014 - 11:22:11 AM

File

DCSD12084.1399388482.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01060349, version 1

Collections

Citation

Florent Teichteil-Königsbuch. Path-Constrained Markov Decision Processes: bridging the gap between probabilistic model-checking and decision-theoretic planning.. 20th European Conference on Artificial Intelligence (ECAI 2012), Aug 2012, MONTPELLIER, France. ⟨hal-01060349⟩

Share

Metrics

Record views

508

Files downloads

379