首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Threshold Constraints with Guarantees for Parity Objectives in Markov Decision Processes
  • 本地全文:下载
  • 作者:Rapha{\"e}l Berthon ; Mickael Randour ; Jean-Fran{\c{c}}ois Raskin
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:80
  • 页码:121:1-121:15
  • DOI:10.4230/LIPIcs.ICALP.2017.121
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:The beyond worst-case synthesis problem was introduced recently by Bruyère et al. [BFRR14]: it aims at building system controllers that provide strict worst-case performance guarantees against an antagonistic environment while ensuring higher expected performance against a stochastic model of the environment. Our work extends the framework of [Bruyère/Filiot/Randour/Raskin, STACS 2014] and follow-up papers, which focused on quantitative objectives, by addressing the case of omega-regular conditions encoded as parity objectives, a natural way to represent functional requirements of systems. We build strategies that satisfy a main parity objective on all plays, while ensuring a secondary one with sufficient probability. This setting raises new challenges in comparison to quantitative objectives, as one cannot easily mix different strategies without endangering the functional properties of the system. We establish that, for all variants of this problem, deciding the existence of a strategy lies in NP and in coNP, the same complexity class as classical parity games. Hence, our framework provides additional modeling power while staying in the same complexity class.
  • 关键词:Markov decision processes; parity objectives; beyond worst-case synthesis
国家哲学社会科学文献中心版权所有