arXiv:2611.22404v1 cs.AI

기호적 추상화 정제

Symbolic Abstraction Refinement

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)

제출 2026-11-18

한국어 초록

자율 시스템은 결과가 불확실하고 시간 제약이 있는 행동을 선택한다. 확률적 시간 오토마톤(PTA)은 이 상황을 모델링한다. PTA를 검증하면 제어기가 보장할 수 있는 최대 목표 도달 확률이나 최소 위험 상태 도달 확률을 알 수 있다. 검증은 일반적으로 이산 위치와 시계 값의 영역을 짝지은 기호 상태를 사용한다. 그러나 같은 시계 영역 안에서도 최적 행동이 달라지는 경우가 많아 검증이 어렵다. PRISM 검증기의 가장 강력한 PTA 방법은 각 영역이 균일해질 때까지 영역을 분할한다. 해당 영역으로 들어오는 전이를 다시 만들고 확률 게임의 상태 그래프에서 분할을 역방향으로 전파한다. 이 연쇄적인 그래프 재구성은 검증 속성과 무관한 영역까지 분할할 수 있다. 대신 가치 함수를 기호적으로 표현하는 SYMAR를 제시한다. 각 기호 상태는 시계 영역의 하위 영역을 확률 상·하한에 매핑하는 함수를 갖는다. 정제 과정에서 해당 함수에 하위 영역이 새로 생기며, 이미 만든 상태를 분할하거나 유입 전이를 재구성할 필요는 없다. PTA의 두 비결정성 원천인 행동 시점과 행동 선택은 하위 영역을 만드는 역상 계산에 암묵적으로 반영한다. 휴리스틱 순방향 탐색으로 정제량을 제한한다. 기존 방법을 정제 없이 한 번 실행해 얻은 경계와 선호 행동을 사용해, 초기 상태부터 유망한 행동을 따라 AND–OR 그래프를 확장한다. 이렇게 검증 속성과 관련된 부분에만 계산을 집중한다. 부분 정제 백업은 조합적으로 늘어날 수 있는 하위 영역 수를 줄이며, 저장된 모든 구간은 참확률을 포함함이 증명된다. PRISM PTA 벤치마크의 경합 상황에서 분산 합의, 리더 선출, 중앙 조정 없는 자체 구성 문제는 자율 시스템에도 나타난다. 여기서 SYMAR는 최대 108배 빨랐고, 기존 방법이 시간 제한을 넘긴 사례를 풀었다. 마감 시간 상수에도 훨씬 덜 민감했다. 한 사례에서는 마감 시간을 세 배로 늘려도 노드 37개의 탐색 그래프로 풀었으며, 기존 방법은 추상 상태 86,380개와 정제 73회가 필요했다.

원문 초록

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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2611.22404v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.