Symbolic Control for Stochastic Systems via Finite Parity Games
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. , 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.Where the paper says it
Where the paper says it
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 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. 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
3Where the paper says it
Where the paper says it
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 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. , 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
References
de Alfaro, L., & Henzinger, T. p. 3 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Althoff, M., & Krogh, B. H. (2013). Reachability analysis of nonlinear differential-algebraic systems. p. 1 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.Where the paper says it
Baier, C., & Katoen, J. p. 2 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. , 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.Where the paper says it
Where the paper says it
Banerjee, T., Majumdar, R. p. 0 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. 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. org (Rupak Majumdar), kmallik@mpi-sws. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Rupak Majumdar), kmallik@mpi-sws. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Rupak Majumdar), kmallik@mpi-sws. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Rupak Majumdar), kmallik@mpi-sws. org
(Kaushik Mallik), akschmuck@mpi-sws. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck),
sadegh. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck),
sadegh. org
(Kaushik Mallik), akschmuck@mpi-sws. org (Anne-Kathrin Schmuck),
sadegh. 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. 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. 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. 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. 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. 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) 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Banerjee, T., Majumdar, R., Mallik, K., Schmuck, A.-K., & Soudjani, S. (2022). A direct symbolic algorithm for solving stochastic rabin games. p. 5 (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.Where the paper says it
Bianco, A., & de Alfaro, L. p. 2 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Chatterjee, K., & Henzinger, T. A. (2012). A survey of stochastic ω-regular games. p. 0 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.Where the paper says it
Chatterjee, K., Jurdzinski, M., & Henzinger, T. A. (2003). Simple stochastic parity games. p. 0 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.Where the paper says it
Condon, A. (1992). The complexity of stochastic games. p. 4 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.Where the paper says it
Coogan, S., & Arcak, M. (2015). Efficient finite abstraction of mixed monotone systems. p. 5 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. 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.Where the paper says it
Where the paper says it
Courcoubetis, C., & Yannakakis, M. p. 2 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
de Alfaro, L. (1998). Formal Verification of Probabilistic Systems. p. 5 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.Where the paper says it
Dutreix, M., & Coogan, S. p. 1 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Dutreix, M., Huh, J., & Coogan, S. (2020). Abstraction-based synthesis for stochastic systems with omega-regular objectives. p. 1 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. soudjani@ncl. uk (Sadegh Soudjani)
Preprint submitted to Elsevier September 30, 2022
arXiv:2101. soudjani@ncl. uk (Sadegh Soudjani)
Preprint submitted to Elsevier September 30, 2022
arXiv:2101.Where the paper says it
Where the paper says it
Where the paper says it
Emerson, E. A., & Jutla, C. p. 2 , 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. 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.Where the paper says it
Where the paper says it
Girard, A., G¨oßler, G., & Mouelhi, S. (2016). Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models. p. 3 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
4Where the paper says it
Gradel, E., & Thomas, W. p. 2 , 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. 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.Where the paper says it
Where the paper says it
Haesaert, S., Nilsson, P. p. 3 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. 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. , 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.Where the paper says it
Where the paper says it
Where the paper says it
Haesaert, S., & Soudjani, S. (2020). Robust dynamic programming for temporal logic control of stochastic systems. p. 5 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.Where the paper says it
Hart, S., Sharir, M., & Pnueli, A. (1983). Termination of probabilistic concurrent program. p. 0 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.Where the paper says it
Hern´andez-Lerma, O., & Lasserre, J. p. 9 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
ρ
α. 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.Where the paper says it
Where the paper says it
Kallenberg, O. (2002). Foundations of modern probability. p. 0 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. 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.Where the paper says it
Where the paper says it
Kemeny, J. G., Snell, J. L., & Knapp, A. W. (1976). Denumerable Markov chains. p. 1 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 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.Where the paper says it
Where the paper says it
Kwiatkowska, M., Norman, G., Parker, D., & Santos, G. (2020). PRISMgames 3.0: Stochastic game verification with concurrency, equilibria and time. p. 0 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. 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.Where the paper says it
Where the paper says it
Lahijanian, M., Andersson, S. B., & Belta, C. (2015). Formal verification and synthesis for discrete-time stochastic systems. p. 1 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.Where the paper says it
Lavaei, A., Soudjani, S. p. 0 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. 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. 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. 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. 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. soudjani@ncl. uk (Sadegh Soudjani)
Preprint submitted to Elsevier September 30, 2022
arXiv:2101.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Lavaei, A., Soudjani, S., & Zamani, M. (2019). Compositional construction of infinite abstractions for networks of stochastic control systems. p. 3 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.Where the paper says it
Lesser, K., & Oishi, M. (2017). Approximate safety verification and control of partially observable stochastic hybrid systems. p. 0 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
Majumdar, R., Mallik, K., Schmuck, A.-K., & Soudjani, S. (2021). Symbolic qualitative control for stochastic systems via finite parity games. p. 0 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.Where the paper says it
Majumdar, R., Mallik, K., & Soudjani, S. (2020). Symbolic controller synthesis for B¨uchi specifications on stochastic systems. p. 1 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. 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.Where the paper says it
Where the paper says it
Nilsson, P., Ozay, N., & Liu, J. (2017). Augmented finite transition systems as abstractions for control synthesis. p. 3 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
4Where the paper says it
Piterman, N., & Pnueli, A. (2006). Faster solutions of rabin and streett games. p. 6 (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. 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.Where the paper says it
Where the paper says it
Reissig, G., Weber, A., & Rungger, M. (2017). Feedback refinement relations for the synthesis of symbolic controllers. p. 6 (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.Where the paper says it
Soudjani, S., & Abate, A. p. 2 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Soudjani, S., & Abate, A. (2013). Adaptive and sequential gridding procedures for the abstraction and verification of stochastic processes. p. 5 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.Where the paper says it
Soudjani, S., Abate, A., & Majumdar, R. p. 0 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 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.Where the paper says it
Where the paper says it
Svoreˇnov´a, M., Kˇret´ınsk‘y, J., Chmel´ık, M., Chatterjee, K. p. 3 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. 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.Where the paper says it
Where the paper says it
Tabuada, P. (2009). Verification and Control of Hybrid Systems: A Symbolic Approach. p. 0 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.Where the paper says it
Tkachev, I., & Abate, A. (2012). Regularization of Bellman equations for infinite-horizon probabilistic properties. p. 2 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 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.Where the paper says it
Where the paper says it
Tkachev, I., Mereacre, A., Katoen, J. p. 2 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. 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.Where the paper says it
Where the paper says it
Vardi, M. Y. (1985). Automatic verification of probabilistic concurrent finite state programs. p. 0 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.Where the paper says it
Vinod, A. P., & Oishi, M. M. K. (2018). Scalable underapproximative verification of stochastic LTI systems using convexity and compactness. p. 3 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. 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.Where the paper says it
Where the paper says it
Weininger, M., Meggendorfer, T., & Kˇret´ınsk‘y, J. (2019). Satisfiability bounds for ω-regular properties in bounded-parameter markov decision processes. p. 1 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. 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.Where the paper says it
Where the paper says it
Zielonka, W. (2004). Perfect-information stochastic parity games. p. 0 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. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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
- Abstraction-based Synthesis for Stochastic Systems with Omega-Regular Objectives
- Automated Verification and Synthesis of Stochastic Hybrid Systems: A Survey
Related papers
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction
- Passive Identification of Unequal Phase Grid Impedances by Phase-Domain Source Cancellation