跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2101.00834 · v3

Symbolic Control for Stochastic Systems via Finite Parity Games

首次提交 2021-01-04 16:50
版本更新 2026-11-13 06:51
雷达观测 2026-11-17 04:58
arXiv ↗PDF ↗

摘要

We consider the problem of computing the maximal probability of satisfying an omega-regular specification for stochastic nonlinear systems evolving in discrete time. The problem reduces, after automata-theoretic constructions, to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space. While characterizing the exact satisfaction probability is open, we show that a lower bound on this probability can be obtained by (I) computing an under-approximation of the qualitative winning region, i.e., states from which the parity condition can be enforced almost surely, and (II) computing the maximal probability of reaching this qualitative winning region. The heart of our approach is a technique to symbolically compute the under-approximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2.5-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities. We prove that the winning set in the abstract 2.5-player game induces an under-approximation of the qualitative winning region in the original synthesis problem, along with a policy to solve it. By combining these contributions with (a) a symbolic fixpoint algorithm to solve 2.5-player games and (b) existing techniques for reachability policy synthesis in stochastic nonlinear systems, we get an abstraction-based algorithm for finding a lower bound on the maximal satisfaction probability. We have implemented the abstraction-based algorithm in Mascot-SDS (Majumdar et al., 2020), where we combined the outlined abstraction step with our recent tool FairSyn. We evaluated our implementation on the nonlinear model of a perturbed bistable switch from the literature. We outperform a recently proposed tool for solving this problem by a large margin.

期刊信息:Majumdar, R., Mallik, K., Schmuck, A.K. and Soudjani, S., 2024. Symbolic control for stochastic systems via finite parity games. Nonlinear Analysis: Hybrid Systems, 51, p.101430

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-13 06:51 · 最新观测版本

Symbolic Control for Stochastic Systems via Finite Parity Games

We consider the problem of computing the maximal probability of satisfying an omega-regular specification for stochastic nonlinear systems evolving in discrete time. The problem reduces, after automata-theoretic constructions, to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space. While characterizing the exact satisfaction probability is open, we show that a lower bound on this probability can be obtained by (I) computing an under-approximation of the qualitative winning region, i.e., states from which the parity condition can be enforced almost surely, and (II) computing the maximal probability of reaching this qualitative winning region. The heart of our approach is a technique to symbolically compute the under-approximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2.5-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities. We prove that the winning set in the abstract 2.5-player game induces an under-approximation of the qualitative winning region in the original synthesis problem, along with a policy to solve it. By combining these contributions with (a) a symbolic fixpoint algorithm to solve 2.5-player games and (b) existing techniques for reachability policy synthesis in stochastic nonlinear systems, we get an abstraction-based algorithm for finding a lower bound on the maximal satisfaction probability. We have implemented the abstraction-based algorithm in Mascot-SDS (Majumdar et al., 2020), where we combined the outlined abstraction step with our recent tool FairSyn. We evaluated our implementation on the nonlinear model of a perturbed bistable switch from the literature. We outperform a recently proposed tool for solving this problem by a large margin.

查看此版本解读 →查看此版本原文 ↗