跳到正文
arXiv cs.AI· Daniel Bryce (Smart Information Flow Technologies, LLC), Robert P. Goldman (Smart Information Flow Technologies, LLC), David J. Musliner (Smart Information Flow Technologies, LLC), Jeremy Gottlieb (Smart Information Flow Technologies, LLC), John Skovbekk (Smart Information Flow Technologies, LLC)·· 4 小时前AI 评分22

SYMAR:用符号化值函数改进概率时间自动机验证

Symbolic Abstraction Refinement

AI 导读

SYMAR 提出将值函数符号化,让每个符号状态携带从时钟区域子区域到概率边界的函数,从而避免拆分已有状态和重建入边。在 PRISM PTA 基准上,SYMAR 最高快 108 倍,能解出现有方法超时的实例,并在截止时间增至三倍时仍以 37 节点搜索图求解,而现有方法需 86,380 个抽象状态和 73 轮精化。

正文 · AI 翻译

作者:Daniel Bryce(Smart Information Flow Technologies, LLC)、Robert P. Goldman(Smart Information Flow Technologies, LLC)、David J. Musliner(Smart Information Flow Technologies, LLC)、Jeremy Gottlieb(Smart Information Flow Technologies, LLC)、John Skovbekk(Smart Information Flow Technologies, LLC)

查看 PDF

摘要:自主系统选择结果不确定且受时间约束的动作。概率时间自动机(PTA)正是对此建模,验证一个 PTA 可以回答关于系统决策的问题:控制器能够保证的到达目标的最大概率,或到达危险的最小概率。验证通常在符号状态上进行,每个符号状态将一个离散位置与一个时钟值区域配对,其难点在于最优行为通常在这样的区域内会发生变化。PRISM 验证器最强大的 PTA 方法通过拆分区域直到每个区域都均匀来应对,重建到达这些区域的转移,并将拆分沿随机博弈的状态图向后传播,这种图重建的级联会划分性质从不依赖的区域。我们提出 SYMAR,它转而将值函数符号化:每个符号状态携带一个从其时钟区域的子区域到概率界的函数,因此细化就是该函数中出现新的子区域,先前生成的状态永远不会被拆分,其入向转移也不会被重建。PTA 的两种非确定性来源——时序和动作选择——都由产生这些子区域的原像计算隐式捕获。随后启发式前向搜索限制细化的总量,从初始状态沿最有希望的行为扩展一个与或图,使工作量局限于与性质相关的片段,并由现有方法单次未细化运行得到的界和首选动作引导;部分细化回传使原本组合爆炸的子区域数量保持精简,且每个存储的区间都可证明包含真实概率。在 PRISM PTA 基准上(其子问题在自主系统中反复出现:争用下的分布式一致、领导者选举以及无中心协调的自配置),SYMAR 最高快 108 倍,求解了一个现有方法耗尽时间限制的实例,并且对截止时间常数的敏感性明显更低,在一个 37 节点搜索图中求解了一个实例,当截止时间增至三倍时该图保持不变,而现有方法需要 86,380 个抽象状态和 73 轮细化。
评论: 载于 Proceedings FMAS 2026,arXiv:2611.21375
主题: 人工智能(cs.AI)
引用为: arXiv:2611.22404 [cs.AI]
  (或 arXiv:2611.22404v1 [cs.AI] 为此版本)
  https://doi.org/10.48550/arXiv.2611.22404

由 DataCite 颁发的 arXiv DOI(待注册)

期刊 参考: EPTCS 457, 2026, pp. 110-126
相关 DOI: https://doi.org/10.4204/EPTCS.457.8

链接到相关资源的 DOI

提交历史

来自:EPTCS [查看邮件] [通过 EPTCS 代理]
[v1] 2026 年 11 月 17 日星期二 08:45:57 UTC(636 KB)

来源:arXiv cs.AI · arxiv.org