データ駆動型の因子化抽象化による確率システムの検証
Data-Driven Factored Abstractions of Stochastic Systems
ノイズを含む遷移観測から因子化区間マルコフ決定過程(fIMDP)を構築し、条件付き独立性を利用して推定確率の数を指数的に削減、ω正則仕様の満足確率の認証下界を有限サンプル保証付きで導出した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Mahdi Nazeri, Frederik Baymler Mathiesen, Sadegh Soudjani, Alessandro Abate
分類: eess.SY
原文アブストラクト
Formal verification and correct-by-design policy synthesis for stochastic dynamical systems face significant scalability challenges due to the curse of dimensionality. These challenges are exacerbated when the system dynamics are unknown and abstractions must be constructed from data. This paper introduces a data-driven framework for constructing factored interval Markov decision process (fIMDP) abstractions from noisy transition observations. Assuming conditional independence of successor coordinates and known coordinate-wise Lipschitz bounds on the dynamics, the framework estimates marginal transition probabilities rather than joint probabilities, resulting in an exponential reduction in the number of probability entries to be estimated and stored. We establish finite-sample confidence guarantees that the abstraction captures the concrete transition probabilities uniformly over each abstract region, enabling certified lower bounds on satisfaction probabilities for $ω$-regular specifications. Experiments on benchmark systems, including pendulum swing-up, unicycle control, and a four-dimensional planar robot model, demonstrate improvements in certified satisfaction probability lower bounds of up to 25 percentage points compared with a state-of-the-art flat IMDP abstraction method. Our framework required up to 23x less memory and was consistently faster in constructing the abstraction.
