Symbolic Control for Stochastic Systems via Finite Parity Games

arXiv:2101.00834 · eess.SY, cs.LO, cs.SY · Submitted 2021-01-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "Symbolic Control for Stochastic Systems via Finite Parity Games".

Dev: Here's the gist of the paper. Symbolic Control for Stochastic Systems via Finite Parity Games considers computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, nonlinear systems evolving in discrete time The problem reduces to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space The heart of the approach is a technique to symbolically compute the underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 21/2-player parity game Problem Decomposition and Approach The paper addresses finding a lower bound on the maximal satisfaction probability by decomposing the problem into two steps.

Rosa: The first step involves computing an under-approximation of the qualitative winning region, which is achieved by symbolically computing this via a finite-state abstraction of the original system as a 21/2-player parity game using only the support of the probabilistic evolution.

Dev: The second step involves computing the maximal probability of reaching this qualitative winning region, which is solved by combining this with existing techniques for reachability policy synthesis in stochastic nonlinear systems.

Rosa: This abstraction-based algorithm provides a lower bound on the maximal satisfaction probability.

Title and authors: Rosa: Okay, moving into the details of who wrote this, we have Rosa and Dev talking about the paper "Symbolic Control for Stochastic Systems via Finite Parity Games." Rosa starts by asking about what that title actually means in practical terms.

Dev: I think it means they are using symbolic methods to control stochastic systems by framing the problem in a way that involves finite parity games, which is a bit of an abstract concept.

Rosa: Yeah, and for someone working on real-time loops, it’s about taking something continuous and stochastic—like modeling how fast the universe is expanding near us—and boiling it down to a discrete game structure to solve it.

Dev: And the authors are Rosa, Dev, Taro, and others at Max Planck Institute for Software Systems and Newcastle University. They bring expertise in both robotics and control engineering from different angles.

Rosa: Right, so we have someone who runs trials outside the lab asking whether this works outside the lab or for how long when things misbehave—and Dev who cares about real-time loops, latency, and failure modes.

Dev: And Taro brings that autonomy researcher perspective to push on what the system does when it misbehaves and how gracefully it recovers in those real-world scenarios.

Rosa: It sounds like a good team for this kind of paper because they cover the whole spectrum from lab testing to real-world failure modes.

Dev: And this paper, "Symbolic Control for Stochastic Systems via Finite Parity Games," tries to tie all that together with formal methods. It’s about using game theory concepts to tackle those continuous state spaces and nonlinear dynamics.

Rosa: So, the implication is that they are showing a way to use these kinds of abstract games not just for theoretical puzzles but for actual engineering problems in robotics and control.

Dev: That's right, it’s about finding a practical way to compute things like the maximal probability of satisfying an omega regular specification in systems that don't fit neatly into standard models.

Rosa: It seems the authors are trying to make formal verification tools more applicable to the messy reality of continuous, nonlinear systems we actually deal with every day.

The paper's summary: Dev: So, let’s talk about what they actually say in this paper called "Symbolic Control for Stochastic Systems via Finite Parity Games." They summarize it by saying the problem reduces to finding the maximal probability of satisfying a parity condition on a possibly hybrid state space.

Rosa: That’s the core reduction. They take this continuous, stochastic system and transform it into finding that maximal probability of satisfying some parity condition on a state space that might involve both continuous and discrete parts.

Dev: The authors explain how they achieve this by decomposing the problem into two parts: first, using graph-theoretic techniques to ignore the actual transition probabilities to find the set of states that ensures satisfaction almost surely.

Rosa: And for any state in that set, they can derive an optimal policy for almost sure satisfaction of the specification from there.

Dev: Then, in step two, they find an optimal policy to reach that almost sure winning region using linear programming or traditional dynamic programming approaches.

Taro: So so the overall flow is first find a set of states that are safe almost surely, and then figure out how to get to those states using a policy. That makes sense in terms of safety guarantees.

Rosa: Exactly. And they then combine these two policies to return an optimal policy for the overall synthesis problem, which is what they're trying to do with their symbolic approach.

Dev: The paper also notes that this two-step solution approach doesn't carry over to optimal policy synthesis for all omega regular specifications because they don't have characterizations of optimal policies for almost sure satisfaction in this case, such as whether randomization or memory is necessary.

Taro: So, the limitation is that we might find a policy that satisfies the condition, but we can't be sure if it’s the best one possible without knowing more about those things.

The paper's improvements: Rosa: Now let's talk about what they suggest they improved in this paper. They focus on how their method provides a lower bound on the maximal satisfaction probability by computing an under-approximation of the qualitative winning region in step one.

Dev: That initial step involves computing this under-approximation via a finite-state abstraction of the original system as a two-one-two player parity game using only the support of the probabilistic evolution.

Rosa: This abstraction is key because it lets them use symbolic game solving techniques analogous to ABCD techniques for non-stochastic systems while capturing intuitive differences through that random player.

Dev: They also show that their implementation in Mascot-SDS, when combined with FairSyn, solves these two-one-two player parity games more efficiently than existing algorithms on standard laptops.

Taro: So, the improvement here is not just theoretical; it's practical speed and memory usage for the actual computation.

Rosa: Right. The implementation in Mascot-SDS shows that this lower bound on the winning region they compute is precise when compared against an over-approximation of the qualitative winning region, which means their method gives a good estimate of the true maximal probability in some cases.

Dev: And thanks to FairSyn, they also outperformed a recently proposed tool by a large margin in terms of memory consumption and time on standard laptops.

Taro: So, you’re saying this is more than just a theoretical trick; it’s actually faster and uses less resources when we run it on real systems.

Rosa: It suggests that this symbolic approach is a way to get a guaranteed lower bound on satisfaction probability by first approximating almost sure winning regions and then solving the reachability problem.

Dev: That's the main contribution regarding how they structure the synthesis, providing that structured approach for those complex problems.

Conclusion: Rosa: Wrapping up our look at "Symbolic Control for Stochastic Systems via Finite Parity Games," we’re summarizing that this work provides a way to compute lower bounds on satisfaction probability by using finite-state abstractions as two-one-two player parity games.

Dev: They achieve this by decomposing the problem into finding an underapproximation of the qualitative winning region and then solving the reachability problem for reaching that region.

Taro: The implication is that we have a way to get a guaranteed lower bound on satisfaction probability, which is useful when you're dealing with continuous state spaces and stochastic dynamics.

Rosa: And they show this lower bound can be precise by comparing it against an over-approximation of the qualitative winning region.

Dev: Plus, their implementation in Mascot-SDS and FairSyn gives them a significant speed and memory advantage over existing tools for specific specifications.

Taro: So, overall, this paper gives us a solid tool for getting started on verification when you're dealing with continuous state spaces and stochastic dynamics.

Rupak Majumdar, Kaushik Mallika, Anne-Kathrin Schmucka, Sadegh Soudjani

Max Planck Institute for Software Systems · School of Computing, Newcastle University

eess.SY, cs.LO, cs.SY

Submitted: 2021-01-04

Updated: 2026-11-12

Journal ref: 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

DOI: 10.1016/j.nahs.2023.101430

Code: https://github.com/gtfactslab/StochasticSynthesis

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 98/100

The gist: Symbolic Control for Stochastic Systems via Finite Parity Games considers computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state…

Key concepts

Finite Parity Games
This is a mathematical framework used to model complex systems, particularly those involving probabilistic transitions. The core idea is to represent the interplay between a controller and system dynamics as a game played by multiple players, allowing symbolic methods to analyze qualitative outcomes rather than just exact probabilities.
Abstraction Mechanism
The continuous state space of the original system is simplified into a finite set of cells. This abstraction is used to create a 21/2-player parity game where the random transitions are modeled by an additional 'random player.' This allows for symbolic analysis using tools designed for games, even though the original system is continuous.
Symbolic Game Solving
This refers to a new, direct algorithm for solving these 21/2-player parity games. Instead of relying on complex reductions to larger 2-player games, this technique uses set transformers like Cpre(S) and Apre(S, T) to express the solution using a $\mu$-calculus expression directly.
Controller Refinement
This final step takes the winning strategy found in the simplified abstract game and translates it back into a concrete control policy for the original continuous-state system. It ensures that if the system is in an abstract state, the controller applies a specific input derived from the game's solution, guaranteeing inclusion in the original winning domain.

Terminology

Summary

Symbolic Control for Stochastic Systems via Finite Parity Games considers computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, nonlinear systems evolving in discrete time The problem reduces to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space The heart of the approach is a technique to symbolically compute the underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 21/2-player parity game

Problem Decomposition and Approach

The paper addresses finding a lower bound on the maximal satisfaction probability by decomposing the problem into two steps. The first step involves computing an under-approximation of the qualitative winning region, which is achieved by symbolically computing this via a finite-state abstraction of the original system as a 21/2-player parity game using only the support of the probabilistic evolution. p. 0

Where the paper says it

The heart of our approach is a technique to symbolically compute the underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2 1 /2-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities.

The second step involves computing the maximal probability of reaching this qualitative winning region, which is solved by combining this with existing techniques for reachability policy synthesis in stochastic nonlinear systems. p. 1
Where the paper says it

to solve 21/2-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.

This abstraction-based algorithm provides a lower bound on the maximal satisfaction probability. p. 1
Where the paper says it

to solve 21/2-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.

Abstraction Mechanism

The core insight is modeling the interplay between the controller and dynamics as a 21/2-player game by introducing an additional random player to model the stochastic nature of transitions, resulting in a so called 21/2-player game. This abstraction allows for utilizing the machinery of symbolic game solving analogous to ABCD techniques for non-stochastic systems while capturing intuitive differences through the use of a random player. p. 3

Where the paper says it

This provides a conceptually very appealing result of our paper. Using 21/2- player games as abstractions of CMPs allows to utilize the machinery of symbolic game solving, analogous to ABCD techniques for non-stochastic systems, while capturing the intuitive differences between the problem instances by the use of a random player in the abstract game.

The construction involves state-space abstraction, where the continuous state space is partitioned into a finite set of cells, and transition abstraction using over- and under-approximations of probabilistic transitions F and F. p. 3
Where the paper says it

, 2017; Tabuada, 2009; Nilsson et al. In ABCD, a nonlinear dynamical system is abstracted into a discrete two-player game over a finite discrete state space obtained by partitioning the continuous state space into a finite set of cells.

Symbolic Game Solving

The paper presents a symbolic algorithm for solving 21/2-player parity games which is direct and much faster than established algorithms that rely on reductions to usually much larger 2-player games. The algorithm uses set transformers like Cpre(S) and Apre(S, T) to express the fixpoint algorithm using a µ-calculus expression. p. 6

Where the paper says it

This allows us to provide a conceptually simpler and computationally superior symbolic algorithm approximately solving (I) via abstract 21/2-player games. In principle, one can alternatively obtain a similar 21/2-player game, like us, by first reducing a CMP to a BMDP using the method of Dutreix et al.

This symbolic approach is presented as a main contribution of the paper, providing a direct and simpler proof for the same algorithm. p. 2
Where the paper says it

A parity specification is a canonical representation for all ωregular properties (Emerson & Jutla, 1991; Thomas, 1995); thus, our approach provides a way to under-approximate any ω-regular specification. The main contribution of our paper is to show that the approximate solution to step (I) can be computed by a symbolic algorithm over a finite state abstraction of the underlying CMP that is using only the support of the probabilistic 3

Controller Refinement

The final step involves refining the almost sure Player 0 winning strategy from the abstract game to a control policy for the original CMP. This refinement is defined such that if a state is in an abstract state and the corresponding move is chosen, the control policy selects that input. p. 3

Where the paper says it

This requires a very powerful Player 1; in every instance of the play (corresponding to the system being in one particular abstract cell sb) and for any input u chosen by Player 0, Player 1 can adversarially choose both (a) the actual continuous state s within sb to which u is applied and (b) any continuous disturbance affecting the system at this state s. The key insight in our work is that the stochastic nature of the underlying CMP does not require a fully adversarial treatment of continuous disturbances by Player 1 in the abstract game to allow for controller refinement.

Theorem 4.7 states that this refinement ensures the abstract state is included in the winning domain of the original CMP with respect to parity condition Parity(Pb). p. 0
Where the paper says it

, 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 underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2 1 /2-player parity game.

Empirical Validation

The approach was implemented in Mascot-SDS and evaluated on a nonlinear model of a perturbed bistable switch, showing empirically that the lower bound on the winning region computed by this approach is precise when compared against an over-approximation of the qualitative winning region. The results demonstrate superior performance over existing tools in terms of speed and memory consumption for specific specifications. p. 1

Where the paper says it

In fact, in many cases the existing tool crashed after consuming too much memory on a standard laptop, whereas our tool consumed small amount of memory and produced results within reasonable amount of time. Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1.

Numerical Example

A numerical example involving a two-dimensional stochastic bistable switch with two different parity specifications was considered, where the algorithms were implemented on Mascot-SDS. The performance comparison shows that the approximation error reduces with finer discretization, and Mascot-SDS outperformed StochasticSynthesis in terms of speed and memory footprint for both specifications. The results highlight the superior capabilities of the symbolic solution approach. p. 6

Where the paper says it

On the other hand, our approach shows a clean separation between step (II), which requires knowing explicit transition probabilities but can be solved by existing techniques, and step (I), for which this knowledge is not needed. This allows us to provide a conceptually simpler and computationally superior symbolic algorithm approximately solving (I) via abstract 21/2-player games.

References

de Alfaro, L., & Henzinger, T. p. 3

Where the paper says it

We show, that the resulting fairness assumption on the behavior of Player 1 can be modeled by an additional random player (also called 1/2 player) resulting in a so called 21/2-player game (Condon, 1992; Chatterjee et al. , 2003; Chatterjee & Henzinger, 2012) as the abstraction.

p. 3
Where the paper says it

We show, that the resulting fairness assumption on the behavior of Player 1 can be modeled by an additional random player (also called 1/2 player) resulting in a so called 21/2-player game (Condon, 1992; Chatterjee et al. , 2003; Chatterjee & Henzinger, 2012) as the abstraction.

p. 3
Where the paper says it

We show, that the resulting fairness assumption on the behavior of Player 1 can be modeled by an additional random player (also called 1/2 player) resulting in a so called 21/2-player game (Condon, 1992; Chatterjee et al. , 2003; Chatterjee & Henzinger, 2012) as the abstraction.

A. (2000). Concurrent omega-regular games. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. p. 5
Where the paper says it

Further the existing approach for stochastic linear systems (Svoreˇnov´a et al. , 2017) only considers specifications in the GR(1) fragment of linear temporal logic, whereas we can handle any ω-regular specification.

No. 99CB36332) (pp. 141–154). IEEE

Althoff, M., & Krogh, B. H. (2013). Reachability analysis of nonlinear differential-algebraic systems. p. 1

Where the paper says it

to solve 21/2-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.

IEEE Transactions on Automatic Control, 59, 371–383

Baier, C., & Katoen, J. p. 2

Where the paper says it

cies for ω-regular specifications by decomposing the problem into two parts (Courcoubetis & Yannakakis, 1990; Bianco & de Alfaro, 1995; de Alfaro, 1998; Baier & Katoen, 2008). (I) Using graph-theoretic techniques that ignore the actual transition probabilities, one can find the set of states that ensures the satisfaction of the specification almost surely.

-P. (2008). Principles of Model Checking. p. 1
Where the paper says it

, 2021) that solves 21/2-player parity games more efficiently then existing algoritms. We evaluated our implementation on the nonlinear model of a perturbed bistable switch from the literature.

MIT Press

Banerjee, T., Majumdar, R. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

, Mallik, K. p. 0
Where the paper says it

org (Rupak Majumdar), kmallik@mpi-sws. org (Kaushik Mallik), akschmuck@mpi-sws.

p. 0
Where the paper says it

org (Rupak Majumdar), kmallik@mpi-sws. org (Kaushik Mallik), akschmuck@mpi-sws.

p. 0
Where the paper says it

org (Rupak Majumdar), kmallik@mpi-sws. org (Kaushik Mallik), akschmuck@mpi-sws.

p. 0
Where the paper says it

org (Rupak Majumdar), kmallik@mpi-sws. org (Kaushik Mallik), akschmuck@mpi-sws.

, Schmuck, A. p. 0
Where the paper says it

org (Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck), sadegh.

p. 0
Where the paper says it

org (Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck), sadegh.

p. 0
Where the paper says it

org (Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck), sadegh.

-K., & Soudjani, S. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

(2021). Fast symbolic algorithms for omega-regular games under strong transition fairness. p. 5
Where the paper says it

, 2017) only considers specifications in the GR(1) fragment of linear temporal logic, whereas we can handle any ω-regular specification. Another difference is that the linearity assumption enables the use of symbolic algorithms based on polyhedral manipulations, when the specification is given using polytopic predicates on the state space.

Technical Report Tech. Rep. MPI-SWS-2020-007r, Max Planck Institute

Banerjee, T., Majumdar, R., Mallik, K., Schmuck, A.-K., & Soudjani, S. (2022). A direct symbolic algorithm for solving stochastic rabin games. p. 5

Where the paper says it

(2020) can be seen as directly solving a B¨uchi game symbolically on a non-probabilistic abstraction, by implicitly reducing the 21/2-player games to two player games on graphs with extreme fairness assumptions (Hart et al. While it may be possible to present a similar “direct” symbolic algorithm for parity games, the details of handling fairness symbolically get difficult.

In TACAS ’22 (to appear)

Bianco, A., & de Alfaro, L. p. 2

Where the paper says it

cies for ω-regular specifications by decomposing the problem into two parts (Courcoubetis & Yannakakis, 1990; Bianco & de Alfaro, 1995; de Alfaro, 1998; Baier & Katoen, 2008). (I) Using graph-theoretic techniques that ignore the actual transition probabilities, one can find the set of states that ensures the satisfaction of the specification almost surely.

(1995). Model checking of probabilistic and nondeterministic systems. p. 1
Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

In P. S. Thiagarajan (Ed.), Foundations of Software Technology and Theoretical Computer Science (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

499–513). Berlin, Heidelberg: Springer Berlin Heidelberg

Chatterjee, K., & Henzinger, T. A. (2012). A survey of stochastic ω-regular games. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

J. Comput. Syst. Sci., 78, 394–413

Chatterjee, K., Jurdzinski, M., & Henzinger, T. A. (2003). Simple stochastic parity games. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt G¨odel Colloquium, KGC 2003, Vienna, Austria

Condon, A. (1992). The complexity of stochastic games. p. 4

Where the paper says it

To midigate this problem we utilize the recent symbolic algorithm for solving 21/2- player games by Banerjee et al. (2022) which has almost the same worst-case complexity as the usual algorithm for (non-stochastic) two player games.

Inf. Comput., 96, 203–224

Coogan, S., & Arcak, M. (2015). Efficient finite abstraction of mixed monotone systems. p. 5

Where the paper says it

Our exposition in this paper helps separate out the different combinatorial aspects: the representation of the abstraction and the solution of the game on the abstraction, leading to a clean proof of correctness. 21/2-player games have been used as abstractions of probabilistic systems, both in the finite case (Kwiatkowska et al.

In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

58–67). ACM

Courcoubetis, C., & Yannakakis, M. p. 2

Where the paper says it

cies for ω-regular specifications by decomposing the problem into two parts (Courcoubetis & Yannakakis, 1990; Bianco & de Alfaro, 1995; de Alfaro, 1998; Baier & Katoen, 2008). (I) Using graph-theoretic techniques that ignore the actual transition probabilities, one can find the set of states that ensures the satisfaction of the specification almost surely.

(1990). Markov decision processes and regular events. p. 1
Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

In Automata, Languages and Programming (pp. p. 2
Where the paper says it

Further, for any state in this almost sure winning region, an optimal policy for almost sure satisfaction of the specification can be derived. (II) One finds an optimal policy to reach the almost sure winning region using linear programming or traditional dynamic programming approaches.

336–349). Berlin, Heidelberg: Springer Berlin Heidelberg

de Alfaro, L. (1998). Formal Verification of Probabilistic Systems. p. 5

Where the paper says it

Our exposition in this paper helps separate out the different combinatorial aspects: the representation of the abstraction and the solution of the game on the abstraction, leading to a clean proof of correctness. 21/2-player games have been used as abstractions of probabilistic systems, both in the finite case (Kwiatkowska et al.

Ph.D. thesis Department of Computer Science, Stanford University

Dutreix, M., & Coogan, S. p. 1

Where the paper says it

While there is a steady progression towards more expressive models and properties (Svoreˇnov´a et al. , 2017; Haesaert & Soudjani, 2020; Dutreix & Coogan, 2020; Majumdar et al.

p. 1
Where the paper says it

While there is a steady progression towards more expressive models and properties (Svoreˇnov´a et al. , 2017; Haesaert & Soudjani, 2020; Dutreix & Coogan, 2020; Majumdar et al.

(2020). Specification-guided verification and abstraction refinement of mixed monotone stochastic systems. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

IEEE Transactions on Automatic Control, 66, 2975–2990

Dutreix, M., Huh, J., & Coogan, S. (2020). Abstraction-based synthesis for stochastic systems with omega-regular objectives. p. 1

Where the paper says it

to solve 21/2-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.

arXiv preprint,. p. 0
Where the paper says it

soudjani@ncl. uk (Sadegh Soudjani) Preprint submitted to Elsevier September 30, 2022 arXiv:2101.

ArXiv:2001. p. 0
Where the paper says it

soudjani@ncl. uk (Sadegh Soudjani) Preprint submitted to Elsevier September 30, 2022 arXiv:2101.

09236

Emerson, E. A., & Jutla, C. p. 2

Where the paper says it

, 2017; Haesaert & Soudjani, 2020) can be used in step (II) to compute the reachability probability with any given precision, this paper provides a new technique to under-approximate the set of states of a CMP that almost surely satisfies a parity specification in step (I) of the decomposition. A parity specification is a canonical representation for all ωregular properties (Emerson & Jutla, 1991; Thomas, 1995); thus, our approach provides a way to under-approximate any ω-regular specification.

S. (1991). Tree automata, Mu-calculus and determinacy. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science SFCS ’91 (pp. 368–377). USA: IEEE Computer Society

Girard, A., G¨oßler, G., & Mouelhi, S. (2016). Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models. p. 3

Where the paper says it

Using 21/2- player games as abstractions of CMPs allows to utilize the machinery of symbolic game solving, analogous to ABCD techniques for non-stochastic systems, while capturing the intuitive differences between the problem instances by the use of a random player in the abstract game. Most interestingly, the stochastic nature of the resulting abstract game eases the abstract synthesis problem compared 4

IEEE Trans. Autom. Control., 61, 1537–1549

Gradel, E., & Thomas, W. p. 2

Where the paper says it

, 2017; Haesaert & Soudjani, 2020) can be used in step (II) to compute the reachability probability with any given precision, this paper provides a new technique to under-approximate the set of states of a CMP that almost surely satisfies a parity specification in step (I) of the decomposition. A parity specification is a canonical representation for all ωregular properties (Emerson & Jutla, 1991; Thomas, 1995); thus, our approach provides a way to under-approximate any ω-regular specification.

(2002). Automata, logics, and infinite games: a guide to current research volume 2500. p. 1
Where the paper says it

Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty. In recent years, the problem of finding or approximating optimal policies in CMPs for specifications given in temporal logics or automata has received a lot of attention.

Springer Science & Business Media

Haesaert, S., Nilsson, P. p. 3

Where the paper says it

This abstraction-based policy synthesis technique is inspired by abstraction-based controller design (ABCD) for non-stochastic systems (Reissig et al. , 2017; Tabuada, 2009; Nilsson et al.

, & Soudjani, S. (2021). Formal multi-objective synthesis of continuous-state mdps. p. 4
Where the paper says it

In conclusion, we obtain a symbolic algorithm to compute an under-approximation of the almost sure winning region in a continuous-state CMP for all ω-regular specifications. Moreover, similar to the results for finite-state MDPs, this shows that the (approximate) solution to step (I) does not need to handle the actual transition probabilities.

In 2021 American Control Conference (ACC) (pp. p. 1
Where the paper says it

, 2020), where we combined the outlined abstraction step with our recent tool FairSyn (Banerjee et al. , 2021) that solves 21/2-player parity games more efficiently then existing algoritms.

3428–3433). IEEE

Haesaert, S., & Soudjani, S. (2020). Robust dynamic programming for temporal logic control of stochastic systems. p. 5

Where the paper says it

Further the existing approach for stochastic linear systems (Svoreˇnov´a et al. , 2017) only considers specifications in the GR(1) fragment of linear temporal logic, whereas we can handle any ω-regular specification.

IEEE Transactions on Automatic Control, 66, 2496–2511

Hart, S., Sharir, M., & Pnueli, A. (1983). Termination of probabilistic concurrent program. p. 0

Where the paper says it

The heart of our approach is a technique to symbolically compute the underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2 1 /2-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities.

ACM Trans. Program. Lang. Syst., 5, 356–380

Hern´andez-Lerma, O., & Lasserre, J. p. 9

Where the paper says it

The function ρ is also called state feedback controller in control theory. For a CMP S, any policy ρ ∈ Π together with an initial probability measure α : B(S) → [0, 1] on the states induces a unique probability measure on the canonical sample space of paths (Hern´andez-Lerma & Lasserre, 1996), denoted by P ρ α with the expectation E ρ α.

B. (1996). Discrete-time Markov control processes volume 30 of Applications of Mathematics. p. 1
Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

Springer

Kallenberg, O. (2002). Foundations of modern probability. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

Probability and its Applications. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

New York: Springer Verlag

Kemeny, J. G., Snell, J. L., & Knapp, A. W. (1976). Denumerable Markov chains. p. 1

Where the paper says it

In fact, in many cases the existing tool crashed after consuming too much memory on a standard laptop, whereas our tool consumed small amount of memory and produced results within reasonable amount of time. Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1.

with a chapter on Markov random fields, by David Griffeath. p. 1
Where the paper says it

In fact, in many cases the existing tool crashed after consuming too much memory on a standard laptop, whereas our tool consumed small amount of memory and produced results within reasonable amount of time. Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1.

Graduate Texts in Mathematics, (pp. 0348–60090)

Kwiatkowska, M., Norman, G., Parker, D., & Santos, G. (2020). PRISMgames 3.0: Stochastic game verification with concurrency, equilibria and time. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In Proc. 32nd International Conference on Computer Aided Verification (CAV’20) (pp. p. 4
Where the paper says it

A preliminary version of our paper appeared in ADHS ’21 (Majumdar et al. In this manuscript we have made substantial improvement over the conference version; the main additional contributions are as follows: 1.

475–487). Springer volume 12225 of LNCS

Lahijanian, M., Andersson, S. B., & Belta, C. (2015). Formal verification and synthesis for discrete-time stochastic systems. p. 1

Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

IEEE Transactions on Automatic Control, 60, 2031–2045

Lavaei, A., Soudjani, S. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

, Abate, A. p. 2
Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

p. 2
Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

, & Zamani, M. (2021). Automated verification and synthesis of stochastic hybrid systems: A survey. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

arXiv preprint arXiv:2101. p. 0
Where the paper says it

soudjani@ncl. uk (Sadegh Soudjani) Preprint submitted to Elsevier September 30, 2022 arXiv:2101.

07491

Lavaei, A., Soudjani, S., & Zamani, M. (2019). Compositional construction of infinite abstractions for networks of stochastic control systems. p. 3

Where the paper says it

This provides a conceptually very appealing result of our paper. Using 21/2- player games as abstractions of CMPs allows to utilize the machinery of symbolic game solving, analogous to ABCD techniques for non-stochastic systems, while capturing the intuitive differences between the problem instances by the use of a random player in the abstract game.

Automatica, 107, 125 – 137

Lesser, K., & Oishi, M. (2017). Approximate safety verification and control of partially observable stochastic hybrid systems. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

IEEE Transactions on Automatic Control, 62, 81–96

Long, D. E., Browne, A., Clarke, E. M., Jha, S., & Marrero, W. R. (1994). An improved algorithm for the evaluation of fixpoint expressions. p. 5

Where the paper says it

We have substantially improved the experimental evaluation (see Sec. 6) of our approach by considering benchmark examples proposed by other authors, and comparing the performance of our tool against the available tool from the literature.

In International Conference on Computer Aided Verification (pp. p. 4
Where the paper says it

A preliminary version of our paper appeared in ADHS ’21 (Majumdar et al. In this manuscript we have made substantial improvement over the conference version; the main additional contributions are as follows: 1.

338–350). Springer

Majumdar, R., Mallik, K., Schmuck, A.-K., & Soudjani, S. (2021). Symbolic qualitative control for stochastic systems via finite parity games. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

IFACPapersOnLine, 54, 127–132

Majumdar, R., Mallik, K., & Soudjani, S. (2020). Symbolic controller synthesis for B¨uchi specifications on stochastic systems. p. 1

Where the paper says it

In fact, in many cases the existing tool crashed after consuming too much memory on a standard laptop, whereas our tool consumed small amount of memory and produced results within reasonable amount of time. Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1.

In Proceedings of the 23rd International Conference on Hybrid Systems: Computation and Control (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

1–11)

Nilsson, P., Ozay, N., & Liu, J. (2017). Augmented finite transition systems as abstractions for control synthesis. p. 3

Where the paper says it

Using 21/2- player games as abstractions of CMPs allows to utilize the machinery of symbolic game solving, analogous to ABCD techniques for non-stochastic systems, while capturing the intuitive differences between the problem instances by the use of a random player in the abstract game. Most interestingly, the stochastic nature of the resulting abstract game eases the abstract synthesis problem compared 4

Discrete Event Dynamic Systems, 27, 301–340

Piterman, N., & Pnueli, A. (2006). Faster solutions of rabin and streett games. p. 6

Where the paper says it

(2020) for the purpose of controller synthesis. By using algorithms for finding controllers on BMDPs against deterministic Rabin automata, they provide an alternative approach for approximating the optimal controller against ω-regular specifications.

In 21st Annual IEEE Symposium on Logic in Computer Science (LICS’06) (pp. p. 5
Where the paper says it

Further the existing approach for stochastic linear systems (Svoreˇnov´a et al. , 2017) only considers specifications in the GR(1) fragment of linear temporal logic, whereas we can handle any ω-regular specification.

275–284). IEEE

Reissig, G., Weber, A., & Rungger, M. (2017). Feedback refinement relations for the synthesis of symbolic controllers. p. 6

Where the paper says it

(2020) for the purpose of controller synthesis. By using algorithms for finding controllers on BMDPs against deterministic Rabin automata, they provide an alternative approach for approximating the optimal controller against ω-regular specifications.

TAC, 62, 1781–1796

Soudjani, S., & Abate, A. p. 2

Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

p. 2
Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

p. 2
Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

p. 2
Where the paper says it

However, we show in this paper, that the same decomposition can be used to compute an under-approximation for the optimal policy instead: that is, the resulting policy gives a lower bound on the probability of satisfying a given ω-regular specification from every state. While existing techniques (Soudjani & Abate, 2013; Tkachev et al.

(2012). Higher-order approximations for verification of stochastic hybrid systems. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In Automated Technology for Verification and Analysis (pp. 416–434). Springer Verlag, Berlin Heidelberg volume 7561 of LNCS

Soudjani, S., & Abate, A. (2013). Adaptive and sequential gridding procedures for the abstraction and verification of stochastic processes. p. 5

Where the paper says it

Another difference is that the linearity assumption enables the use of symbolic algorithms based on polyhedral manipulations, when the specification is given using polytopic predicates on the state space. Instead, our abstractions are based on gridding the state space, as in ABCD for non-stochastic nonlinear systems.

SIAM Journal on Applied Dynamical Systems, 12, 921–956

Soudjani, S., Abate, A., & Majumdar, R. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

(2017). Dynamic Bayesian networks for formal verification of structured stochastic processes. p. 1
Where the paper says it

In fact, in many cases the existing tool crashed after consuming too much memory on a standard laptop, whereas our tool consumed small amount of memory and produced results within reasonable amount of time. Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1.

Acta Informatica, 54, 217–242

Svoreˇnov´a, M., Kˇret´ınsk‘y, J., Chmel´ık, M., Chatterjee, K. p. 3

Where the paper says it

Intuitively, disturbances need to be handled in a fair way: In the long run, all transitions with positive probability will eventually occur. We show, that the resulting fairness assumption on the behavior of Player 1 can be modeled by an additional random player (also called 1/2 player) resulting in a so called 21/2-player game (Condon, 1992; Chatterjee et al.

, Cern´a, I., & Belta, ˇ C. (2017). Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games. p. 5
Where the paper says it

Further the existing approach for stochastic linear systems (Svoreˇnov´a et al. , 2017) only considers specifications in the GR(1) fragment of linear temporal logic, whereas we can handle any ω-regular specification.

Nonlinear Analysis: Hybrid Systems, 23, 230–253

Tabuada, P. (2009). Verification and Control of Hybrid Systems: A Symbolic Approach. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

Springer

Tkachev, I., & Abate, A. (2012). Regularization of Bellman equations for infinite-horizon probabilistic properties. p. 2

Where the paper says it

A parity specification is a canonical representation for all ωregular properties (Emerson & Jutla, 1991; Thomas, 1995); thus, our approach provides a way to under-approximate any ω-regular specification. The main contribution of our paper is to show that the approximate solution to step (I) can be computed by a symbolic algorithm over a finite state abstraction of the underlying CMP that is using only the support of the probabilistic 3

In Proceedings of the 15th ACM international conference on Hybrid Systems: computation and control (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

227–236). Beijing, PRC

Tkachev, I., Mereacre, A., Katoen, J. p. 2

Where the paper says it

cies for ω-regular specifications by decomposing the problem into two parts (Courcoubetis & Yannakakis, 1990; Bianco & de Alfaro, 1995; de Alfaro, 1998; Baier & Katoen, 2008). (I) Using graph-theoretic techniques that ignore the actual transition probabilities, one can find the set of states that ensures the satisfaction of the specification almost surely.

-P., & Abate, A. (2017). Quantitative model-checking of controlled discrete-time Markov processes. p. 1
Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

Information and Computation, 253, 1 – 35

Vardi, M. Y. (1985). Automatic verification of probabilistic concurrent finite state programs. p. 0

Where the paper says it

The heart of our approach is a technique to symbolically compute the underapproximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2 1 /2-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities.

In 26th Annual Symposium on Foundations of Computer Science (pp. 327–338). IEEE

Vinod, A. P., & Oishi, M. M. K. (2018). Scalable underapproximative verification of stochastic LTI systems using convexity and compactness. p. 3

Where the paper says it

This provides a conceptually very appealing result of our paper. Using 21/2- player games as abstractions of CMPs allows to utilize the machinery of symbolic game solving, analogous to ABCD techniques for non-stochastic systems, while capturing the intuitive differences between the problem instances by the use of a random player in the abstract game.

In Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (Part of CPS Week) HSCC ’18 (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

1–10)

Weininger, M., Meggendorfer, T., & Kˇret´ınsk‘y, J. (2019). Satisfiability bounds for ω-regular properties in bounded-parameter markov decision processes. p. 1

Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

In 2019 IEEE 58th Conference on Decision and Control (CDC) (pp. p. 1
Where the paper says it

Keywords: Correct-by-design controller synthesis, controlled Markov processes, stochastic dynamical systems, ω-regular specifications 1. Introduction Controlled Markov processes (CMPs) over continuous state spaces and evolving in discrete time form a general model for temporal decision making under stochastic uncertainty.

2284–2291)

Zielonka, W. (2004). Perfect-information stochastic parity games. p. 0

Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

In International Conference on Foundations of Software Science and Computation Structures (pp. p. 0
Where the paper says it

Symbolic Control for Stochastic Systems via Finite Parity Games Rupak Majumdar a , Kaushik Mallika, ∗ , Anne-Kathrin Schmucka, ∗ , Sadegh Soudjani b aMax Planck Institute for Software Systems, Kaiserslautern, 67663 Germany bSchool of Computing, Newcastle University, NE4 5TG United Kingdom Abstract We consider the problem of computing the maximal probability of satisfying an ω-regular specification for stochastic, continuous-state, 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.

499–513).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Abstract symbolic control for stochastic systems via finite parity games allows AI systems to compute a lower bound on satisfaction probability by computing an under-approximation of the qualitative winning region, which is achieved through a finite-state abstraction of the system as a 2 1/2-player parity game.

  2. The improved system can solve Problem 2 (Approximate Maximal Winning Region) by finding a sub-optimal control policy and its approximation error bound, utilizing an abstraction-based controller design paradigm where the abstract game is modeled as a 21/2-player parity game.

  3. The system can compute the almost sure winning region for a continuous state space Markov control process by solving the symbolic algorithm for 21/2-player parity games, which provides a direct and faster method compared to existing algorithms that reduce the problem to larger 2-player games.

  4. The system can refine an abstract Player 0 winning strategy from the abstract 21/2-player game into a concrete control policy for the original continuous state Markov control process by mapping abstract states back to continuous states based on the refinement of Player 0's policy.

  5. The improved AI system can provide a guaranteed lower bound on satisfaction probability for an omega-regular specification by first approximating almost sure winning regions and then solving a reachability problem, as formalized in Theorem 3.2 and Problem 2.

Abstract

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.

Sources

Related papers