www.prismmodelchecker.org
[LK16] Morteza Lahijanian and Marta Kwiatkowska. Specification Revision for Markov Decision Processes with Optimal Trade-off. In Proc. 55th Conference on Decision and Control (CDC'16), pages 7411-7418. 2016. [pdf] [bib] [Presents techniques for techniques for analysing trade-offs between the probability of satisfying a specification and the cost of revising, using PRISM as an underlying multi-objective model checker.]
Downloads:  pdf pdf (1.73 MB)  bib bib
Links: [Google] [Google Scholar]
Abstract. Optimal control policy synthesis for probabilistic systems from high-level specifications is increasingly often studied. One major question that is commonly faced, however, is what to do when the optimal probability of achieving the specification is not satisfactory? We address this question by viewing the specification as a soft constraint and present a synthesis framework for MDPs that encodes and automates specification revision in a trade-off for higher probability. The method uses co-safe LTL as the specification language and quantifies the revisions to the specification according to user-defined proposition costs. The framework computes a control policy that optimizes the trade-off between the probability of satisfaction and the cost of specification revision. The key idea of the method is a rule for the composition of the MDP, the automaton representing the specification, and the proposition costs such that all possible specification revisions along with their costs and probabilities of satisfaction are captured in one structure. The problem is then reduced to multi-objective optimization on an MDP. The power of the method is illustrated though simulations of a complex robotic scenario.

Publications