Optimal control of MDPs with temporal logic constraints
Files
Accepted manuscript
Date
2013-01-01
Authors
Svorenova, Maria
Cerna, Ivana
Belta, Calin
Version
OA Version
Citation
Maria Svorenova, Ivana Cerna, Calin Belta. 2013. "Optimal Control of MDPs with Temporal Logic Constraints." 2013 IEEE 52ND ANNUAL CONFERENCE ON DECISION AND CONTROL (CDC), pp. 3938 - 3943 (6).
Abstract
In this paper, we focus on formal synthesis of control policies for finite Markov decision processes with non-negative real-valued costs. We develop an algorithm to automatically generate a policy that guarantees the satisfaction of a correctness specification expressed as a formula of Linear Temporal Logic, while at the same time minimizing the expected average cost between two consecutive satisfactions of a desired property. The existing solutions to this problem are sub-optimal. By leveraging ideas from automata-based model checking and game theory, we provide an optimal solution. We demonstrate the approach on an illustrative example.