Distributionally Robust Strategy Synthesis for Switched Stochastic Systems

Ibon Gracia, Dimitris Boskos, Luca Laurenti, Manuel Mazo Jr.

TL;DR

This paper introduces a new method for designing control strategies for complex systems (like robots or cyber-physical systems) that operate with noisy components and uncertain behavior. The key innovation is a framework that guarantees the system will achieve its goals with high probability, even when the exact nature of the noise is unknown, by considering a range of possible noise distributions.

What Problem Does This Paper Address?

Many real-world systems, such as robots or networked control systems, are inherently stochastic due to noise and disturbances. Furthermore, the precise statistical properties of this noise are often unknown or can change over time (distributional shifts). Designing controllers for these systems that can provide formal guarantees of safety and performance (e.g., reaching a target location while avoiding obstacles) is a significant challenge. Traditional methods often assume exact knowledge of noise distributions, which is unrealistic. This paper tackles the problem of synthesizing control strategies for switched stochastic systems that are robust to uncertainty in the noise distribution, specifically when the distribution is known to be within a certain "ambiguity set" defined by the Wasserstein distance from a nominal distribution.

Methods

The authors propose a two-step approach:

  1. Finite Abstraction: They first create a simplified model of the complex system, called a "robust Markov decision process" (robust MDP). This abstraction captures both the system's inherent randomness and the uncertainty in the noise distribution. This is achieved by discretizing the system's state space and then defining transition probabilities that account for the range of possible noise distributions.
  2. Robust Strategy Synthesis: Once the robust MDP is constructed, they develop algorithms to synthesize a control strategy that maximizes the probability of achieving a desired specification (like reach-avoidance) while being robust to all possible noise distributions within the ambiguity set. This synthesis process leverages techniques from optimal transport and stochastic programming, reducing the problem to solving a set of linear programs, which makes it computationally efficient. The resulting strategy for the abstract model is then refined into a switching strategy for the original system.

Datasets

Not discussed in the paper. The paper focuses on synthesizing strategies for given system dynamics and noise models, rather than learning from data. However, the framework is designed to handle ambiguity sets that can be constructed from data (e.g., using empirical distributions).

Key Insights and Ideas

  • Bridging the Gap: The paper effectively bridges the gap between formal verification/control and the practical reality of uncertain system dynamics, particularly concerning noise distributions.
  • Wasserstein Ambiguity Sets: Using Wasserstein distance to define ambiguity sets is a powerful way to capture distributional uncertainty, especially when dealing with data-driven models or potential distributional shifts.
  • Robust MDP Abstraction: The concept of abstracting the system into a robust MDP is crucial. It allows for formal reasoning and synthesis on a tractable model that still captures essential uncertainties.
  • Linear Programming for Efficiency: Reducing the complex synthesis problem to solving linear programs is a significant contribution, enabling efficient computation of robust strategies.
  • Unbounded-Time Guarantees: The framework extends to infinite-horizon specifications, providing guarantees for long-term system behavior.

Key Results

  • Framework for Distributionally-Uncertain Systems: The paper presents a formal framework for reasoning about and controlling switched stochastic systems with distributional uncertainty.
  • Robust MDP Abstraction: A procedure to construct a finite robust MDP abstraction for nonlinear switched stochastic systems with additive uncertain noise is provided.
  • Efficient Synthesis Algorithm: A robust strategy synthesis algorithm for robust MDPs with unbounded-time reachability specifications is developed, which is shown to be computationally efficient by reducing it to linear programs.
  • Experimental Validation: The framework was tested on various case studies, including linear and nonlinear systems, demonstrating its efficacy in synthesizing strategies that provide high satisfaction probabilities and formal guarantees. The results show significant speedups compared to using standard linear programming solvers and highlight the superiority of their approach over simpler IMDP abstractions. For instance, in Table 1, the "Dual" algorithm for synthesis is orders of magnitude faster than "Linprog" for similar problems.

Limitations and Future Work

  • Computational Complexity: While the approach is efficient, the complexity can still increase with larger state spaces or more complex specifications (as seen in Experiment #13).
  • Abstraction Fidelity: The abstraction process inherently involves some loss of information. The paper discusses how the robust MDP abstraction provides bounds on the satisfaction probability, acknowledging that these are not exact for the original system.
  • Future Work: The authors mention that their framework can be extended to more complex logical specifications beyond reach-avoidance (e.g., sc-LTL, LTLf, PCTL). They also suggest exploring more general forms of uncertainty and system dynamics. The paper also highlights the potential for further algorithmic improvements in strategy synthesis.

Summary updated

Abstract

We present a novel framework for formal control of uncertain discrete-time switched stochastic systems against probabilistic reach-avoid specifications, defined as the probability of reaching a goal region while being safe. In particular, we consider stochastic systems with additive noise, whose distribution lies in an ambiguity set of distributions that are $\varepsilon-$close to a nominal one according to the Wasserstein distance. For this class of systems, we derive control synthesis algorithms that are robust against all these distributions and maximize the probability of satisfying a reach-avoid specification. The framework we present first learns an abstraction of a switched stochastic system as a robust Markov decision process (robust MDP) by accounting for both the stochasticity of the system and the uncertainty in the noise distribution. Then, it synthesizes a strategy on the resulting robust MDP that maximizes the probability of satisfying the property and is robust to all uncertainty in the system. This strategy is then refined into a switching strategy for the original stochastic system. By exploiting tools from optimal transport and stochastic programming, we show that synthesizing such a strategy reduces to solving a set of linear programs, thus guaranteeing efficiency. We experimentally validate the efficacy of our framework on various case studies, including both linear and non-linear switched stochastic systems.
BibTeX
@inproceedings{gracia2023distributionally,
  author = {Ibon Gracia and Dimitris Boskos and Luca Laurenti and Manuel Mazo Jr.},
  title = {{Distributionally Robust Strategy Synthesis for Switched Stochastic Systems}},
  booktitle = {Hscc},
  year = {2023},
  doi = {10.1145/3575870.3587127},
}

Loading related content...

Figure