跳到正文
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 轮精化。

正文 · 原文

Authors: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)

View PDF

Abstract:Autonomous systems choose actions whose outcomes are uncertain and are subject to time constraints. Probabilistic timed automata (PTAs) model exactly this, and verifying one answers a question about the system's decision-making: the maximum probability of reaching a goal, or the minimum probability of reaching a hazard, that a controller can guarantee. Verification normally works over symbolic states, each pairing a discrete location with a region of clock values, and its difficulty is that the best behavior generally varies within such a region. The PRISM verifier's most capable PTA method responds by splitting regions until each is uniform, rebuilding the transitions that reach them and propagating the split backward through the state graph of a stochastic game, a cascade of graph reconstruction that partitions regions the property never depends on. We present SYMAR, which instead makes the value function symbolic: each symbolic state carries a function from sub-regions of its clock region to probability bounds, so refinement is the appearance of new sub-regions in that function, and previously generated states are never split nor their incoming transitions reconstructed. Both sources of PTA nondeterminism, the timing and the choice of actions, are captured implicitly by the preimage computation that produces those sub-regions. Heuristic forward search then bounds how much refinement is done at all, expanding an And-Or graph from the initial state along the most promising behaviors so that effort is confined to the property-relevant fragment, guided by bounds and preferred actions from a single unrefined run of the existing method; a partial-refinement backup keeps the otherwise combinatorial sub-region count lean, and every stored interval provably contains the true probability. On the PRISM PTA benchmarks, whose subproblems recur in autonomous systems (distributed agreement under contention, leader election, and self-configuration without central coordination), SYMAR is up to 108x faster, solves an instance on which the existing method exhausts the time limit, and is markedly less sensitive to the deadline constant, resolving one instance in a 37-node search graph, unchanged as the deadline triples, where the existing method needs 86,380 abstract states and 73 refinement rounds.
Comments: In Proceedings FMAS 2026, arXiv:2611.21375
Subjects: Artificial Intelligence (cs.AI)
Cite as: arXiv:2611.22404 [cs.AI]
  (or arXiv:2611.22404v1 [cs.AI] for this version)
  https://doi.org/10.48550/arXiv.2611.22404

arXiv-issued DOI via DataCite (pending registration)

Journal reference: EPTCS 457, 2026, pp. 110-126
Related DOI: https://doi.org/10.4204/EPTCS.457.8

DOI(s) linking to related resources

Submission history

From: EPTCS [view email] [via EPTCS proxy]
[v1] Tue, 17 Nov 2026 08:45:57 UTC (636 KB)

来源:arXiv cs.AI · arxiv.org