betaFeedback

WorksComputer Science

Symbolic Abstraction Refinement

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.

Introduction

Autonomous systems by their very nature make decisions about what actions to take and when to take them, and they can sometimes fail. A critical aspect of designing these systems is ensuring they can avoid foreseeable failures. Probabilistic timed automata (PTAs) are a natural fit for these concerns. PTAs provide a powerful formalism for modeling real-time systems with uncertainty, finding application in autonomous systems [20], wireless protocols [16, 14], security protocols [18, 23], and embedded control systems [21]. More broadly, probabilistic model checking is applied throughout autonomy (synthesising mission controllers for unmanned aerial vehicles [9, 3], verifying human–robot handover tasks [27], and assuring robots whose perception components are learned [1]) with deployments in mobile service robotics and underwater vehicles [13]. Such systems act under deadlines, so the timing of their decisions is part of what must be verified.

A PTA defines an MDP over symbolic states, pairs of a location and a clock zone, and verification amounts to computing the optimal reachability probability over that symbolic state space. A PTA separates two kinds of choice: a controller selects which action to take, and a scheduler determines when actions occur. The actions have stochastic outcomes and event timing can be partially controlled or even adversarial. The optimal reachability probability is then a guarantee about that decision-making: the maximum probability of reaching a goal any controller can achieve, or the minimum probability of reaching a hazard any controller can be held to, against a worst-case environment. Verifying the decisions themselves rather than a nondeterministic over-approximation requires resolving both choices separately, which is what makes PTA verification harder than verification of the underlying untimed MDP. The benchmarks of § 8 exercise exactly the capabilities an autonomous system depends on: agreeing on a leader, resolving contention for a shared channel, configuring an address without central coordination, and completing an exchange in the presence of an adversary, each under a deadline, and each a case where the answer is a probability rather than a yes or no.

Existing methods compute a scalar value function. Whether the symbolic state space is treated as an MDP and solved by value iteration [15, 17] or as a stochastic game in which one player chooses a concrete state within the zone and the other chooses among the actions then enabled [11], each symbolic state is assigned a single value: one probability bound, or one pair of bounds, per (location, zone) pair. Since the optimal behavior generally varies within a zone, such a value is sound only once the zone is fine enough that one behavior is optimal throughout it. Achieving that means splitting the state into finer states and rebuilding the transitions that reach it, and because each predecessor was solved against the coarser partition, the split propagates backward through the reachable state space. This global refinement cascade is the scalability bottleneck: it is driven by the representation’s inability to express variation within a zone, not by the property, so effort is spent partitioning regions the property never depends on.

SYMAR (SYMbolic Abstraction Refinement) keeps the abstraction-refinement insight of the stochastic games (SG) method [11], that a symbolic state admitting several distinct optimal behaviors must be refined before its bounds converge, while changing two things about how refinement is carried out. First, it is performed symbolically, in the value function. The central object is V:Zones→[0,1]2V : \mathrm{Zones} \to[0,1]^2, a zone-valued probability function mapping sub-regions of a state’s clock zone to probability bounds on reaching the target: where a scalar method holds one interval per state, VV holds a partition of that state’s zone into cells, each with its own interval, and refinement is the appearance of new cells. Both sources of nondeterminism are handled implicitly by the preimage computation that defines the value of a transition (§ 4), so the scheduler’s zone distinctions emerge from the geometry of the preimage instead of being materialized as states, which also removes the need for an explicit two-player game, since a single node type per symbolic state suffices. The cascade does not disappear: a refinement still propagates to predecessors whose bounds came from the coarser value it replaces. What changes is its content: in the SG method predecessors are split and their transitions rebuilt, whereas in SYMAR the cascade revises values while leaving existing states and transitions intact.

Second, refinement is directed by heuristic forward search. SYMAR grows an And-Or graph forward from the initial state with AO∗AO^* [19, 22], expanding along the best partial solution and backpropagating VV through ancestors. Where the SG method refines globally and uniformly, AO∗AO^* refines only where the property-relevant probability mass lies, leaving irrelevant regions at their initial coarse bounds. The two changes are complementary: symbolic refinement makes each refinement cheap, and forward search makes most refinements unnecessary. Two costs come with the design. A state’s value is computed from a cross product over its successors’ sub-regions, whose size grows combinatorially, so SYMAR refines each state partially, committing to the sub-regions that currently determine the bounds and refining further only once they prove to depend on what was deferred. And because forward search is only as good as its guidance, SYMAR takes admissible bounds and preferred actions from a single unrefined run of the SG method, so a coarse solution directs the symbolic one. Pmin⁡P_{\min} queries are supported as the dual of Pmax⁡P_{\max} (maxima become minima and upper bounds become lower bounds), with every extremum-selection site branching on the query direction.

We prove that every interval SYMAR stores brackets the optimal probability of acting at each valuation its cell represents, and that the reported root interval contains the true answer, independently of convergence. Empirically, on the PRISM PTA benchmarks SYMAR is up to 108×108\times faster than the SG method and solves a csma instance on which that method exhausts the 20 minute time limit; its runtime is far less sensitive to the deadline constant, resolving one firewire instance in a 37-node search graph where the SG method needs 86,380 abstract states over 73 refinement rounds.

Background

We define PTAs and the associated reachability problem solved by this work.

Definition 1 (PTA). A PTA is a tuple P=(X,L,l0,Act,inv,g,prob)P = (\mathcal{X}, L, l_0, Act, inv, g, prob) where:

  • X\mathcal{X} is a finite set of non-negative real clock variables;

  • LL is a finite set of locations and l0∈Ll_0 \in L is the initial location;

  • ActAct is a finite set of actions;

  • inv:L→ΦXinv : L \to\Phi_{\mathcal{X}} is the invariant condition;

  • g:L×Act→ΦXg : L \times Act \to\Phi_{\mathcal{X}} is the guard of an act in a state;

  • prob:L×Act→Dist⁡(2L×2X)prob : L \times Act \to\operatorname{Dist}(2^{L \times2^{\mathcal{X}}}) is the probabilistic transition function, a distribution over location-reset pairs, or outcomes, outcomes(l,a)(l,a). Outcomes are ordered, so we may refer to the ithi^{\mathrm{th}} outcome of aa in ll, and we write resets(l,a,i)(l,a,i) for the clocks it resets. We use outcomes(l,a)(l,a) for both the outcomes and their indices.

A clock valuation v∈RXv \in\mathbb{R}^{\mathcal{X}} assigns each clock a value, and a state (l,v)∈L×RX(l,v) \in L \times\mathbb{R}^{\mathcal{X}} pairs a location with a valuation. Guards and invariants are clock constraints, conjunctions and disjunctions of atoms x≤cx \le c, c≤xc \le x and x+c1≤y+c2x+c_1 \le y+c_2 with c∈Qc \in\mathbb{Q}. A conjunction of atoms denotes a convex set of valuations called a zone; a disjunction denotes a union of zones, which need not be convex. We write ΦX\Phi_{\mathcal{X}} for the constraints over X\mathcal{X}, and say a state satisfies a constraint when its valuation does.

We use the PTA PP of Figure 1 as a running example. It has X={x,y}\mathcal{X} = \{x,y\}, L={l0,…,l3}L = \{l_0,\ldots,l_3\}, Act={a,b,c}Act = \{a,b,c\} and trivial invariants, with the guards and resets shown in the figure.

Figure 1. Example PTA, adapted from [11]. The aa transition is probabilistic, leading to l1l_1 and l2l_2. Taken immediately, cc in l1l_1 reaches the target l3l_3; taken after one time unit, cc in l2l_2 does. No execution lets both outcomes of aa reach l3l_3.

The semantics of a PTA is a probability over its traces, strings of two kinds of transition: time may elapse, or an action may occur. Only the actions carry probability, so a trace’s probability is the product of the action probabilities along it. Two forms of nondeterminism must be resolved before that product is determined: when an action occurs, fixed by the duration of the preceding time elapse and referred to as scheduler nondeterminism, and which enabled action occurs, referred to as controller nondeterminism. A policy resolves both, making a decision at each nondeterministic choice, and the reachability probability we seek is an optimum over policies. A policy still induces a distribution over uncountably many traces, since time may advance by any real amount, but the probability of reaching a target depends only on the sequence of action occurrences a trace contains, not on the exact clock valuations along it. Traces are therefore grouped into equivalence classes by those sequences, and the probability of a class is the product of its action probabilities. The definitions below make the two transitions precise and state the problem.

Definition 2 (Time transition). A time transition, (l,vi)→n(l,vj)(l,v_i) \xrightarrow{n} (l,v_j) models the elapse of n∈R≥0n \in\mathbb{R}_{\ge0} time units, incrementing every clock by nn without changing location: vj[x]=vi[x]+nv_j[x] = v_i[x] + n for every x∈Xx \in\mathcal{X}. For this transition to be valid, viv_i and vjv_j must both satisfy inv(l)inv(l), which entails that every intermediate valuation does too.

Definition 3 (Jump transition). A jump transition, (li,vi)→a,k(lj,vj)(l_i,v_i) \xrightarrow{a,k} (l_j,v_j) models the occurrence of an action, aa. For this transition to be valid, viv_i must satisfy g(li,a)g(l_i,a), prob(li,a)[k]>0prob(l_i,a)[k] > 0, vj[x]=vi[x]v_j[x] = v_i[x] if x∉resets(li,a,k)x \notin resets(l_i,a,k), vj[x]=0v_j[x] = 0 if x∈resets(li,a,k)x \in resets(l_i,a,k), and vjv_j satisfies inv(lj)inv(l_j). The probability of this transition, given that aa occurs in viv_i, is the probability of the kthk^{\mathrm{th}} outcome of (li,a)(l_i,a), and is independent of the clock values so long as they satisfy the guard.

Definition 4 (Probabilistic Reachability). The probabilistic reachability problem is to find the maximum (minimum) probability, over all policies, of reaching a target F⊆LF \subseteq L from the initial state l0l_0 of PTA PP, denoted pPmax⁡(F)p_P^{\max}(F) (pPmin⁡(F)p_P^{\min}(F)). Under a given policy this is the probability of the set of trace equivalence classes ending in FF.

Symbolic State MDP

A PTA defines an MDP over symbolic states. Each symbolic state z=(l,ζ)z = (l,\zeta) is a pair of a location ll and a clock zone ζ\zeta (a set of clock valuations expressed as a clock constraint). The symbolic state z0=(l0,ζ0)z_0 = (l_0,\zeta_0), where ζ0=inv(l0)∧↗x∈X(x=0)\zeta_0 = inv(l_0) \land\mathop{\nearrow}_{x \in\mathcal{X}} (x = 0), is the initial symbolic state representing all clock valuations reachable from x=0x = 0 for all x∈Xx \in\mathcal{X} by time transitions. The operators ↗ζ\nearrow\zeta and ↙ζ\swarrow\zeta let time in ζ\zeta advance forward or backward. The operators reset(ζ,X)reset(\zeta,X) and unset(ζ,X)unset(\zeta,X) set the clocks in XX to zero, or to their possible values before a reset; they are distinct from resets(l,a,i)resets(l,a,i), which names the set of clocks that outcome ii of aa in ll resets. The successor and predecessor functions below are built from these.

Definition 5 (Symbolic Successor Function). The successor function identifies the states z′z' reached by an outcome of aa when executed in z=(l,ζ)z=(l,\zeta). The jump step post⁡J\operatorname{post}_{\mathrm{J}} restricts to valuations meeting the guard and applies the resets; the temporal step post⁡T\operatorname{post}_{\mathrm{T}} adds the valuations reachable by letting time elapse within the invariant:

post⁡((l,ζ),a)={post⁡((l,ζ),a,i)∣i∈[1,n]}\operatorname{post}((l,\zeta),a)=\{\operatorname{post}((l,\zeta),a,i)\mid i\in[1,n]\}
post⁡((l,ζ),a,i)=post⁡T(post⁡J((l,ζ),a,i))\operatorname{post}((l,\zeta),a,i)=\operatorname{post}_{\mathrm{T}}(\operatorname{post}_{\mathrm{J}}((l,\zeta),a,i))
post⁡J((l,ζ),a,i)=(l′,reset⁡(ζ∧g(l,a),resets⁡(l,a,i)))\operatorname{post}_{\mathrm{J}}((l,\zeta),a,i)=(l',\operatorname{reset}(\zeta\land g(l,a),\operatorname{resets}(l,a,i)))
post⁡T((l,ζ))=(l,inv⁡(l)∧↗ζ)\operatorname{post}_{\mathrm{T}}((l,\zeta))=(l,\operatorname{inv}(l)\land\nearrow\zeta)

where n=∣outcomes⁡(l,a)∣n=|\operatorname{outcomes}(l,a)| is the number of outcomes of aa in ll, and l′l' is a successor location.

Definition 6 (Symbolic Predecessor Function). The predecessor function identifies the valuations of z=(l,ζ)z=(l,\zeta) from which taking aa can reach the given zone in every outcome. Per outcome, pre⁡T\operatorname{pre}_{\mathrm{T}} runs time backward within the successor’s invariant and pre⁡J\operatorname{pre}_{\mathrm{J}} inverts that outcome’s resets and imposes the guard and source invariant; the results are intersected, since one valuation must serve all nn outcomes of the same occurrence of aa:

pre⁡((l,ζ),a,{(l1,ζ1),…,(ln,ζn)})=ζ∧⋀i=1npre⁡J(l,a,pre⁡T((li,ζi)),i)\operatorname{pre}((l,\zeta),a,\{(l_1,\zeta_1),\ldots,(l_n,\zeta_n)\})=\zeta\land\bigwedge_{i=1}^{n}\operatorname{pre}_{\mathrm{J}}(l,a,\operatorname{pre}_{\mathrm{T}}((l_i,\zeta_i)),i)
pre⁡T((li,ζi))=inv⁡(li)∧↘ζi\operatorname{pre}_{\mathrm{T}}((l_i,\zeta_i))=\operatorname{inv}(l_i)\land\searrow\zeta_i
pre⁡J(l,a,ζ′,i)=g(l,a)∧inv⁡(l)∧unset⁡(ζ′,resets⁡(l,a,i))\operatorname{pre}_{\mathrm{J}}(l,a,\zeta',i)=g(l,a)\land\operatorname{inv}(l)\land\operatorname{unset}(\zeta',\operatorname{resets}(l,a,i))

The key difficulty in computing optimal reachability probabilities over this MDP is that in a symbolic state z=(l,ζ)z=(l,\zeta), the available actions and their successors may depend on which sub-zone of ζ\zeta the clock valuation lies in. The guard g(l,a)g(l,a) and the reset together determine which valuations can reach which successor zone. This means the optimal probability is not uniform over ζ\zeta: it varies by sub-region. For example, in the initial symbolic state (l0,x=y)(l_0,x=y) of the running example, taking action aa immediately (when 0=x=y0=x=y) vs. after a delay (when 0<x=y0<x=y) leads to different successor zones with different probabilities.

The established response, and the state of the art for PTA verification, is the stochastic games (SG) method of Kwiatkowska et al. [11]; we describe it only as far as the contrast with SYMAR requires. It assigns each symbolic state a single pair of bounds [lb,ub][lb,ub], obtained from a game in which one player picks a concrete state inside the zone and the other picks among the actions then enabled: resolving both cooperatively gives ubub, resolving the first adversarially gives lblb. The interval is always sound, and its width indicates the utility in refining it: a wide interval means the state is too abstract. The remedy is to split zz into sub-regions on which the players no longer disagree and rebuilding the transitions that reach them; iterating split-and-resolve converges to the true probability. The cost is that a split is not local: every symbolic state whose transitions reach zz was solved against the coarser partition, so each must be updated in turn, and those updates may force further splits, a cascade that can reach back to the initial state over many refinement rounds.

Figure 2(a,Figure 2b) illustrates the pattern. In the initial abstraction (a), the states reached by action aa carry uninformative bounds [0,1][0,1]: whether l1l_1 or l2l_2 leads to the target depends on when aa was taken, a distinction those states do not make. Refining (l1,0≤x=y)(l_1,0\leq x=y) and (l2,0≤x≤y)(l_2,0\leq x\leq y) (b) makes the distinction and the bounds tighten to exact values. Note what this costs: the transitions out of z0z_0 must be rebuilt to point at the new sub-states, even though z0z_0 itself was never the state in question. That obligation is the cascade.

Figure 2. Stochastic game and symbolic formulations of the example PTA. (a) The initial game. (b) After refining (l1,0≤x=y)(l_1,0 \le x = y) into (l1,0=x=y)(l_1,0 = x = y) and (l1,0<x=y)(l_1,0 < x = y), and (l2,0≤x≤y)(l_2,0 \le x \le y) into (l2,x=0∧y=1)(l_2,x = 0 \land y = 1) and (l2,0≤x≤y∧(x>0∨y≠1))(l_2,0 \le x \le y \land(x > 0 \lor y \ne1)). Symbolic states are labeled with their bounds, e.g. [0.6,0.6][0.6,0.6]; the target state is gray; small black circles denote joint symbolic transitions, with edges labeled by action and intervals showing the intermediate values from which state bounds are computed. (c) SYMAR’s symbolic backpropagation over the same PTA: the distinctions (b) obtains by splitting states appear instead as cells of the zone-valued function attached to the unsplit states, so a graph more similar to (a) is retained throughout.

SYMAR adapts the concept of the SG method, where a symbolic state whose zone admits several distinct optimal behaviors is too coarse and must be refined. Instead of splitting symbolic states, SYMAR associates a zone-valued probability function Vz:Zones⁡(X)→[0,1]2V_z : \operatorname{Zones}(\mathcal{X}) \to[0,1]^2 with each symbolic state zz. This function maps sub-regions of ζ\zeta to probability bounds and is computed directly from the preimage computation during backpropagation, as we describe in the next section. The partition that the SG method would materialize as new states appears instead as the cell structure of VzV_z.

To be precise about what this eliminates: the refinement still happens and still propagates, since when VzV_z acquires a finer cell structure every predecessor holds bounds derived from the coarser function and must be recomputed. SYMAR therefore has a cascade too, but it revises values over a graph whose existing states and transitions are left intact, reusing the preimages cached on them, rather than rebuilding the graph the next round of value iteration runs over. The saving is not the absence of backward propagation but the absence of reconstruction. Section 5 then adds the second ingredient, forward search, which decides which symbolic states are worth refining at all.

Zone-Valued Probability Functions

The primary insight of SYMAR is that the scheduler’s zone distinctions, which the SG method materializes through state splitting, can instead be captured directly in the value function. We associate with each symbolic state zz a zone-valued probability function:

Definition 7 (Zone-Valued Probability Function). A zone-valued probability function for symbolic state zz is a finite set

Vz={(ζ1,[lb1,ub1]),…,(ζk,[lbk,ubk])}V_z = \{(\zeta_1,[lb_1,ub_1]),\ldots,(\zeta_k,[lb_k,ub_k])\}

where {ζi}\{\zeta_i\} partition the clock zone of zz. Each pair (ζi,[lbi,ubi])(\zeta_i,[lb_i,ub_i]) associates a sub-region of the state zone

with bounds on the probability of reaching the target when an action is taken at a valuation in that sub-region now, before any further delay. Delay before an action enters through the preimage (Definition 6), which maps each successor cell back through post-jump elapse, and, at the root only, through time closure (§ 5.1). We call VzV_z a cell map: each (ζi,[lbi,ubi])(\zeta_i,[lb_i,ub_i]) is a cell.

Three cases are immediate. A symbolic state whose location lies in the target set FF has Vz={(ζ,[1,1])}V_z=\{(\zeta,[1,1])\}, and one from which no action is ever enabled has Vz={(ζ,[0,0])}V_z=\{(\zeta,[0,0])\}; both are exact over the entire zone. A symbolic state whose value has not yet been computed carries the uninformative Vz={(ζ,[0,1])}V_z=\{(\zeta,[0,1])\}, a single cell spanning the zone. Every other symbolic state takes its bounds from its successors, via the two definitions that follow.

Transition Value VθV_\theta

Let θ=(z,a,{z1,…,zn})\theta=(z,a,\{z_1,\ldots,z_n\}) be a symbolic transition, where ziz_i is the successor for outcome ii and carries value function VziV_{z_i}. Then

Vθ=M{(pre⁡(z,a,ζ(c)),∑i=1nprob⁡(l,a,i)⋅ci)|c∈C(θ), pre⁡(z,a,ζ(c))≠⊥}(1)V_\theta=\mathop{\mathrm{M}}\left\{\left(\operatorname{pre}(z,a,\zeta(c)),\sum_{i=1}^{n}\operatorname{prob}(l,a,i)\cdot c_i\right)\mathrel{\middle|}c\in C(\theta),\ \operatorname{pre}(z,a,\zeta(c))\ne\perp\right\} \tag*{(1)}

where C(θ)=Vz1×⋯×VznC(\theta)=V_{z_1}\times\cdots\times V_{z_n} is the cross product of the successors’ value functions, cic_i is the probability interval of the cell cc selects from VziV_{z_i}, and ζ(c)\zeta(c) is the tuple of zones of those cells.

A combination c∈C(θ)c\in C(\theta) picks one cell from each successor, hypothesizing that outcome ii lands in the sub-region cc selects there. Its preimage pre⁡(z,a,ζ(c))\operatorname{pre}(z,a,\zeta(c)) is the set of valuations in zz for which that hypothesis holds: those where aa is enabled and every outcome lands in its selected zone. Combinations whose preimage is empty (⊥\perp) are discarded, since no valuation can realize them. Over the valuations that remain, the outcome intervals are fixed, so the transition’s value there is their expectation under prob⁡(l,a,⋅)\operatorname{prob}(l,a,\cdot), computed by interval arithmetic. Finally M\mathrm{M} resolves the cells against one another, keeping the higher ubub (then lblb) wherever two preimages overlap.

Both sources of nondeterminism enter through the preimage. Distinct combinations have distinct preimages, so the cross product partitions zz by which timing and action choice is optimal: the refinement, obtained without splitting the state. The cost is that ∣C(θ)∣|C(\theta)| is a product over successors; § 5 bounds it.

Symbolic State Value VzV_z

VzV_z is the pointwise maximum over applicable transitions: for each sub-zone ζ′\zeta',

Vz(ζ′)=max⁡θVθ(ζ′)V_z(\zeta')=\max_{\theta}V_\theta(\zeta')

where the max is by ubub then lblb, merging the zone partitions of all applicable transitions and taking the best-action value in each sub-region. A valuation at which no applicable transition is enabled lies in no cell of any VθV_\theta and receives [0,0][0,0], so VzV_z covers the whole zone of zz even though each VθV_\theta covers only the region where aa is enabled.

Running Example

Figure 2(c) illustrates the SYMAR symbolic backpropagation for the running example. The successors of transition θa\theta_a (action aa from z0=(l0,0≤x=y)z_0=(l_0,0\le x=y)) are z1=(l1,0≤x=y)z_1=(l_1,0\le x=y) and z2=(l2,0≤x≤y)z_2=(l_2,0\le x\le y). Their value functions are

Vz1={(ζ11,[1,1]),(ζ12,[0,0])}Vz2={(ζ21,[1,1]),(ζ22,[0,0])}\begin{aligned} V_{z_1} &= \{(\zeta_{11}, [1,1]), (\zeta_{12}, [0,0])\}\\ V_{z_2} &= \{(\zeta_{21}, [1,1]), (\zeta_{22}, [0,0])\} \end{aligned}

for ζ11=(0=x=y)\zeta_{11} = (0 = x = y), ζ12=(0<x=y)\zeta_{12} = (0 < x = y), ζ21=(x=0∧y=1)\zeta_{21} = (x = 0 \land y = 1) and ζ22=(0≤x≤y∧(x>0∨y≠1))\zeta_{22} = (0 \le x \le y \land(x > 0 \lor y \ne1)), the probabilities for different clock valuations in each successor.

The combinations C(θa)C(\theta_a) are all pairs of one element from Vz1V_{z_1} and one from Vz2V_{z_2}, so the four combinations give

pre⁡(z0,a,{ζ11,ζ21})=⊥pre⁡(z0,a,{ζ12,ζ21})=(1=x=y)0.6[0,0]+0.4[1,1]=[0.4,0.4]pre⁡(z0,a,{ζ11,ζ22})=(0=x=y)0.6[1,1]+0.4[0,0]=[0.6,0.6]pre⁡(z0,a,{ζ12,ζ22})=(0<x=y≠1)0.6[0,0]+0.4[0,0]=[0,0]\begin{aligned} \operatorname{pre}(z_0,a,\{\zeta_{11},\zeta_{21}\}) &= \perp\\ \operatorname{pre}(z_0,a,\{\zeta_{12},\zeta_{21}\}) &= (1 = x = y) && 0.6[0,0] + 0.4[1,1] = [0.4,0.4]\\ \operatorname{pre}(z_0,a,\{\zeta_{11},\zeta_{22}\}) &= (0 = x = y) && 0.6[1,1] + 0.4[0,0] = [0.6,0.6]\\ \operatorname{pre}(z_0,a,\{\zeta_{12},\zeta_{22}\}) &= (0 < x = y \ne1) && 0.6[0,0] + 0.4[0,0] = [0,0] \end{aligned}

The first combination is infeasible: reaching ζ11\zeta_{11} requires taking aa at x=y=0x = y = 0 and reaching ζ21\zeta_{21} requires taking it at x=y=1x = y = 1, which are mutually exclusive. The second and third preimages cover disjoint sub-zones (1=x=y(1 = x = y and 0=x=y)0 = x = y), while the fourth covers the remainder 0<x=y≠10 < x = y \ne1. Together they partition z0=(0≤x=y)z_0 = (0 \le x = y) into three cells, matching the zone-valued function shown in Figure 2(c). Since θa\theta_a is the only transition applicable in z0z_0, Vz0=VθaV_{z_0} = V_{\theta_a}, and the initial valuation x=y=0x = y = 0 has bound [0.6,0.6][0.6,0.6], the correct answer, which both the SG and backward-reachability methods also return. No state was split: the partition of z0z_0 by timing choice emerged from the preimage computation.

Minimum Reachability

For Pmin⁡P_{\min} queries, VzV_z takes the pointwise minimum over applicable transitions instead of the maximum, and the M of (1) inverts correspondingly. The expectation is direction-free, as are the [0,0][0,0] bounds of a symbolic state with no enabled action: “unreachable under every policy” holds regardless of the query direction. Every remaining extremum-selection site branches on the query direction; § 5 notes where this matters once the value function is embedded in a search.

Forward AO* Search

Section 4 made each refinement cheap by keeping it in the value function. Forward search makes most refinements unnecessary. SYMAR employs And-Or search to explore the symbolic state space and compute bounds on the probability of satisfying reachability properties, expanding nodes in best-first order so that refinement effort is spent only where it can still change the answer at the root.

The Search Algorithm

The two value functions of Section 4 correspond to the two node types of an And-Or graph, which is what lets AO* schedule their computation. Or-nodes represent symbolic states and store VzV_z; And-nodes represent probabilistic transitions and store VθV_\theta. Figure 3 gives the control structure, and the paragraphs below refer to its line numbers.

SYMAR’s control structure

Figure 3. SYMAR’s control structure. SOLVESG returns admissible bounds hh and helpful actions from the unrefined stochastic game; the loop alternates forward expansion at the frontier with symbolic backpropagation over the ancestors, and terminates on the origin cell of the root.

Expansion (lines 7–9) adds Or-nodes for symbolic states not previously generated; backup (lines 10–12) adds cells to VzV_z and VθV_\theta without splitting the states that hold them or reconstructing their incoming

SYMAR(P,F,\varepsilon)

1: $(h,\mathit{Help}) \leftarrow \mathit{SOLVESG}(P)$                                      // unrefined abstraction
2: $r \leftarrow$ Or-node for $z_0$, seeded from $h$
3: **loop**
4: &nbsp;&nbsp;&nbsp;&nbsp;$N \leftarrow$ unexpanded frontier of the best partial solution from $r$
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $N = \varnothing$ **then** close the cyclic component below $r$                         // collapse, then relax ungated
6: &nbsp;&nbsp;&nbsp;&nbsp;**else**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B \leftarrow \{u \in N \mid u$ reached by an action in $\mathit{Help}$ of its parent$\}$, or the best single node if empty
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expand each $u \in B$: an And-node per enabled action, an Or-node per outcome                         // growth
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;seed each new state: $[1,1]$ if in $F$, $[0,0]$ if no action is enabled, else $h$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** each ancestor of $B$ bottom-up over the affected ancestor subgraph
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;And-node $\theta = (z,a,\{z_i\})$: $V_\theta \leftarrow M\{(\operatorname{pre}(z,a,\zeta(c)), \sum_i \operatorname{prob}(l,a,i)\cdot c_i)\}$                         // refinement
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;over $c \in \prod_i V_{z_i}$ with nonempty preimage, or its best two cells plus a hull
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Or-node $z$: $V_z \leftarrow M\{V_\theta \mid \theta$ applicable$\}$, time-closed if $z = r$
13: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\operatorname{GAP}(\operatorname{ORIGINCELL}(V_r)) \le 2\varepsilon$ **then return** $\operatorname{ORIGINCELL}(V_r)$

transitions. The SG method’s refinement does both at once, which is why a split there propagates structurally; in SYMAR only expansion adds nodes, and at the frontier rather than behind it. A cascade still reaches the ancestors whose bounds derived from a coarser value, but it revises cells on existing edges.

Time closure applies only at the root. A cell’s value is available to any valuation that can reach it by letting time elapse within the state’s zone; for a non-root state that rewinding is already performed by the incoming transition, whose preT term maps a successor cell back through post-jump elapse. The root has no incoming transition, which is why it needs the step and no other node does.

Closing (line 5) handles a graph in which every node is expanded yet the bounds have not met. Members that cannot reach positive-probability mass outside the component are pinned to [0,0][0,0], and the remainder is relaxed with the ε\varepsilon gate removed. The ε\varepsilon gate is the test that lets a node stop being updated once its interval is narrower than ε\varepsilon, which keeps the backup from repeatedly re-deriving values that can no longer change the answer. On a cycle the gate can freeze a loose bound that backup would otherwise tighten, which is why closing removes it. § 6 explains what this does and does not guarantee.

Termination (line 13) reads one cell, not the whole root function. VrV_r may hold several cells, and non-root cells legitimately carry higher values mid-run, so the maximum over VrV_r is not the answer to the query. ORIGINCELL⁡(Vr)\operatorname{ORIGINCELL}(V_r) selects the cell whose zone contains the initial valuation, all clocks zero, which is the only cell the query asks about; GAP is the width ub−lbub-lb of that cell. The interval [lb,ub][lb,ub] is sound, so the true value lies somewhere in it, and its midpoint is then within (ub−lb)/2(ub-lb)/2 of that value. Comparing the gap against 2ε2\varepsilon therefore certifies a midpoint answer within ε\varepsilon of the truth, whereas comparing against ε\varepsilon would demand a midpoint within ε/2\varepsilon/2, twice the precision the tolerance asks for. The certificate is sound but a posteriori: the interval is valid at every iteration, so an answer returned under the test is always within ε\varepsilon, but nothing guarantees the gap will reach 2ε2\varepsilon. On a cycle a loose bound may never tighten, in which case the search reports the sound interval rather than a converged value. § 6 gives the details.

Games Heuristic

The two methods compose rather than compete. Before AO* begins, SYMAR runs the SG method on the unrefined PTA to compute per-zone bounds hzh_z, which initialize the VzV_z of open nodes. One fixpoint solve on the coarsest abstraction is far cheaper than the refinement cascade it would otherwise drive, since it is the cascade rather than the initial abstraction that dominates the SG method’s cost. It is not cheap in absolute terms, however: that abstraction spans the whole reachable symbolic state space, and on the larger models this solve, not the search, dominates SYMAR’s runtime, as § 8 quantifies.

The SG method is itself an interval method: solving the unrefined abstraction with both players cooperating gives an upper bound, and with the abstraction player adversarial a lower bound, so each symbolic state receives a sound interval [lbh,ubh][lb_h,ub_h] containing the optimal probability at every valuation it groups. SYMAR seeds an open node only with the side its query optimizes, ubhub_h for Pmax⁡P_{\max} and lbhlb_h for Pmin⁡P_{\min} (the other side stays 0, respectively the same upper cap). Cells bound the value of acting immediately, which delay can only improve for the optimizing player, so a bound on the optimum is sound for cells on exactly this side (Section 6); this is why Theorem 1 may treat the seed as sound. The side must also be admissible or the best-first search order is corrupted. It is: an unrefined state groups valuations that may take different optimal actions, so for Pmax⁡P_{\max} the SG upper bound over-approximates the true optimum at every valuation, and dually for Pmin⁡P_{\min}. Beyond the bounds, the SG solution also records which actions attain them, which the next subsection puts to use.

Helpful Actions

The SG solve yields more than a bound per state: for each abstract state the choice set attaining the optimum is also available. By analogy with heuristic-search planning [8] we call these the state’s helpful actions. SYMAR uses them as a focus set governing how many nodes are expanded per iteration: instead of expanding one frontier node it expands every frontier node reached by a helpful action at once, falling back to a single node when none is helpful. This lets the relaxation drive the rate of expansion rather than only the order, which matters because backpropagation is expensive relative to expansion: each round recomputes cross-product preimages along the ancestor path, so amortizing one backpropagation over several expansions is a real saving.

Unlike the planning technique it is named for, this does not restrict the successor set: an Or-node always generates a child for every enabled transition, the frontier is recomputed each iteration, and neither the backed-up values nor the best-partial-solution walk consult helpfulness. Admissibility and termination are therefore independent of the quality of the helpful-action sets, which is what makes it safe to take guidance from an unrefined abstraction whose choices may be wrong.

Best-Only Backup: Partial Refinement

Forward search decides which symbolic states to refine; best-only backup decides how far. The refinement one And-node induces is the full cell structure of VθV_\theta, one cell per feasible combination in C(θ)C(\theta), whose size grows exponentially in the outcomes and in the cells per successor. Committing to that partition at every backup is usually wasted, since most combinations describe sub-regions whose values never reach the root. Best-only backup instead commits to the load-bearing sub-regions and summarizes the rest, exporting at most three cells: the combination c∗c^{*} with the highest upper bound, the combination c†c^{\dagger} with the highest lower bound if distinct, whose upper bound is raised to cover any summarized combination overlapping it, and a hull covering the remainder with bounds [0,pˉ∗][0,\bar{p}^{*}], where pˉ∗\bar{p}^{*} is the upper bound of the best summarized combination. For Pmin⁡P_{\min} every extremum inverts and the hull becomes a pessimistic floor [p∗,1][p^*,1].

The hull is deliberately conservative: its bound is at least as loose as any summarized combination’s true value, and hull cells are barred from being marked solved, so the deferred part can never masquerade as converged. Partial refinement becomes full exactly when the bounds prove to depend on it: if the best behavior runs through the hull, the And-node is permanently promoted to enumerating all of C(θ)C(\theta). This is the refine-on-demand discipline of the search as a whole, applied within one backup.

Correctness

Write P∗(z,v)P^*(z,v) for the true optimal probability of reaching FF from the concrete state (l,v)(l,v) of z=(l,ζ)z=(l,\zeta), the maximum over policies for a Pmax⁡P_{\max} query and the minimum for a Pmin⁡P_{\min} one. The quantity the query asks for is P∗P^* at the initial state: pPopt(F)p_P^{\mathrm{opt}}(F) denotes pmax⁡(F)p^{\max}(F) or pmin⁡(F)p^{\min}(F) of Definition 4 according to that direction, so pPopt(F)=P∗(z0,0)p_P^{\mathrm{opt}}(F)=P^*(z_0,\mathbf{0}) with 0\mathbf{0} the all-zero valuation.

The backup works with a second, narrower quantity. Write P0(z,v)P^0(z,v) for the optimal probability when an action is taken at vv immediately, with no delay first: 11 if l∈Fl\in F, and 00 if no action is enabled at vv. Delay is the only difference, so

P∗(z,v)=opt⁡d≥0, v+d∈ζP0(z,v+d),P^*(z,v)=\operatorname{opt}_{d\ge0,\ v+d\in\zeta} P^0(z,v+d),

with opt the supremum for Pmax⁡P_{\max} and the infimum for Pmin⁡P_{\min}. The two differ whenever delaying enables an action: a valuation at which nothing is enabled has P0=0P^0=0 but may have P∗>0P^*>0.

Definition 8 (Soundness invariant). VzV_z is sound if for every cell (ζi,[lbi,ubi])∈Vz(\zeta_i,[lb_i,ub_i])\in V_z and every v∈ζiv\in\zeta_i, lbi≤P0(z,v)≤ubilb_i\le P^0(z,v)\le ub_i. The time-closed value function V‾z\overline{V}_z obtained by the closure of Section 5.1 is sound if the same holds with P∗P^* in place of P0P^0.

The invariant is cell-wise and says nothing about valuations in no cell: the merge resolves overlapping cells without guaranteeing that their union covers ζ\zeta, so coverage matters only at the root, whose origin cell must exist for the reported answer to mean anything. Cells below the root bound P0P^0, not P∗P^*; delay before an action enters through pre⁡T\operatorname{pre}_{T} on the successor side of each backup (Lemma 1) and, for the root, through the closure.

Lemma 1 (Preimage). Let cc select cell (ζi,⋅)(\zeta_i,\cdot) from each successor ziz_i. Then pre⁡(z,a,ζ(c))\operatorname{pre}(z,a,\zeta(c)) is the set of v∈ζv\in\zeta at which aa is enabled and from which executing aa immediately can produce, for every outcome ii, an arrival valuation wiw_i that can elapse time into ζi\zeta_i.

What must be common is the source valuation at which aa is taken, not the behavior after it: nature does not reveal the outcome in advance, so a single vv must serve every outcome. The post-jump trajectories may differ, and Definition 6 allows that, applying pre⁡T\operatorname{pre}_{T} per outcome inside the conjunction. Each successor zone is closed under post-jump elapse, so pre⁡T\operatorname{pre}_{T} carries a successor cell back to that outcome’s jump instant; pre⁡J\operatorname{pre}_{J} then inverts that outcome’s resets, and the results are intersected in the source frame, where they constrain the one valuation at which aa occurs.

Theorem 1 (Soundness). Every VzV_z and VθV_\theta SYMAR produces is sound in the sense of Definition 8. In particular, if the origin-containing root cell is [lb,ub][lb,ub] then lb≤pPopt(F)≤ublb\le p_P^{\mathrm{opt}}(F)\le ub.

Sketch. Induction over the backup sequence, for P0P^0 below the root. Initialization. A state with location in FF has P0=1P^0=1 and a valuation at which no action is enabled has P0=0P^0=0, so [1,1][1,1] and [0,0][0,0] are exact and direction-independent (these cells say nothing about P∗P^* at such a valuation, which time may yet carry into a guard); otherwise the seed uses the side of hh that the query optimizes, which bounds P0P^0 because it bounds P∗P^* in the direction where P0P^0 lies inside it (§ 5.2), and the other side is 0 for Pmax⁡P_{\max} or the same upper cap for Pmin⁡P_{\min}; [0,1][0,1] absent a heuristic. Transition backup. Fix feasible cc and v∈pre⁡(z,a,ζ(c))v \in\operatorname{pre}(z,a,\zeta(c)). By Lemma 1, taking aa at vv gives each outcome ii an arrival wiw_i that can elapse into ζi\zeta_i at some wi′≥wiw_i' \ge w_i. A policy may do exactly this, so P∗(wi)≥P0(wi′)≥lbiP^*(w_i) \ge P^0(w_i') \ge lb_i for Pmax⁡P_{\max} (dually ≤ubi\le ub_i for Pmin⁡P_{\min}). Define the value through cell ζi\zeta_i as P0(wi′)P^0(w_i') bracketed by [lbi,ubi][lb_i,ub_i]; since prob⁡(l,a,i)≥0\operatorname{prob}(l,a,i) \ge0 and sums to one, monotonicity of expectation gives ∑iprob⁡(l,a,i)lbi≤Pc(v)≤∑iprob⁡(l,a,i)ubi\sum_i \operatorname{prob}(l,a,i)lb_i \le P_c(v) \le\sum_i \operatorname{prob}(l,a,i)ub_i for the value Pc(v)P_c(v) of taking aa at vv and then delaying into the cells selected by cc. This is the interval assigned. The optimum over delays is then the optimum over cc: each outcome elapses independently, so the cross product C(θ)C(\theta) ranges over every choice of landing cell, and Pθ0(v)=opt⁡cPc(v)P^0_\theta(v) = \operatorname{opt}_c P_c(v) over the combinations cc with v∈pre⁡(z,a,ζ(c))v \in\operatorname{pre}(z,a,\zeta(c)). Where preimages overlap, M retains one whole candidate rather than combining bounds: for Pmax⁡P_{\max} it keeps the candidate jj of greatest ubub, breaking ties on lblb. This is sound. Each candidate brackets its own value, lbi≤Pi≤ubilb_i \le P_i \le ub_i, so max⁡iPi≤max⁡iubi=ubj\max_i P_i \le\max_i ub_i = ub_j; and lbj≤Pj≤max⁡iPilb_j \le P_j \le\max_i P_i, so [lbj,ubj][lb_j,ub_j] contains max⁡iPi\max_i P_i. The upper bound needs every landing cell to be a candidate, so it requires that the successor cells cover every valuation at which some action is enabled; the remainder carries [0,0][0,0]. For Pmin⁡P_{\min} the dual argument applies to the candidate of least lblb. State backup. The same argument applies to the extremum over applicable transitions, the Bellman choice among actions enabled at vv; it bounds P0P^0. Root closure. The closure rewinds each root cell through time within ζ\zeta, best cell first, so a valuation v′v' that can elapse to vv inherits the cell’s bound. For Pmax⁡P_{\max} the lower bound is valid because P∗(v′)≥P0(v)P^*(v') \ge P^0(v). The upper bound is valid because the cells are processed in descending ubub: v′v' is claimed by the highest-ubub cell that rewinds onto it, which bounds sup⁡dP0(v′+d)=P∗(v′)\sup_d P^0(v' + d) = P^*(v'). Partial refinement. The retained c∗c^* carries the interval full backup assigns it. The retained c†c^\dagger carries the interval full backup assigns it, except that where a dropped combination overlaps c†c^\dagger outside c∗c^* the cell takes the weaker of the two bounds on that region (the larger ubub for Pmax⁡P_{\max}), since the dropped combination’s candidate would otherwise have won there under M. The hull is at least as loose as every combination it summarizes, so it cannot exclude P0P^0; its lower bound is 0 because it may cover valuations no combination realizes. Promotion to full enumeration only narrows it. Soundness is independent of convergence: it holds at every iteration, so the bounds may be reported whether or not the tolerance was met.

Convergence

Soundness does not imply the bounds meet. On a finite acyclic solution graph that is fully expanded and whose load-bearing deferred backups have all been promoted, they do, by induction on distance from the exact target and dead-end nodes. Both provisos matter: an unexpanded leaf still carries its heuristic interval and an unpromoted hull a placeholder lower bound. Cycles are the further difficulty, since a node on a cycle can hold a loose bound that backup never tightens, its value depending on its own previous value. The closing phase of Section 5.1 attacks this in the two ways described there, neither guaranteed to close every gap. SYMAR therefore treats convergence as something to check rather than assume: it accepts an answer only when the origin cell’s gap is within tolerance, and if relaxation stalls it reports the sound interval it has instead of claiming a converged value. Section 8 shows the bounds do close, to tolerance, on every benchmark. A general guarantee is future work; the missing ingredient is a treatment of cycles a policy can stay inside forever, and it must operate on (node, cell) pairs rather than nodes, since a symbolic state may cycle for some clock valuations and escape for others.

Related Work

Kwiatkowska et al. [11] established the foundation for PTA verification, formulating reachability as a stochastic game and obtaining two-sided bounds by abstraction refinement. SYMAR is a direct descendant: we retain the central idea that sound bounds come from refining an abstraction until the property-relevant zone distinctions are exposed, and change only how refinement is represented and scheduled, as § 3 describes. Because their method remains the best available source of admissible bounds, SYMAR uses it as its heuristic rather than discarding it. PTA model checking otherwise divides into backward reachability [17] and forward search [15]; SYMAR is a forward method that avoids the blowup usually afflicting them by refining symbolically rather than enumerating. We previously developed an AO∗AO^* MDP solver PRISM extension [4], and Hansen and Zilberstein’s LAO∗LAO^* [5] handles the cycles plain AO∗AO^* cannot; the closing phase of § 5.1 plays that role here.

Symbolic value iteration [7, 26] represents MDP value functions as algebraic decision diagrams. Like SYMAR these avoid enumerating states, but their basis is a fixed propositional one and cannot express the continuous zone partitions timed transitions induce, whereas SYMAR’s partition is built on demand from preimage computation. Point-based POMDP methods [25, 24, 10] are closer still: HSVI in particular tightens two-sided bounds by heuristically guided forward search, and its belief simplex plays the role our clock zone does. The difference is the representation’s shape: α\alpha-vectors are globally linear and their hull convex, whereas SYMAR’s zone partition is piecewise-constant and non-convex, arising from the geometry of clock resets and guards. Statistical model checking [6, 2] samples instead of enumerating, which suits finding counterexamples to a bound but not proving that no property-violating policy exists.

Experiments and Results

We implemented SYMAR within PRISM [12] and compare it with the SG method, the state-of-the-art baseline, on the PRISM benchmark PTAs. SYMAR runs with the games heuristic, helpful actions, and best-only backup all enabled (§ 5). Table 1 compares the two methods on both Pmax⁡P_{\max} and Pmin⁡P_{\min} instances; PRISM’s backward reachability engine does not implement Pmin⁡P_{\min}, so we report it in the text rather than the table.

PTA Instances

We used the PTA models distributed with PRISM1: the non-repudiation security protocol with an honest principal (Pmin⁡P_{\min}) and with a malicious one (Pmax⁡P_{\max}); IEEE 1394 FireWire leader election in both its abstract and implementation models (Pmin⁡P_{\min}); the CSMA/CD protocol in its abstract (Pmin⁡P_{\min}) and full (Pmax⁡P_{\max}) models; and the Zeroconf address assignment protocol (Pmax⁡P_{\max}). Except for csma/full, parameterized by its collision bound KK, each is queried under deadlines at a range of constants TT; the deadline queries are where the methods differ most. On the small formats09 example of Figure 1 all three methods are similar, and we omit it.

Experimental Setup

All experiments ran on an Apple M4 Max, in an amd64 Linux container (Alpine Linux 3.24) allotted 10 CPUs and 96 GB of memory. SYMAR and the SG method are both implemented in PRISM 4.8.1 and ran on OpenJDK 21.0.12 with a 2 GB maximum heap. Each instance was run three times and we report the mean of the time PRISM reports as “model checking completed”, which covers constructing the PTA and the check, including for SYMAR the heuristic solve, but not JVM startup or parsing; a run stopped at the 1200 s limit or by heap exhaustion was not repeated and appears as a dash in Table 1. Games used each benchmark’s distributed refinement options (refine=all).

Instance / PropertyGamesSYMARP(prop)P(\mathrm{prop})
initfinalrefsgensoliters
repudiation/honest (Pmin⁡P_{\min})
deadline T=40T = 40171471190.318860.250.61258
deadline T=400T = 40016113161119925.708860.50≈1.0\approx1.0
deadline T=524T = 52421075322124255.358860.51≈1.0\approx1.0
deadline T=526T = 5262113211300.42seed0.50≈1.0\approx1.0
firewire/abst (Pmin⁡P_{\min}, delay=360)
deadline T=10000T = 100005251020190.552319120.330.97473
deadline T=20000T = 2000018759070403.742319120.440.99963
deadline T=33000T = 330004850436784445.622319120.64≈1.0\approx1.0
deadline T=34000T = 340005141600111.132319120.69≈1.0\approx1.0
firewire/impl (Pmin⁡P_{\min}, delay=360)
deadline T=5000T = 500038474463171.373733200.790.78125
deadline T=10000T = 1000012168244495618.743733201.460.97473
deadline T=15000T = 15000261718638073234.703733202.430.99719
csma/abst (Pmin⁡P_{\min}, bmax=1, K=4K=4)
deadline T=1000T = 1000805988059802.32unreachable2.630.0
deadline T=2000T = 20003537153598111631.0832282312.180.40537
deadline T=2500T = 250058251869590617870.7332282318.810.94908
deadline T=3000T = 3000——32282329.650.99642
repudiation/malicious (Pmax⁡P_{\max})
deadline T=5T = 51660170020.34261080.380.1
deadline T=10T = 1056416589151.364701972180.950.10544
deadline T=40T = 40159272172687653.078806489743916.490.10566
zeroconf (Pmax⁡P_{\max})
deadline T=200T = 200811858160.314073993400.730.00122
deadline T=400T = 40032646776312.033234317928801.670.00130
deadline T=2000T = 2000660116601102.61seed2.900.00130
csma/full (Pmax⁡P_{\max}, bmax=2, COL=4)
collisions K=2K = 263856487100.883643252921.190.14355
collisions K=4K = 43471534849102.076445974442.270.07690
collisions K=8K = 88181398182731024.6164459744426.620.07690

Table 1. Runtime and search-space size, faster time in bold. For games: initial and final STPG states, refinement rounds, and seconds. For SYMAR: nodes generated, final solution-graph size, AO* iterations, and seconds. Pmin⁡P_{\min} families above the double rule, Pmax⁡P_{\max} below. A dash marks a method that exceeded the 1200 s limit or its 2 GB heap. “seed” marks instances whose unrefined heuristic already met the acceptance width, so AO* did not search; “unreach” those it settled by proving every upper bound zero.

Results

Each method states its stopping condition differently: games refines until the initial-state gap is below its refinement parameter, BR runs value iteration to the same absolute criterion, and SYMAR accepts an origin cell whose gap is at most 2ε2\varepsilon. We set ε=5×10−7\varepsilon= 5 \times10^{-7} for SYMAR (window 10−610^{-6}) and the refinement parameter to 10−610^{-6} for games; results agree to within 10−610^{-6} on every instance both finished (largest difference 5.4×10−75.4 \times10^{-7}), including BR on the Pmax⁡P_{\max} instances, an independent method rather than a refinement of the same abstraction.

Runtime. On the Pmin⁡P_{\min} families SYMAR is faster by one to two orders of magnitude at intermediate deadlines (108×108\times on repudiation/honest at T=524T = 524, 97×97\times on firewire/impl at T=15000T = 15000), and on csma/abst by 2.6×2.6\times at T=2000T = 2000 and 46×46\times at T=2500T = 2500; at T=3000T = 3000 it returns in 29.7 s where games exhausts the 1200 s limit. Games leads only where refinement is cheap (the bold games entries of Table 1), never by more than about 2.0 s, and SYMAR is at most 35% slower on all of them but zeroconf at T=200T = 200 (0.31 s against 0.73 s).

The two degrade differently. Games’ cost tracks refinement depth, which is non-monotone in TT: 55.4 s at T=524T = 524 on repudiation/honest against 0.42 s at T=526T = 526, as the refinement count falls from 242 to 0. Its state count grows with the deadline, whereas SYMAR’s search graph does not (37 generated nodes and 20 iterations on every firewire/impl instance, 8 and 6 on repudiation/honest, 23 and 12 on firewire/abst), because SYMAR expands only along the best partial solution. The rows SYMAR loses are not lost in the search, which is always negligible (csma/full K=8K = 8: 0.53 s of 26.6 s): the cost is solving the unrefined abstraction over the entire reachable symbolic state space (818,139 states there), so SYMAR cannot beat games by more than games spends on refinement beyond that solve. Wins track refinement rounds, and csma/full, needing 10 rounds at every size, admits none.

PRISM’s backward reachability engine (only the Pmax⁡P_{\max} instances) is fastest on csma/full and on repudiation/malicious at T=10T = 10, but degrades with the state space it enumerates: on zeroconf at T=400T = 400 it needs 102 value-iteration rounds over a 3165-state backward graph, taking 17.6 s against SYMAR’s 1.7 s.

Conclusion

We have presented SYMAR, which adapts the abstraction refinement of Kwiatkowska et al. [11] along two axes: refinement is symbolic, the partition the SG method materializes as split states appearing instead in a zone-valued probability function V:Zones→[0,1]2V : \mathrm{Zones} \to[0,1]^2 updated in place, and demand-driven, directed by forward AO∗AO^* search with bounds and helpful actions from the unrefined SG abstraction and partial refinement bounding the cross product. The stored abstraction and partial refinement bounding the cross product. The stored intervals are sound at every iteration independently of convergence (Theorem 1), so a run stopped early still bounds the answer.

The method pays off where refinement is expensive and the property-relevant fragment is small: SYMAR is up to 108×108\times faster than the SG method, solves a csma instance on which that method exhausts the time limit, and holds its search graph constant as the deadline grows where the SG abstraction expands with it. Where refinement is cheap the two are within about two seconds of each other, because SYMAR’s cost is dominated by the heuristic solve (98% of the total on the largest csma/full instance). Lowering that floor remains open, as does convergence, which we certify only a posteriori.

AI Usage. This paper’s prose was drafted with the assistance of a large language model (Claude, Anthropic) under author direction; the authors specified all content and claims and revised all generated text. The same assistant scripted the benchmark runs and instrumented the implementation for Table 1. The authors reviewed the benchmark scripts and the implementation. No results or citations were model-generated, and the algorithm, correctness argument, and implementation are the authors’ own.

Acknowledgements This material is based upon work supported by the Defense Advanced Research Projects Agency under Contract No. HR00112490439. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency.

References

  1. [1]Mustafa Adam, Kangfeng Ye, David A. Anisi, Ana Cavalcanti, Jim Woodcock & Robert Morris (2023): Probabilistic Modelling and Safety Assurance of an Agriculture Robot Providing Light-Treatment. In: 2023 IEEE 19th International Conference on Automation Science and Engineering (CASE), IEEE, pp. 1–7, doi:10.1109/CASE56687.2023.10260395.DOI
  2. [2]Peter Bulychev, Alexandre David, Kim Gulstrand Larsen, Marius Mikučionis, Danny Bøgsted Poulsen, Axel Legay & Zheng Wang (2012): UPPAAL-SMC: Statistical Model Checking for Priced Timed Automata, doi:10.4204/EPTCS.85.1. Available at https://arxiv.org/abs/1207.1272v1.
  3. [3]Ruben Giaquinta, Ruth Hoffmann, Murray Ireland, Alice Miller & Gethin Norman (2018): Strategy Synthesis for Autonomous Agents Using PRISM. In: Proceedings of the 10th NASA Formal Methods Symposium (NFM 2018), Lecture Notes in Computer Science 10811, Springer, pp. 220–236, doi:10.1007/978-3-319-77935-5_16.DOI
  4. [4]Robert P. Goldman, David J. Musliner & Michael W. Boldt (2015): Heuristic Search for Bounded Model Checking of Probabilistic Automata. In: Int’l Workshop on Design and Implementation of Formal Tools and Systems (DIFTS), Austin, TX. Available at http://www.musliner.com/david/papers/difts15-heuristic.pdf.
  5. [5]Eric A. Hansen & Shlomo Zilberstein (2001): LAO: A heuristic search algorithm that finds solutions with loops. Artificial Intelligence 129(1), pp. 35–62, doi:10.1016/S0004-3702(01)00106-0. Available at https://www.sciencedirect.com/science/article/pii/S0004370201001060.DOI
  6. [6]David Henriques, João G. Martins, Paolo Zuliani, André Platzer & Edmund M. Clarke (2012): Statistical Model Checking for Markov Decision Processes. In: 2012 Ninth International Conference on Quantitative Evaluation of Systems, pp. 84–93, doi:10.1109/QEST.2012.19.DOI
  7. [7]Jesse Hoey, Robert St-Aubin, Alan Hu & Craig Boutilier (1999): SPUDD: Stochastic Planning Using Decision Diagrams. In: Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Morgan Kaufmann, pp. 279–288, doi:10.48550/arXiv.1301.6704. Available at https://arxiv.org/abs/1301.6704.
  8. [8]Jörg Hoffmann & Bernhard Nebel (2001): The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14, pp. 253–302, doi:10.1613/jair.855.DOI
  9. [9]Ruth Hoffmann, Murray Ireland, Alice Miller, Gethin Norman & Sandor Veres (2016): Autonomous Agent Behaviour Modelled in PRISM — A Case Study. In: Proceedings of the 23rd International Symposium on Model Checking Software (SPIN 2016), Lecture Notes in Computer Science 9641, Springer, pp. 104–110, doi:10.1007/978-3-319-32582-8_7.DOI
  10. [10]Hanna Kurniawati, David Hsu & Wee Sun Lee (2008): SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces. In: Proceedings of Robotics: Science and Systems (RSS 2008), doi:10.15607/RSS.2008.IV.009.DOI
  11. [11]M. Kwiatkowska, G. Norman & D. Parker (2009): Stochastic Games for Verification of Probabilistic Timed Automata. In J. Ouaknine & F. Vaandrager, editors: Proc. 7th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS’09), LNCS 5813, Springer, pp. 212–227, doi:10.1007/978-3-642-04368-0_17.DOI
  12. [12]Marta Kwiatkowska, Gethin Norman & David Parker (2011): PRISM 4.0: Verification of Probabilistic Real-Time Systems. In: Proceedings of the 23rd International Conference on Computer Aided Verification (CAV 2011), Lecture Notes in Computer Science 6806, Springer, pp. 585–591, doi:10.1007/978-3-642-22110-1_47.DOI
  13. [13]Marta Kwiatkowska, Gethin Norman & David Parker (2025): Probabilistic Model Checking: Applications and Trends. In: Principles of Formal Quantitative Analysis, Lecture Notes in Computer Science 15760, Springer, pp. 158–173, doi:10.1007/978-3-031-97439-7_7.DOI
  14. [14]Marta Kwiatkowska, Gethin Norman, David Parker & Jeremy Sproston (2006): Performance Analysis of Probabilistic Timed Automata Using Digital Clocks. Formal Methods in System Design 29(1), pp. 33–78, doi:10.1007/s10703-006-0005-2.DOI
  15. [15]Marta Kwiatkowska, Gethin Norman, Roberto Segala & Jeremy Sproston (2002): Automatic verification of real-time systems with discrete probability distributions. Theoretical Computer Science 282(1), pp. 101–150, doi:10.1016/S0304-3975(01)00046-9.DOI
  16. [16]Marta Kwiatkowska, Gethin Norman & Jeremy Sproston (2002): Probabilistic Model Checking of the IEEE 802.11 Wireless Local Area Network Protocol. In: Process Algebra and Probabilistic Methods, Lecture Notes in Computer Science 2399, Springer, pp. 169–187, doi:10.1007/3-540-45605-8_11.DOI
  17. [17]Marta Kwiatkowska, Gethin Norman, Jeremy Sproston & Fuzhi Wang (2007): Symbolic model checking for probabilistic timed automata. Information and Computation 205(7), pp. 1027–1077, doi:10.1016/j.ic.2007.01.004.DOI
  18. [18]Ruggero Lanotte, Andrea Maggiolo-Schettini & Angelo Troina (2005): Automatic Analysis of a Non-Repudiation Protocol. In: Proceedings of the Second Workshop on Quantitative Aspects of Programming Languages (QAPL 2004), Electronic Notes in Theoretical Computer Science 112, Elsevier, pp. 113–129, doi:10.1016/j.entcs.2004.01.020.
  19. [19]Alberto Martelli & Ugo Montanari (1978): Optimizing Decision Trees Through Heuristically Guided Search. Communications of the ACM 21(12), pp. 1025–1039, doi:10.1145/359657.359664.DOI
  20. [20]Yongan Mu, Wei Liu, Tao Lu, Juan Li, Sheng Gao & Zihao Wang (2023): Runtime Verification of Self-Adaptive Multi-Agent System Using Probabilistic Timed Automata. Journal of Intelligent & Fuzzy Systems 45(6), pp. 10305–10322, doi:10.3233/JIFS-232397.DOI
  21. [21]Yasunari Mutsuda, Tsuyoshi Kato & Shigeru Yamane (2005): Specification and Verification Techniques of Embedded Systems Using Probabilistic Linear Hybrid Automata. In: Embedded Software and Systems (ICESS 2005), Lecture Notes in Computer Science 3820, Springer, pp. 328–339, doi:10.1007/11599555_34.DOI
  22. [22]Nils J. Nilsson (1980): Principles of Artificial Intelligence. Tioga Publishing Company, Palo Alto, CA, doi:10.5555/30425.
  23. [23]Olga Siedlecka-Lamch (2021): Probabilistic and Timed Analysis of Security Protocols. In: 13th International Conference on Computational Intelligence in Security for Information Systems (CISIS 2020), Advances in Intelligent Systems and Computing 1267, Springer, pp. 143–153, doi:10.1007/978-3-030-57805-3_14.
  24. [24]Trey Smith & Reid Simmons (2004): Heuristic Search Value Iteration for POMDPs. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI 2004), AUAI Press, pp. 520–527, doi:10.48550/arXiv.1207.4166. Available at https://arxiv.org/abs/1207.4166.
  25. [25]Matthijs T. J. Spaan & Nikos Vlassis (2005): Perseus: Randomized Point-based Value Iteration for POMDPs. Journal of Artificial Intelligence Research 24, pp. 195–220, doi:10.1613/jair.1659.DOI
  26. [26]Robert St-Aubin, Jesse Hoey & Craig Boutilier (2000): APRICODD: Approximate Policy Construction Using Decision Diagrams. In: Advances in Neural Information Processing Systems (NIPS 2000), MIT Press, pp. 1089–1095. Available at https://papers.nips.cc/paper/1840-apricodd-approximate-policy-construction-using-decision-diagrams.
  27. [27]Matt Webster, David Western, Dejanira Araiza-Illan, Clare Dixon, Kerstin Eder, Michael Fisher & Anthony G. Pipe (2020): A Corroborative Approach to Verification and Validation of Human–Robot Teams. International Journal of Robotics Research 39(1), pp. 73–99, doi:10.1177/0278364919883338.DOI

Paper details

vlnc:W_9k25vzx5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents