Probabilistic Model Checking Under Partial Observability With Multiple Objectives

多目标部分可观测下的概率模型检验

基本信息

项目摘要

Probabilistic model checking (PMC) is a branch of computer-aided verification focusing on the automated verification of probabilistic models. Markov decision processes (MDPs) are such a prominent probabilistic model. They have their roots in operations research and stochastic control theory and are frequently used for optimisation problems. PMC checks for a given MDP M and a property specification f whether M satisfies f. Under the hood, it uses graph algorithms, value or policy iteration, compact data structures, etc. so as to achieve a fully automated procedure. Effective abstraction, reduction, and symbolic techniques curb the ``curse of dimensionality'' problem. Model checkers such as PRISM and Storm can solve (many) MDPs with billions of states in a few minutes. An important advantage is that PMC automatically obtains an optimal policy for f as a by-product of the verification process. A major assumption in MDPs though is that states are fully observable. That is to say, given a finite sequence of states and actions taken so far (the ``history''), the current state of the MDP is uniquely determined. In many realistic scenarios --- e.g., a robot with sensors that cannot cover the entire environment or an attacker for which the system is a gray box --- this perfect information assumption is too severe. The aim of this project is to investigate the automated verification of probabilistic models under partial observability. We do so by gradually considering models of increasing difficulty: we first consider MDPs in which part of the states is observable and part is not, so-called mixed observable MDPs (MOMDPs). We then consider partially observable MDP (POMDPs) in which each state is partially observable. POMDPs are a prominent model in planning in AI. Finally, we consider partially observable stochastic games (POSGs), a generalisation of POMDPs with an extra player. Our primary focus is to consider specifications that consist of multiple objectives, e.g., target states should be reached with high probability while certainly avoiding dedicated ``bad'' states. As preparatory investigations, we will start off by considering some open questions concerning multiple objectives on just MDPs. Depending on the model at hand, we will consider various types of multiple objectives: mixtures of stochastic and non-stochastic (e.g. always/exist) objectives, multiple objectives under a lexicographic ordering, multiple total reward objectives, objectives on fully as well as partially observable states, and the like. Our investigations will focus on decidability and complexity as well as developing (approximate) algorithms, implementing those algorithms on top of the Storm model checker, and conducting some experimental evaluations.
概率模型检验是计算机辅助验证的一个分支,主要研究概率模型的自动验证。马尔可夫决策过程(MDP)就是这样一个突出的概率模型。他们有自己的根在运筹学和随机控制理论,并经常用于优化问题。PMC针对给定的MDP M和属性规范f检查M是否满足f。 在引擎盖下,它使用图形算法,值或策略迭代,紧凑的数据结构等,以实现完全自动化的过程。有效的抽象、约简和符号技术可以抑制“维数灾难”问题。像PRISM和Storm这样的模型检查器可以在几分钟内解决数十亿个状态的(许多)MDP。一个重要的优点是PMC自动获得f的最优策略作为验证过程的副产品。然而,MDPs的一个主要假设是状态是完全可观察的。也就是说,给定到目前为止所采取的状态和动作的有限序列(“历史”),MDP的当前状态是唯一确定的。在许多现实场景中,例如,一个机器人的传感器不能覆盖整个环境,或者一个攻击者的系统是一个灰色的盒子-这个完美的信息假设太严重了。本计画的目的是研究部分可观测性下机率模型的自动化验证。我们这样做是通过逐渐考虑模型的难度增加:我们首先考虑MDP,其中部分状态是可观察的,部分是不可观察的,所谓的混合可观察MDP(MOMDP)。然后,我们考虑部分可观察的MDP(POMDP),其中每个状态是部分可观察的。POMDPs是AI规划中的一个突出模型。最后,我们考虑部分可观察的随机游戏(POSGs),一个概括的POMDPs与一个额外的球员。我们的主要重点是考虑由多个目标组成的规范,例如,目标国家应该以高概率到达,同时肯定要避免专门的"坏“国家。作为预备性研究,我们将首先考虑一些关于MDPs多目标的开放性问题。根据手头的模型,我们将考虑各种类型的多目标:随机和非随机(例如总是/存在)目标的混合,字典排序下的多个目标,多个总奖励目标,完全以及部分可观察状态的目标,等等。我们的调查将集中在可判定性和复杂性,以及开发(近似)算法,在Storm模型检查器上实现这些算法,并进行一些实验评估。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Professor Dr. Joost-Pieter Katoen其他文献

Professor Dr. Joost-Pieter Katoen的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Professor Dr. Joost-Pieter Katoen', 18)}}的其他基金

Parameter Synthesis for Reliable, Performant and Efficient Wireless Network Protocols
可靠、高性能和高效无线网络协议的参数综合
  • 批准号:
    433044889
  • 财政年份:
    2019
  • 资助金额:
    --
  • 项目类别:
    Research Grants

相似国自然基金

基于术中实时影像的SAM(Segment anything model)开发AI指导房间隔穿刺位置决策的增强现实模型
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
Development of a Linear Stochastic Model for Wind Field Reconstruction from Limited Measurement Data
  • 批准号:
  • 批准年份:
    2020
  • 资助金额:
    40 万元
  • 项目类别:
应用Agent-Based-Model研究围术期单剂量地塞米松对手术切口愈合的影响及机制
  • 批准号:
    81771933
  • 批准年份:
    2017
  • 资助金额:
    50.0 万元
  • 项目类别:
    面上项目
基于Multilevel Model的雷公藤多苷致育龄女性闭经预测模型研究
  • 批准号:
    81503449
  • 批准年份:
    2015
  • 资助金额:
    18.0 万元
  • 项目类别:
    青年科学基金项目
基于非齐性 Makov model 建立病证结合的绝经后骨质疏松症早期风险评估模型
  • 批准号:
    30873339
  • 批准年份:
    2008
  • 资助金额:
    32.0 万元
  • 项目类别:
    面上项目

相似海外基金

Development of model checking technology for dependable distributed systems
可靠分布式系统模型检测技术的开发
  • 批准号:
    23H03370
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Scientific Research (B)
A Tableau-based Approach to Model Checking Temporal Properties for Large-scale Systems
基于 Tableau 的大型系统时态属性模型检查方法
  • 批准号:
    23K19959
  • 财政年份:
    2023
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Research Activity Start-up
Quantitative Model Checking and Synthesis
定量模型检验与综合
  • 批准号:
    2751001
  • 财政年份:
    2022
  • 资助金额:
    --
  • 项目类别:
    Studentship
Vérification par model-checking et synthèse de contrôleur de systèmes temps réel complexes
模型检查和系统时间控制综合的验证
  • 批准号:
    RGPIN-2016-06393
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Discovery Grants Program - Individual
Belief Ratio Approach of Model Checking for Right Censored Data
右删失数据模型检验的置信比法
  • 批准号:
    562116-2021
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    University Undergraduate Student Research Awards
Correct by construction model checking
通过施工模型检查修正
  • 批准号:
    2598915
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Studentship
Software model checking for real-time properties of embedded assembply program with interruptions
带有中断的嵌入式汇编程序实时特性的软件模型检查
  • 批准号:
    21K11824
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
SHF: Small: Transforming Computer Architecture Evaluation with Statistical Model Checking
SHF:小型:通过统计模型检查转变计算机架构评估
  • 批准号:
    2133160
  • 财政年份:
    2021
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
Student Travel Support for Verification, Model Checking, and Abstract Interpretation (VMCAI) Winter School 2020
验证、模型检查和摘要解释 (VMCAI) 2020 年冬季学校学生旅行支持
  • 批准号:
    2004561
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
SaTC: CORE: Small: Techniques for Software Model Checking of Hyperproperties
SaTC:核心:小型:超属性软件模型检查技术
  • 批准号:
    2100989
  • 财政年份:
    2020
  • 资助金额:
    --
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了